H. Оленьи игры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На северном полюсе проживают $$$n$$$ оленей, и все они соревнуются за первые позиции в таблице лидеров на главной странице CodeNorses (популярный сайт по спортивным оленьим играм). Довольно примечательно, что лидерство в таблице зависит от вклада и напрямую не связано с уровнем навыков в самих оленьих играх, однако для оленей таблица все равно крайне важна.

На текущий момент, у $$$i$$$-го оленя вклад равен $$$a_i$$$. Вы хотите повлиять на таблицу лидеров с помощью нескольких операций. За одну операцию вы можете выбрать оленя и либо увеличить, либо уменьшить его вклад на $$$1$$$. Отрицательные вклады разрешены.

При этом у вас есть $$$m$$$ ограничений на получившиеся вклады. Каждое ограничение задается упорядоченной парой $$$(u, v)$$$, означающей, что в финальный вклад оленя $$$u$$$ должен быть меньше или равен финального вклада оленя $$$v$$$.

Ваша задача — сделать наименьшее количество операций так, чтобы все ограничения были выполнены.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2\le n\le 1000$$$; $$$1\le m\le 1000$$$) — количество оленей и ограничений, соответственно.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1,\ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$), где $$$a_i$$$ равно первоначальному вкладу $$$i$$$-го оленя.

В следующих $$$m$$$ строках заданы сами ограничения.

В $$$i$$$-й строке заданы два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1\le u_i, v_i\le n$$$; $$$u_i\ne v_i$$$) — номера оленей в $$$i$$$-м ограничении.

Выходные данные

Выведите $$$n$$$ целых чисел $$$b_1,\ldots, b_n$$$ ($$$-10^{15}\le b_i\le 10^{15}$$$), где $$$b_i$$$ будет равно финальному вкладу $$$i$$$-го оленя после применения всех операций.

Если существует несколько решений с наименьшим количеством операций, выведите любое из них.

Можно доказать, что всегда существует оптимальное решение с $$$|b_i|\le 10^{15}$$$ для всех $$$i$$$.

Примеры
Входные данные
7 6
3 1 4 9 2 5 6
1 2
2 3
3 4
4 5
5 6
6 7
Выходные данные
1 1 4 4 4 5 6
Входные данные
4 6
6 5 8 2
3 1
4 1
3 2
1 2
2 3
3 1
Выходные данные
6 6 6 2
Входные данные
10 18
214 204 195 182 180 176 176 172 169 167
1 2
3 2
4 2
5 2
6 2
7 2
8 2
9 2
10 2
6 1
6 2
6 3
6 4
6 5
6 7
6 8
6 9
6 10
Выходные данные
204 204 195 182 180 167 176 172 169 167