На северном полюсе проживают \(n\) оленей, и все они соревнуются за первые позиции в таблице лидеров на главной странице CodeNorses (популярный сайт по спортивным оленьим играм). Довольно примечательно, что лидерство в таблице зависит от вклада и напрямую не связано с уровнем навыков в самих оленьих играх, однако для оленей таблица все равно крайне важна.
На текущий момент, у \(i\)-го оленя вклад равен \(a_i\). Вы хотите повлиять на таблицу лидеров с помощью нескольких операций. За одну операцию вы можете выбрать оленя и либо увеличить, либо уменьшить его вклад на \(1\). Отрицательные вклады разрешены.
При этом у вас есть \(m\) ограничений на получившиеся вклады. Каждое ограничение задается упорядоченной парой \((u, v)\), означающей, что в финальный вклад оленя \(u\) должен быть меньше или равен финального вклада оленя \(v\).
Ваша задача — сделать наименьшее количество операций так, чтобы все ограничения были выполнены.
Выходные данные
Выведите \(n\) целых чисел \(b_1,\ldots, b_n\) (\(-10^{15}\le b_i\le 10^{15}\)), где \(b_i\) будет равно финальному вкладу \(i\)-го оленя после применения всех операций.
Если существует несколько решений с наименьшим количеством операций, выведите любое из них.
Можно доказать, что всегда существует оптимальное решение с \(|b_i|\le 10^{15}\) для всех \(i\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
4 6
6 5 8 2
3 1
4 1
3 2
1 2
2 3
3 1
|
6 6 6 2
|
|
3
|
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
|