← 返回题目列表

Codeforces · 625/E

E. 青蛙打架

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

Ostap Bender 最近参观了青蛙农场,并受到启发,创作了自己的青蛙游戏。

循环游戏板上放置的青蛙数量,分为 m 个单元。单元格从 1 到 m 编号,但棋盘是循环的,因此编号 1 的单元格在移动方向上紧跟在编号 m 的单元格之后。第 i 个青蛙在轮到时可以跳跃寻找 ai 细胞。

青蛙轮流移动,游戏从青蛙 1 的移动开始。轮到第 i 个青蛙时,它向前移动 ai 细胞,击倒沿途的所有青蛙。如果第 i 个青蛙路径的最后一个单元格中有一只青蛙,则该青蛙也会被淘汰。此后,ai 值会根据本回合中被击倒的青蛙数量而减少。如果 ai 为零或为负值,则第 i 只青蛙不再移动。

1 号青蛙完成回合后,2 号青蛙开始移动,然后是 3 号青蛙,依此类推。当第 n 号青蛙移动后,青蛙 1 又开始移动,然后是青蛙 2,以此类推,如此循环下去。如果某只青蛙已经从棋盘上被击倒,我们认为它会跳过所有动作。

帮助 Ostap 确定,游戏结束时棋盘上会留下哪些青蛙?

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 109, n ≤ m)——分别是青蛙的数量和游戏板的大小。

接下来的 n 行包含青蛙描述 - 两个整数 pi 和 ai (1 ≤ pi, ai ≤ m) - 第 i 只青蛙最初占据的单元格数量和初始跳跃长度。所有 pi 都保证是不同的。

输出

第一行输出最终游戏板上青蛙的数量。在第二行中以任意顺序输出它们的数字。

示例

输入 #1

3 5
2 1
5 3
4 3

输出 #1

1
3

输入 #2

5 6
1 2
3 4
2 5
5 1
6 1

输出 #2

2
1 4

注意

在第一个示例中,第一只青蛙跳了 1 个单元格,并在 3 号单元格中完成。第二只青蛙跳了 3 个单元格,在 3 号单元格上完成,淘汰了 1 号青蛙。2 号青蛙的当前跳跃长度现在为 2。第三只青蛙跳到 2 号单元格,然后第二只青蛙跳到 5 号单元格。第三只青蛙依次在 5 号单元格中完成,并将 2 号青蛙从游戏板上移除。现在,它是游戏中仅存的青蛙了。

在第二个样本中,第一只青蛙跳跃了 2 个单元格,并击倒了单元格 2 和 3 中的青蛙。它的 ai 值现在为 0。然后第四只青蛙跳跃并击倒了第五只青蛙,它的 ai 现在也为 0。这两只青蛙将永远留在游戏板上。