提示: 欢迎访问OurACM平台
Problem 1072 The Frog Show

Accept: 4    Submit: 18
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

N well-trained frogs are going to have a jump show. They are numbered as 1,2,...,N. There are M (M>=N) open boxes on the floor lining up from left to right, numbered as 1,2,...,M. At the beginning of the show, each of the N frogs occupies a box, facing left or right. During the show every frog jumps to the next box in the front of him every other second, except:

(1) No box is before him, and he has to jump onto the floor, and then quit the show.

(2) The frog in the neighboring box or next to an empty box in the front of him is facing him, or the frog in the neighboring box in the front of him turns about, then he has to turn about and face to the opposite direction. At this moment, he does not jump.

Design a program to solve the following problem: Given the number of box where each frog is and the direction each frog faces at the beginning of the show, work out the number of the frog who quits the show last (if two frogs quit the show last at the same time, then just work out the number of the frog who quits the show last at the left).

Input

The input consists of several test cases. For each test case, the first line contains two integers N and M (1<=N<=M<=10000), indicating the number of frogs and the number of boxes respectively. The following N lines are the data denoting the initial states of n frogs at the beginning of the show, and each line contains two integers. In the ith line, the first integer indicates the direction the number i frog faces (0 indicating left, 1 indicating right) and the second integer is the number of the box the number i frog occupies at the beginning. Every two test cases are separated by one blank line and two integers in the same line are separated by one space .The last test case is followed by a blank line and a line contains two 0's, which indicates the end of the input.

Output

For each test case, output a line containing an integer representing the number of the frog who quits the show last.

Sample Input

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

Sample Output

2 2

Source

FJNUPC 2005

Submit  Back  Status  Discuss