E. Предвыборные обещания
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Байтландии, две политические партии борются за места в парламенте на предстоящих выборах: Партия Wrong Answer и Партия Time Limit Exceeded. Поскольку они хотят убедить как можно больше граждан отдать за них свои голоса, они продолжают обещать все более низкие налоги.

В байтландии есть $$$n$$$ городов, соединенных $$$m$$$ односторонними дорогами.

Также интересно, что дорожная сеть не имеет циклов — невозможно начать в каком-то городе, пройти по нескольким дорогам и вернуться в этот город.

В прошлом году, жители $$$i$$$-го города должны были платить $$$h_i$$$ бурлей налога.

Теперь партии будут поочередно проводить избирательные съезды в разных городах.

Если партия проводит съезд в городе $$$v$$$, она должна уменьшить налог в этом городе до любого неотрицательного целого числа бурлей. Однако, в то же время она может произвольно изменить налоги в каждом из городов, которые могут быть достижимы из $$$v$$$, пройдя по одной дороге.

Единственное условие, которое должно быть выполнено, что налог в каждом городе должен оставаться неотрицательным целым количеством бурлей.

Первая партия, которое проводит съезд это Партия Wrong Answer. Ходят легенды, что партия, которая проведет последний съезд, победит на выборах.

Может ли Партия Wrong Answer победить, независимо от ходов Партии Time Limit Exceeded?

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

В первой строке записано два целых числа $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 200\,000$$$, $$$0 \leq m \leq 200\,000$$$) — количество городов и дорог в Байтландии.

В следующей строке записано $$$n$$$ целых чисел, разделенных пробелами $$$h_1, h_2, \dots, h_n$$$ ($$$0 \leq h_i \leq 10^9$$$); $$$h_i$$$ обозначает налог, который требуется платить в $$$i$$$-м городе.

В каждой из следующих $$$m$$$ строк записано по два целых числа ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), описывающих дорогу, ведущую из города $$$u$$$ в город $$$v$$$. Гарантируется, что в сети дорог нет циклов. Никакие две дороги не соединяют одну и ту же пару городов.

Можно показать, что съезды не могут продолжаться бесконечно для любого корректного теста.

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

Если Партия Wrong Answer может выиграть выборы, выведите WIN на первой строке вашего вывода. В этом случае, мы вас дополнительно просим вывести $$$n$$$ неотрицательных целых чисел $$$h'_1, h'_2, \dots, h'_n$$$ ($$$0 \leq h'_i \leq 2 \cdot 10^{18}$$$), описывающих налоги в каждом городе после первого съезда, которые позволят выиграть. Если существует несколько возможных ответов, вы можете вывести любой. Гарантируется, что если у партии есть выигрышный ход, то существует и выигрышный ход, в котором в каждом городе налог не превосходит $$$2 \cdot 10^{18}$$$ бурлей.

Если партия не может гарантировать свою победу, выведите LOSE в первой и единственной строке вывода.

Примеры
Входные данные
4 2
2 1 1 5
1 2
3 4
Выходные данные
WIN
1 5 1 5
Входные данные
4 2
1 5 1 5
1 2
3 4
Выходные данные
LOSE
Входные данные
3 3
314 159 265
1 2
1 3
3 2
Выходные данные
WIN
0 0 0
Входные данные
6 4
2 2 5 5 6 6
1 3
2 4
3 5
4 6
Выходные данные
LOSE
Примечание

В первом примере, Партия Wrong Answer должна провести съезд в городе $$$1$$$. Партия уменьшит налоги в этом городе до $$$1$$$ бурля. Так как город $$$2$$$ напрямую соединен с городом $$$1$$$, мы можем как угодно поменять налоги в этом городе. Партия должна поменять налог на $$$5$$$ бурлей. Можно просто доказать, что Time Limit Exceeded не может выиграть выборы после такого действия если Партия Wrong Answer будет играть оптимально.

Во втором примере теста представлена ситуация, которую мы создали после одного хода в предыдущем тесте; Так как сейчас это ход партии Wrong Answer, партия не может выиграть.

В третьем примере, мы должны провести съезд в первом городе, так как все города непосредственно соединены с ним, и мы можем поставить туда любое число, например, мы можем уменьшить налоги во всех города до нуля, что даст право Партии Wrong Answer сразу же выигрывать выборы.