Description

Walnut Bowling is a minigame in Plants vs. Zombies. Now Crazy Dave only gave lxhgww some ordinary walnuts and asked lxhgww to throw them like bowling balls to smash the zombies in the yard.

The yard consists of $N$ lanes, numbered from $1$ to $N$ from top to bottom. Each lane is divided into cells. There are $M$ zombies in total, each standing in some cell, and you may assume their positions are fixed.

The game has $K$ rounds. In each round, you can choose one lane and throw a walnut. The thrown walnut first rolls straight from left to right along that lane. After it hits the first zombie, it begins to roll along a $45$-degree diagonal toward the center line of the yard (that is, in the first $N/2$ lanes it rolls down-right, and in the last $N/2$ lanes it rolls up-right; it is guaranteed that $N$ is even). The yard is bounded by walls. When a diagonally moving walnut hits a wall or a zombie, it bounces: up-right becomes down-right, or vice versa. The round ends when the walnut can no longer hit any zombie.

Note: Multiple zombies may stand in the same cell; in that case, each time the walnut only kills one zombie in that cell. To kill as many zombies as possible, at the start of each round lxhgww chooses the lane whose resulting path will kill the maximum number of zombies under the current state. When there is a tie, he chooses the lane with the smallest index.

To evaluate this strategy, lxhgww needs your help to compute the number of zombies that can be killed by this method.

Input Format

The first line contains three integers $N$, $M$, $K$. Then each of the next $M$ lines contains two integers $X_i$, $Y_i$, meaning that the $i$-th zombie is at lane $Y_i$, column $X_i$ (the $X_i$-th cell from the left).

Output Format

Output $K+1$ lines. The first $K$ lines each contain two integers $A_i, B_i$, meaning that in the $i$-th round, the walnut is thrown from lane $A_i$ and hits $B_i$ zombies during its movement. The last line contains a single integer: the total number of zombies hit.

4 2 1
1 2
5 2

2 2
2

Hint

Constraints

For $20\%$ of the testdata, it is guaranteed that: $N \le 200$, $M \le 500$, $K \le 200$, $X_i \le 200$.

For $50\%$ of the testdata, it is guaranteed that: $N \le 200$, $M \le 2\times 10^5$, $K \le 200$, $X_i \le 10^6$.

For $100\%$ of the testdata, it is guaranteed that: $N \le 20000$, $M \le 2\times 10^5$, $K \le 10^5$, $X_i \le 10^6$.

For all testdata, it is guaranteed that: $1 \le Y_i \le N$.

Translated by ChatGPT 5