You are given $n$ distinct points on a plane. The coordinates of the $i$-th point are $(x_i, y_i)$.

For each point $i$, find the nearest (in terms of Manhattan distance) point with integer coordinates that is not among the given $n$ points. If there are multiple such points — you can choose any of them.

The Manhattan distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of points in the set.

The next $n$ lines describe points. The $i$-th of them contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le 2 \cdot 10^5$) — coordinates of the $i$-th point.

It is guaranteed that all points in the input are distinct.


-----Output-----

Print $n$ lines. In the $i$-th line, print the point with integer coordinates that is not among the given $n$ points and is the nearest (in terms of Manhattan distance) to the $i$-th point from the input.

Output coordinates should be in range $[-10^6; 10^6]$. It can be shown that any optimal answer meets these constraints.

If there are several answers, you can print any of them.


-----Examples-----

Input
6
2 2
1 2
2 1
3 2
2 3
5 5
Output
1 1
1 1
2 0
3 1
2 4
5 4
Input
8
4 4
2 4
2 2
2 3
1 4
4 2
1 3
3 3
Output
4 3
2 5
2 1
2 5
1 5
4 1
1 2
3 2


-----Note-----

None

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Shortest paths

Sorting

Data structures


Solutions:
import sys
from collections import deque
input = sys.stdin.readline

def solve(n, arr):
	included = set(arr)
	ans = {}
	dq = deque()
	for (x, y) in arr:
		for (nx, ny) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
			if (nx, ny) not in included:
				ans[x, y] = (nx, ny)
				dq.append((x, y))
	while dq:
		(x, y) = dq.popleft()
		for (nx, ny) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
			if (nx, ny) in included and (nx, ny) not in ans:
				ans[nx, ny] = ans[x, y]
				dq.append((nx, ny))
	for (x, y) in arr:
		print(*ans[x, y])
n = int(input())
arr = list([tuple(map(int, input().split())) for _ in range(n)])
solve(n, arr)


import collections
from functools import lru_cache
n = int(input())
m = 200000.0 + 1
t = []
d = {}
for i in range(n):
	(x, y) = map(int, input().split())
	d[x, y] = i
res = [[-1, -1] for i in range(n)]
deq = collections.deque()
visit = collections.defaultdict(int)
for (i, j) in d.keys():
	for (x, y) in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
		if (x, y) not in d:
			res[d[i, j]] = [x, y]
			deq.append((x, y, i, j))
while deq:
	(i, j, x, y) = deq.popleft()
	for (k, v) in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
		if (k, v) in d and res[d[k, v]] == [-1, -1]:
			res[d[k, v]] = [i, j]
			deq.append((i, j, k, v))
for (i, j) in res:
	print(*[i, j])