Trung's city of residence can be represented on a coordinate plane. The entire city is a square with sides parallel to the coordinate axes, bounded by two points ~(0, 0)~ and ~(n, n)~. Currently, the city is under attack by terrorists. They have placed ~m~ bombs throughout the city, with the ~i~-th bomb placed at the position with coordinates ~(x_i, y_i)~.

Each bomb has a destructive power of ~l~. When a bomb at position ~(x, y)~ explodes, all locations with coordinates ~(p, q)~ in the city that satisfy ~x - l \le p \le x + l~ and ~y - l \le q \le y + l~ will be destroyed. If there is another bomb at location ~(p, q)~ that is destroyed, that bomb will also explode.

The terrorists plan to detonate one bomb to threaten the citizens. Currently, Trung is working at position ~(0, 0)~ and his house is located at position ~(n, n)~. From a position with coordinates ~(x, y)~, Trung can only move to ~4~ positions: ~(x- 1, y)~, ~(x, y-1)~, ~(x+1, y)~, ~(x, y+1)~, and cannot leave the city. Trung is worried that detonating a bomb may block his way home. Help Trung determine which bombs, when detonated, will prevent him from returning home so that he can quickly find a safe hiding place.

Input

The first line contains three positive integers ~n~, ~m~, ~l~ (~1 \leq n \leq 10^9~, ~1 \leq m \leq 2 \cdot 10^5~, ~0 \leq l \leq 10^9~) — the size of the city, the number of bombs, and the destructive power of each bomb.

The ~i~-th of the next ~m~ lines contains two integers ~x_i~ and ~y_i~ (~0 \leq x_i, y_i \leq n~) — the coordinates of the ~i~-th bomb. The data is generated such that no two bombs are placed at the same location and there may be exploding bombs at houses or companies.

Output

The first line contains an integer ~k~ — the number of bombs that, when detonated, will prevent Trung from returning home.

The ~i~-th of the next ~k~ lines contains two integers ~x_i~ and ~y_i~ describing the coordinates of a bomb. The bombs can be printed in any order.

Scoring

• Subtask 1 (~750~ points): ~n, m \leq 100~.

• Subtask 2 (~500~ points): ~m \leq 2000~.

• Subtask 3 (~1250~ points): no additional constraints.

If you solve this problem, you will receive ~2500~ points.

Sample Input 1

4 2 2
1 3
3 1

Sample Output 1

2
1 3
3 1

Sample Input 2

2 1 1
1 1

Sample Output 2

1
1 1

Notes

In the first example, there are two bombs. It can be shown that when one bomb is detonated, the other bomb will also explode. Both bombs, when detonated, will block all paths back to Trung's home.

In the second example, there is only one bomb, but when this bomb explodes, all locations in the city will be destroyed.