CF1458E Nim Shortcuts

在你的首款手机游戏“Nim”大获成功后，你决定制作续作“Nim 2”。这款游戏将在经典 Nim 游戏的基础上扩展，加入备受期待的第二堆石子！ 游戏中有两堆石子，每堆包含非负数量的石子。两名玩家轮流行动。在每一回合，玩家可以从任意一堆中取走任意正整数数量的石子。无法行动的玩家判负。 为了方便测试，你引入了开发者快捷方式。有 $n$ 个快捷位置 $(x_1, y_1), \ldots, (x_n, y_n)$。规则变更如下：假设在某一玩家回合前，第一堆和第二堆分别有 $x$ 和 $y$ 个石子。如果 $(x, y)$ 等于某个 $(x_i, y_i)$，那么即将行动的玩家立即判负，否则可以正常行动。注意，堆的顺序是有区分的，即 $x$ 必须指第一堆的石子数，$y$ 必须指第二堆的石子数。 游戏发布后，开发者快捷方式也被加入了正式版！玩家们抱怨 AI 在某些阶段变得不可战胜。你现在需要编写程序，判断在给定的初始局面下，先手玩家是否必胜（假设双方都采取最优策略）。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$），分别表示快捷位置的数量和需要判断的初始局面数量。 接下来的 $n$ 行描述快捷位置。第 $i$ 行包含两个整数 $x_i, y_i$（$0 \leq x_i, y_i \leq 10^9$）。保证所有快捷位置互不相同。 接下来的 $m$ 行描述初始局面。第 $i$ 行包含两个整数 $a_i, b_i$（$0 \leq a_i, b_i \leq 10^9$），分别表示第一堆和第二堆的石子数。保证所有初始局面互不相同，但初始局面不一定与快捷位置不同。

对于每个初始局面，输出一行，如果先手玩家能获胜则输出“WIN”，否则输出“LOSE”。

由 ChatGPT 4.1 翻译