CF1091H New Year and the Tricolore Recreation

Alice 和 Bob 在一个有 $n$ 行、无限多列的网格上玩游戏。每一行上有三个棋子，分别是蓝色、白色和红色。在游戏开始前以及每次移动后，必须满足以下两个条件： - 任意两个棋子不能在同一个格子里。 - 在每一行中，蓝色棋子必须在白色棋子的左侧，红色棋子必须在白色棋子的右侧。 首先，他们选择一个正整数 $f$，该值在整个游戏过程中都有效。然后，选择先手玩家并进行第一次操作。之后两人轮流操作。无法进行操作的一方判负。 每次操作时，玩家首先选择一个整数 $k$，$k$ 必须是质数或两个（可以相同）质数的乘积。也就是说，$k$ 的最小可能取值为 $2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, \dots$。此外，$k$ 不能等于之前选定的整数 $f$。每回合只能在某一行进行一次操作。 如果轮到 Alice，她可以选择一个蓝色棋子，将其向右移动 $k$ 格。或者，她也可以将同一行的蓝色和白色棋子都向右移动 $k$ 格。 如果轮到 Bob，他可以选择一个红色棋子，将其向左移动 $k$ 格。或者，他也可以将同一行的白色和红色棋子都向左移动 $k$ 格。 注意，Alice 不能移动红色棋子，Bob 不能移动蓝色棋子。每次操作后，棋子的相对位置必须始终满足上述两个条件。 两位玩家都采取最优策略。给定棋盘的初始状态，分别判断 Alice 先手和 Bob 先手时，谁能获胜。

第一行包含两个整数 $n$ 和 $f$（$1 \leq n \leq 10^5$，$2 \leq f \leq 2 \cdot 10^5$）——表示行数和禁止的步长。 接下来的 $n$ 行，每行包含三个整数 $b_i$、$w_i$、$r_i$（$-10^5 \leq b_i < w_i < r_i \leq 10^5$），表示第 $i$ 行中蓝色、白色和红色棋子所在的列编号。

输出两行。 第一行输出 Alice 先手时的胜者名字，第二行输出 Bob 先手时的胜者名字。

第一个样例如下： 当 Alice 先手时，她可以将蓝色和白色棋子同时向右移动 $2$ 格，变为 $2~5~9$。无论 Bob 如何操作，Alice 都能多走一步，然后游戏结束。例如，Bob 可以将红色和白色棋子同时向左移动 $2$ 格，变为 $2~3~7$。Alice 再将蓝色和白色棋子同时向右移动 $2$ 格，变为 $4~5~7$，此时已无法再移动。 如果 Bob 先手，他可以获得足够的优势获胜。例如，他可以将红色棋子向左移动 $3$ 格，变为 $0~3~6$。Alice 可以选择将蓝色棋子向右移动 $2$ 格，但 Bob 可以用 $2$ 步反制，最后棋盘变为 $2~3~4$，游戏结束。 第二个样例中，禁止步长为 $2$，但这并不妨碍 Alice 获胜！她可以将蓝色和白色棋子同时向右移动 $4$ 格，变为 $4~7~9$。此时 Bob 无法移动，因为步长 $2$ 被禁止。 由 ChatGPT 4.1 翻译