QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[0]

# 4106. 硬币游戏

Statistics

Alice 和 Bob 现在在玩的游戏,主角是依次编号为 1nn 枚硬币。每一枚硬币都有两面,我们分别称之为正面和反面。一开始的时候,有些硬币是正面向上的,有些是反面朝上的。Alice 和 Bob 将轮流对这些硬币进行翻转操作,且Alice 总是先手。

具体来说每次玩家可以选择一枚编号为 x,要求这枚硬币此刻是反面朝上的。对于编号 x 来说,我们总可以将 x 写成 x=c2a3b,其中 ab 是非负整数,c 是与 2,3 都互质的非负整数,然后有两种选择:

  1. 选择整数 p,q 满足 apq, p11qMAXQ,然后同时翻转所有编号为 c2apj3b 的硬币,其中 j=0,1,2,,q
  2. 选择整数 p,q 满足 bpq, p11qMAXQ,然后同时翻转所有编号为 c2a3bpj 的硬币,其中 j=0,1,2,,q

可以发现这个游戏不能无限进行下去,当某位玩家无法继续操作上述操作时,便输掉了游戏。作为先手的 Alice,总是希望可以在比赛开始之前就知道自己能否获胜。她知道自己和 Bob 都是充分聪明的,所以在游戏过程中,两人都会最优化自己的策略并尽量保证自己处于不败的情形中。

输入格式

本题有多组测试数据,第一行输入一个整数 T,表示总的数据组数。

之后给出 T 组数据,每组数据第一行输入两个整数 n,MAXQ

第二行输入 n 个整数,第 i 个数表示第 i 个硬币的初始状态,0 表示反面朝上,1 表示正面朝上。

输出格式

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

样例数据

样例输入

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

样例输出

win
lose
win
lose
win
win

子任务

测试点 n MAXQ
1 16 20
2 32 20
3 36 20
4 40 20
5 10000 1
6 20000 1
7 30000 1
8 10000 20
9 20000 20
10 30000 20

对于 100% 的数据,1n30000, 1MAXQ20, t100