Projection in \( \mathbb{R}^3 \)

Given N three-dimensional points, your task is to find the nearest point for each one. The distance between any two points is calculated using the formula:

Input

You will be provided with the number of points, N (2 ≤ N ≤ 3·10^4), followed by N points. Each point is specified by three integer coordinates: x, y, and z, where each coordinate ranges from 0 to 10^9.

Output

For each point, output the index of its nearest neighboring point, with indices ranging from 1 to N.

Examples