Frog Fights

题意翻译

有 $n$ 只青蛙在一个长度为 $m$ 的环上打架；每只青蛙有一个初始位置 $p_i$，和一个跳跃数值 $a_i$。从 $1$ 号青蛙开始按序号循环行动，每次若第 $i$ 只青蛙行动，则它会向前跳 $a_i$ 个格子，撞飞它遇见的所有青蛙，包括终点格子上的，之后它的 $a_i$ 减去撞飞的青蛙只数，若 $a_i<0$，它不会移动。求最后剩下的所有青蛙的编号。 $n≤10^5$，$m≤10^9$，不会有两只青蛙一开始在同一个格子里。

题目描述

Ostap Bender recently visited frog farm and was inspired to create his own frog game. Number of frogs are places on a cyclic gameboard, divided into $ m $ cells. Cells are numbered from $ 1 $ to $ m $ , but the board is cyclic, so cell number $ 1 $ goes right after the cell number $ m $ in the direction of movement. $ i $ -th frog during its turn can jump for $ a_{i} $ cells. Frogs move in turns, game starts with a move by frog $ 1 $ . On its turn $ i $ -th frog moves $ a_{i} $ cells forward, knocking out all the frogs on its way. If there is a frog in the last cell of the path of the $ i $ -th frog, that frog is also knocked out. After this the value $ a_{i} $ is decreased by the number of frogs that were knocked out during this turn. If $ a_{i} $ is zero or goes negative, then $ i $ -th frog doesn't make moves anymore. After frog number $ 1 $ finishes its turn, frog number $ 2 $ starts to move, then frog number $ 3 $ and so on. After the frog number $ n $ makes its move, frog $ 1 $ starts to move again, then frog $ 2 $ and so on this process goes forever. If some frog was already knocked out from the board, we consider that it skips all its moves. Help Ostap to identify, what frogs will stay on the board at the end of a game?

输入输出格式

输入格式

First line of the input contains two integers $ n $ and $ m $ ( $ 1<=n<=100000,1<=m<=10^{9},n<=m $ ) — number of frogs and gameboard size, respectively. Following $ n $ lines contains frogs descriptions — two integers $ p_{i} $ and $ a_{i} $ ( $ 1<=p_{i},a_{i}<=m $ ) — the number of cell occupied by $ i $ -th frog initially and initial jump length. All $ p_{i} $ are guaranteed to be distinct.

输出格式

In the first line output number of frogs on the final gameboard. In the second line output their numbers in any order.

输入输出样例

输入样例 #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 

说明

In the first sample first frog jumps $ 1 $ cell and finishes in cell number $ 3 $ . Second frog jumps for $ 3 $ cells and finishes on cell number $ 3 $ , knocking out frog number $ 1 $ . Current jump length for frog number $ 2 $ is now $ 2 $ . Third frog jumps to cell $ 2 $ , then second frog jumps to cell $ 5 $ . Third frog in turn finishes in cell $ 5 $ and removes frog $ 2 $ from the gameboard. Now, it's the only remaining frog in the game. In the second sample first frog jumps $ 2 $ cells and knocks out frogs in cells $ 2 $ and $ 3 $ . Its value $ a_{i} $ is now $ 0 $ . Then fourth frog jumps and knocks out fifth frog and its $ a_{i} $ is now $ 0 $ too. These two frogs will remains on the gameboard forever.

题意翻译

有 $n$ 只青蛙在一个长度为 $m$ 的环上打架；每只青蛙有一个初始位置 $p_i$，和一个跳跃数值 $a_i$。从 $1$ 号青蛙开始按序号循环行动，每次若第 $i$ 只青蛙行动，则它会向前跳 $a_i$ 个格子，撞飞它遇见的所有青蛙，包括终点格子上的，之后它的 $a_i$ 减去撞飞的青蛙只数，若 $a_i<0$，它不会移动。求最后剩下的所有青蛙的编号。 $n≤10^5$，$m≤10^9$，不会有两只青蛙一开始在同一个格子里。