[SDOI2016]硬币游戏

题目描述

Alice 和 Bob 现在在玩的游戏,主角是依次编号为 1 到 n 的 n 枚硬币。每一枚硬币都有两面,我们分别称之为正面和反面。一开始的时候,有些硬币是正面向上的,有些是反面朝上的。Alice 和 Bob 将轮流对这些硬币进行翻转操作,且Alice 总是先手。 具体来说每次玩家可以选择一枚编号为 x,要求这枚硬币此刻是反面朝上的。对于编号 x 来说,我们总可以将 x 写成 $ \cdot 2^a \cdot 3^b$ ,其中 a 和 b 是非负整数,c 是与 2,3 都互质的非负整数,然后有两种选择: 选择整数 p,q 满足 $a \ge pq , p \ge 1$ 且 $1 \leq q \leq \text{MAXQ}$,然后同时翻转所有编号为 $c \cdot 2^{a-pj} \cdot 3^b$ 的硬币,其中 $j = 0, 1, 2, \ldots q$。 选择整数 p,q 满足 $b \geq pq, p \ge 1$ 且 $1 \leq q \leq \text{MAXQ}$,然后同时翻转所有编号为 $c \cdot 2^a \cdot 3^{b-pj}c$的硬币,其中$j = 0, 1, 2, \ldots q$。 可以发现这个游戏不能无限进行下去,当某位玩家无法继续操作上述操作时,便输掉了游戏。作为先手的 Alice,总是希望可以在比赛开始之前就知道自己能否获胜。她知道自己和 Bob 都是充分聪明的,所以在游戏过程中,两人都会最优化自己的策略并尽量保证自己处于不败的情形中。

输入输出格式

输入格式


本题有多组测试数据,第一行输入一个整数T,表示总的数据组数。之后给出T组数据 每组数据第一行输入两个整数n,MAXQ 第二行输入n个整数,第i个数表示第i个硬币的初始状态,0表示反面朝上,1表示正面朝上

输出格式


输出共有t行。对于每一组数据来说,如果Alice先手必胜,则输出"win"(不包括引号),否则输出"lose"

输入输出样例

输入样例 #1

6
16 14
1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1
16 14
0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1
16 11
0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 1
16 12
1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0
16 4
1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0
16 20
0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0

输出样例 #1

win
lose
win
lose
win
win

说明

对于100%的数据$1\le n \le 30000,1 \le MAXQ \le 20,t\le 100$。