又是啥诗山
体面：
环形博弈胜负判定
1. 问题描述
给定一个包含 nnn 个位置的环，位置编号为 0,1,…,n−10,1,\dots,n-10,1,…,n−1，其中位置 000 为终止位置。初始位置为 111 到 n−1n-1n−1 中的某个位置。
有两个行动方（编号为 111 和 222）：
* 行动方 111 有步长集合 s1s_1s1 。
* 行动方 222 有步长集合 s2s_2s2 。
若当前轮到行动方 ppp，则必须从 sps_psp 中选择一个步长 xxx，并将当前位置 iii 更新为 (i+x) mod n(i+x) \bmod n(i+x)modn。若更新后位置为 000，则执行本次行动的一方获胜。
对于每个先手行动方及每个初始位置 1,2,…,n−11,2,\dots,n-11,2,…,n−1，判断先手方在双方最优策略下的结果：
* 必胜（Win）：存在一种策略保证获胜。
* 必败（Lose）：无论怎么走，对方都能获胜。
* 无限进行（Loop）：无法保证获胜但可以避免失败，使过程无限循环。
2. 输入格式
第一行包含整数 TTT（测试数据组数）。
对于每组测试数据：
* 第一行：整数 nnn。
* 第二行：整数 k1k_1k1 ，随后 k1k_1k1 个互不相同的整数 s1,1,s1,2,…,s1,k1s_{1,1},s_{1,2},\dots,s_{1,k_1}s1,1 ,s1,2 ,…,s1,k1 （行动方 111 的步长集合）。
* 第三行：整数 k2k_2k2 ，随后 k2k_2k2 个互不相同的整数 s2,1,s2,2,…,s2,k2s_{2,1},s_{2,2},\dots,s_{2,k_2}s2,1 ,s2,2 ,…,s2,k2 （行动方 222 的步长集合）。
3. 输出格式
对每组测试数据输出两行：
* 第一行：n−1n-1n−1 个单词，第 iii 个单词表示行动方 111 先手且初始位置为 iii 时的结果。
* 第二行：n−1n-1n−1 个单词，第 iii 个单词表示行动方 222 先手且初始位置为 iii 时的结果。
结果只能是以下三种：
* Win（必胜）
* Lose（必败）
* Loop（进行）
4. 数据范围
* 1≤T≤1001 \le T \le 1001≤T≤100
* 2≤n≤70002 \le n \le 70002≤n≤7000
* 1≤k1,k2≤n−11 \le k_1,k_2 \le n-11≤k1 ,k2 ≤n−1
* 1≤sp,j≤n−11 \le s_{p,j} \le n-11≤sp,j ≤n−1，且集合 sps_psp 内元素互不相同
* 所有测试数据满足 ∑n≤7000\sum n \le 7000∑n≤7000
5. 样例
输入
输出
样例解释
第一组数据（n=5n=5n=5）：
* 第一行：行动方 111 先手时，初始位置 1,2,3,41,2,3,41,2,3,4 的结果分别为 Lose、Win、Win、Loop。
* 第二行：行动方 222 先手时，初始位置 1,2,3,41,2,3,41,2,3,4 的结果分别为 Loop、Win、Win、Win。
第二组数据（n=8n=8n=8）：
* 第一行：行动方 111 先手时，位置 111 到 777 的结果均为 Win。
* 第二行：行动方 222 先手时，位置 111 到 777 的结果为 Lose、Win、Lose、Lose、Win、Lose、Lose。
数据范围
* 1≤T≤1001 \le T \le 1001≤T≤100
* 2≤n≤70002 \le n \le 70002≤n≤7000
* 1≤k1,k2≤n−11 \le k_1, k_2 \le n-11≤k1 ,k2 ≤n−1
* 1≤sp,j≤n−11 \le s_{p,j} \le n-11≤sp,j ≤n−1
* 对于每个 p∈{1,2}p \in \{1,2\}p∈{1,2}，集合 sps_psp 内的数互不相同
* 所有测试数据满足 ∑n≤7000\sum n \le 7000∑n≤7000
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
蒟蒻的思路
1. 分析
这是一道分党派带环有向图博弈问题：
* 两名玩家拥有各自独立的步长集合，属于非公平博弈，无法使用公平博弈中的 SG 函数求解。
* 游戏在环形位置上进行，走到位置 0 的玩家直接获胜，最终存在必胜、必败、无限循环三种结果。
* 核心解法为反向拓扑排序（BFS 胜负传播）：从确定的终止胜负态出发，反向推导所有状态的博弈结果。
2. 大炮状态
我们通过两个二维数组维护博弈状态：
* dp[player][pos]：记录当前轮到 player 行动、处于位置 pos 时的博弈结果
* 0：结果未确定，最终对应无限循环（Loop）
* 1：当前玩家必胜（Win）
* 2：当前玩家必败（Lose）
* topo[player][pos]：拓扑排序的度数数组，记录当前状态未确定结果的后继状态数量
* 初始值为对应玩家的步长总数
* 当度数减为 0 时，说明所有后继都是必胜态，当前状态为必败态
3. 博弈规则
双方均采取最优策略，状态转移遵循以下公理：
1. 必胜态：若当前状态存在至少一个后继是必败态，则当前状态为必胜态——选择该步即可让对手陷入必败局面。
2. 必败态：若当前状态的所有后继都是必胜态，则当前状态为必败态——无论怎么走，对手都处于必胜局面。
3. 循环态：BFS 结束后仍未被标记的状态，既无法保证一步制胜，也不会必然落入必败，双方可以通过策略让游戏无限循环。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本题与公平博弈问题区别
1.分党派博弈定义：不同玩家拥有独立、不相同的合法操作集合，双方行动权限不对称。
·特征：不能使用 SG 函数、Sprague-Grundy 定理失效，只能暴力拓扑 / 记忆化推导状态；
2.公平博弈定义：任意局面下，双方玩家拥有完全相同的合法移动集合，没有专属操作。
·特征：理论支撑：Sprague-Grundy 定理，所有公平博弈都能等价为尼姆堆，用 SG 函数快速计算胜负；
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
注意事项：
无环有向图博弈和带环有向图博弈
前者只有Win, Lose两种结果。后者则多出一个Loop（平局）
前者用正拓扑排序，后者用必须使用反向拓扑排序
