## Dan's Monkeys

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Dan has many monkeys, and today he is training them to follow his commands. Dan draws an grid on the ground with rows and columns. Each cell has one monkey. Initially, the monkey at cell has the ID of , i.e., the 1st monkey is at cell , the 2nd monkey is at cell , and so on.

Dan will give commands. In each command, Dan will instruct the monkeys to take the following steps:

1. Dan will call the monkey at the cell to get out of the matrix.
2. Dan will let all monkeys shift to the left if the left spot is empty.
3. Dan will let all monkeys move forward if the forward spot is empty.
4. After the above operations, the empty spot will be at . Dan will let the monkey who is out of the matrix get back and stand at the cell .

Dan wants to get a list of the monkeys' IDs who have been called to get out of the matrix, but he forgot to record this information. Can you write a program to help him?

#### Input Specification

The first line of input contains three integers , , and (), indicating the number of rows, the number of columns, and the number of commands, respectively.

Each of the following lines contains two integers and (, ), indicating that the monkey at cell is asked to get out of the matrix.

#### Output Specification

Output lines. Each line contains one integer, the ID of the monkey who has been asked to get out of the matrix

, .
, .
.

#### Sample Input

2 2 3
1 1
2 2
1 2

#### Sample Output

1
1
4

#### Explanation

The sample case is explained by the following picture.