Nearest Foreign Contestant

In this problem, there are N contestants (indexed from 1 to N) participating in the IOI hosted by JOI Country. Each contestant i (where \(1 \le i \le N\)) is from a country represented by an integer \(C_i\) (\(1\le C_i \le 10^9\)). It is guaranteed that the nationalities are not all identical, i.e. there exists at least one pair \(i \neq j\) such that \(C_i \neq C_j\).

The contestants are seated along a line with contestant i sitting at position \(X_i\). The seat distance between contestants i and j is defined as \(|X_i - X_j|\). Each contestant wishes to know the distance to the nearest contestant from a different country.

Your task is to compute, for each contestant i (\(1 \le i \le N\)), the minimum value of \(|X_i - X_j|\) among all contestants j such that \(C_i \neq C_j\).

inputFormat

The input begins with an integer N, the number of contestants. Each of the following N lines contains two integers: C_i and X_i, representing the country code and the seat position of the i-th contestant respectively.

You can assume that:

• \(1 \le N\)
• \(1 \le C_i \le 10^9\) for each contestant \(i\)
• The nationalities are not all identical.

outputFormat

Output N lines. The i-th line should contain a single integer representing the minimum seat distance between contestant i and any contestant from a different country.

sample

3
1 1
2 3
1 6

2
2
3