← 返回题目列表

Codeforces · 1091/H

H. 新年和三色旗休闲

中文机器翻译题面 查看原题

Alice 和 Bob 在一个包含 $$$n$$$ 行和无限多列的网格上玩游戏。每行有三个标记,蓝色、白色和红色各一个。比赛开始前和每一步棋后,必须满足以下两个条件:

- 任意两个令牌不在同一单元格中。
- 在每行中,蓝色令牌位于白色令牌的左侧,红色令牌位于白色令牌的右侧。

首先,他们选择一个正整数$$$f$$$,其值在整个游戏中有效。其次,选择起始玩家并进行第一回合。然后玩家轮流进行。无法采取行动的玩家就输了。

在移动过程中,玩家首先选择一个整数 $$$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 可能永远不会移动蓝色令牌。请记住,移动后,代币相对位置的两个条件必须仍然成立。

两名玩家都发挥最佳。给定棋盘的初始状态,确定两场比赛谁获胜:如果爱丽丝开始,如果鲍勃开始。

输入

第一行包含两个整数 $$$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 开始时获胜者的姓名。

示例

输入 #1

1 6
0 3 9

输出 #1

Alice
Bob

输入 #2

1 2
0 3 9

输出 #2

Alice
Bob

输入 #3

10 133
-248 -193 -187
97 101 202
-72 67 91
23 89 215
-129 -108 232
-223 -59 236
-99 86 242
-137 -109 -45
-105 173 246
-44 228 243

输出 #3

Bob
Alice

注意

第一个例子如下:

当 Alice 开始时,她可以通过将蓝色和白色标记向右移动 $$$2$$$ 格,进入位置 $$$2~5~9$$$ 来获胜。无论鲍勃做什么,爱丽丝都会再走一步,然后游戏就结束了。例如,他可以将红色和白色标记向左移动 $$$2$$$ 单元格,达到状态 $$$2~3~7$$$。然后,爱丽丝可以将蓝色和白色代币移动$$$2$$$,进入$$$4~5~7$$$,在那里不可能再移动。

如果鲍勃开始,他将获得足够的优势来获胜。例如,他可以将红色标记向左移动$$$3$$$,进入位置$$$0~3~6$$$。例如,爱丽丝可以将蓝色令牌移动 $$$2$$$,而鲍勃则通过将红色令牌移动 $$$2$$$ 来反击。游戏在$$$2~3~4$$$位置结束。

在第二个例子中,禁止移动 $$$2$$$,但这并不能阻止 Alice 获胜!她可以将蓝色和白色标记移动$$$4$$$,进入位置$$$4~7~9$$$。现在鲍勃没有移动,因为移动 $$$2$$$ 是被禁止的。