P7387 「EZEC-6」象棋

> 万籁停吹奏 $\newline$支颐听秋水问蜉蝣 $\newline$既玄冥不可量北斗 $\newline$却何信相思最温柔

象棋将会由两个玩家进行游玩，其中红方为先手，黑方为后手。象棋里有很多种棋子，PF 对其中的“炮”情有独钟，炮的操作为：如果任意一方的某个炮和对方的某个炮之间的位置上**有且仅有一个炮**，那么这一方可以将对方的炮移出棋盘，并将他的炮移到对方的炮的位置。 PF 厌倦了传统象棋的玩法，因此他拿出了一张 $1$ 行 $n$ 列的棋盘。棋盘上的每个位置都有且仅有一个炮，每个炮都隶属于红方或黑方。对于每个回合，操作方可以进行一次操作，也可以不进行操作，然后将操作权交给对手。若双方均同意结束或者无棋可动，游戏结束。 游戏将进行 $T$ 局。每一局 PF 都是红方。定义游戏的胜利条件为一方的剩余的炮的数量大于对方。他想知道，若双方均使用最佳策略，他是否有必胜策略。

第一行一个整数 $T$，表示测试数据的数量。 对于每组数据，第一行一个整数 $n$，表示棋盘大小。 接下来一行一个字符串，其中第 $i$ 个整数 $a_i$ 表示第 $i$ 个棋子的种类，其中 $1$ 表示红方的炮， $0$ 表示黑方的炮。

输出共 $T$ 行，若第 $i$ 组有必胜策略，输出 `WIN`，若为平局输出 `TIE`，否则输出 `LOSE`。

**由于本题输入量较大，请使用较快的读入方法。** **【数据范围】** **本题采用捆绑测试。** |子任务编号|$T\le$|$n\le$|$\sum n\le$|分值| |:-:|:-:|:-:|:-:|:-:| |$1$|$20$|$3$|$60$|$5$| |$2$|$10^3$|$6$|$6\times10^3$|$10$| |$3$|$10^5$|$15$|$1.5\times10^6$|$15$| |$4$|$200$|$200$|$500$|$20$| |$5$|$10^5$|$10^6$|$2\times10^6$|$25$| |$6$|$10^5$|$10^7$|$2\times10^7$|$25$| 对于 $100\%$ 的数据， $1\le T \le 10^5$，$1 \le n \le 10^7$，$\sum n \le 2\times 10^7$，$a \in \{0,1\}$。 **【样例解释】** 对于第一组数据，没有任何棋子能够移动，而棋面红棋子数大于黑棋，故先手有必胜策略。 对于第二组数据，一种平局的变化如下： ```cpp 0 1 1* 0 0* 0 1 0 1 ``` 对于第三组数据，双方的最佳策略有如下两种可能： ```cpp 0 1 1* 1 0* 0* 1 1* 1 1 0 1 ``` ```cpp 0* 1 1* 1 0 1 1* 1 0* 1 0 1 ``` 两种结果均为红炮剩余数量多，故红棋必胜。 对于第四组数据，红棋只有一种操作可行： ```cpp 1* 0 0* 0 0 1 0 ``` 无棋可走后黑炮数量更多。