在Byteland,有两个政党在即将到来的选举中争夺议会席位:错误答案党和超时党。由于他们希望说服尽可能多的公民为他们投票,因此他们不断承诺降低税收。
Byteland 有 $$$n$$$ 个城市,由 $$$m$$$ 单向道路连接。有趣的是,道路网络没有循环——不可能从任何城市出发,沿着多条道路行驶,然后返回该城市。去年,第 $$$i$$$ 个城市的公民必须缴纳 $$$h_i$$$ 布尔税。
政党现在将在各个城市轮流举行选举大会。如果一方在$$$v$$$城市举行大会,则该一方需要将该城市的税收减少到非负整数布尔。然而,同时他们可以任意修改使用单条道路从 $$$v$$$ 可以到达的每个城市的税收。必须满足的唯一条件是每个城市的税收必须保持非负整数布尔值。
第一个召开大会的政党是错误答案党。预计举行最后一次代表大会的政党将赢得选举。无论超时一方如何行动,错误答案一方能否获胜?
输入
输入的第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 200\,000$$$, $$$0 \leq m \leq 200\,000$$$) — Byteland 中城市和道路的数量。
下一行包含 $$$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$$$ 的单向道路。道路网络中不会有自行车。没有两条道路会连接同一对城市。
我们可以证明,对于任何正确的测试用例,约定不能无限期地举行。
输出
如果错误答案党能够赢得选举,请在输出的第一行输出 WIN。在这种情况下,您还需要制定任何约定,无论对手的行为如何,都可以让一方获胜。第二行应包含 $$$n$$$ 非负整数 $$$h'_1, h'_2, \dots, h'_n$$$ ($$$0 \leq h'_i \leq 2 \cdot 10^{18}$$$) 描述会议后连续城市缴纳的税额。如果有多个答案,则输出任意一个。我们保证,如果一方有任何获胜的举动,则存在一个举动,之后没有城市必须支付超过 $$$2 \cdot 10^{18}$$$ 布尔斯。
如果一方不能确保胜利,则在输出的第一行也是唯一一行中输出 LOSE。
示例
输入 #1
4 2 2 1 1 5 1 2 3 4
输出 #1
WIN 1 5 1 5
输入 #2
4 2 1 5 1 5 1 2 3 4
输出 #2
LOSE
输入 #3
3 3 314 159 265 1 2 1 3 3 2
输出 #3
WIN 0 0 0
输入#4
6 4 2 2 5 5 6 6 1 3 2 4 3 5 4 6
输出#4
LOSE
注意
在第一个例子中,错误答案党应该在$$$1$$$城市举行大会。该党将把这个城市的税收降低到 $$$1$$$ bourle。由于从$$$1$$$可以直接到达城市$$$2$$$,所以我们可以任意修改这个城市的税收。该党应该将税收改为$$$5$$$ bourles。很容易证明,如果错误答案党发挥最佳,则超过时间限制在这一步之后就无法赢得选举。
第二个示例测试呈现了我们在上一个测试中单步移动后创建的情况;由于现在是错误答案党的举动,该党无法获胜。
第三次测试,我们应该在第一个城市举行大会。这使我们能够将任何城市的税收更改为任何想要的值;例如,我们可以决定将所有税收设置为零,这使得错误答案党立即赢得选举。