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$$$ 是被禁止的。