Nut Bowling is a mini-game in Plants vs. Zombies. Crazy Dave has given lxhgww some ordinary nuts and asked him to throw them like bowling balls to crush the zombies in the yard.

The yard consists of $N$ lanes, numbered from $1$ to $N$ from top to bottom, and each lane is divided into several cells. There are $M$ zombies in the yard, each standing in a specific cell, and their positions are considered stationary. The game consists of $K$ rounds. In each round, you can choose a lane and throw a nut. The thrown nut first rolls straight along the lane from left to right until it hits the first zombie. Then, it begins to roll along a $45^{\circ}$ diagonal path towards the center (i.e., nuts in the first $N/2$ rows roll towards the bottom-right, and nuts in the last $N/2$ rows roll towards the top-right; it is guaranteed that $N$ is even). The sides of the yard are walls. When a nut moving diagonally hits a wall or a zombie, it bounces, changing from moving towards the top-right to the bottom-right, or vice versa. The round ends when the nut can no longer hit any more zombies. Note: Multiple zombies may stand in the same cell; in this case, the nut will only crush one zombie in that cell each time it hits.

To crush as many zombies as possible, lxhgww decides that at the beginning of each round, he will choose the lane that allows the nut to crush the maximum number of zombies under the current conditions. If there is a tie, he will choose the lane with the smallest index. To understand the effectiveness of this strategy, calculate the total number of zombies crushed using this method.

Input

The first line contains three integers $N, M, K$.

The next $M$ lines each contain two integers $X_i, Y_i$, representing that the $i$-th zombie is located in the $Y_i$-th lane, in the $X_i$-th cell from the left.

Output

The output consists of $K+1$ lines.

The first $K$ lines each contain two integers $A_i$ and $B_i$, representing that in the $i$-th round, the nut was thrown from the $A_i$-th lane, and it crushed $B_i$ zombies during its path.

The last line contains a single integer representing the total number of zombies crushed.

Examples

Input 1

4 2 1
1 2
5 2

Output 1

2 2
2

Input 2

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

Output 2

2 3
2 2
5

Subtasks

For $20\%$ of the data, $N \le 200, M \le 500, K \le 200, X_i \le 200$.

For $50\%$ of the data, $N \le 200, M \le 2\times 10^5, K \le 200, X_i < 10^6$.

For $100\%$ of the data, $N \le 2\times 10^4, M \le 2\times 10^5, K \le 10^5, X_i \le 10^7+1, Y_i \le N$.