The $N$ members of the Japanese Olympiad in Informatics committee, including Director K, have arrived at a Chinese restaurant.

The restaurant table is circular, with $N$ seats arranged at equal intervals. In the center, there is a rotating turntable on which dishes are placed. The $N$ members are seated in the $N$ seats, and the members are numbered $1, 2, \dots, N$ in counter-clockwise order, starting with Director K as $1$. The committee has ordered $N$ different dishes, one of each, and these dishes are placed on the turntable. The dishes are placed in front of the members, and the dish in front of member $i$ is dish $i$ ($1 \le i \le N$). Each member other than Director K has decided on one dish they want to eat, and the dish that member $i$ ($2 \le i \le N$) wants to eat is $A_i$.

The turntable can be rotated in either the clockwise or counter-clockwise direction in units of $(360/N)$ degrees. For example, if the turntable is rotated by $1$ unit counter-clockwise, dish $N$ will be in front of Director K, and dish $i-1$ will be in front of member $i$ ($2 \le i \le N$).

For a member to eat a certain dish, the turntable must be rotated so that the dish is in front of that member.

Since Director K is highly respected by the Japanese Olympiad in Informatics committee, Director K first rotates the turntable so that dish $k$ ($1 \le k \le N$) is in front of them and eats that dish.

After Director K has eaten their dish, the other members each rotate the turntable so that their desired dish is in front of them and eat it. Note that the order in which the members other than Director K rotate the turntable can be any order.

Also, assume that there is a sufficient amount of each dish, and they will not run out.

To ensure that everyone can eat their desired dish regardless of what Director K eats, and to minimize the total amount the turntable is rotated, we want to determine in advance the order and method for the members other than Director K to rotate the turntable for each $k$.

Task

Given the dish $A_i$ that each member $i$ ($2 \le i \le N$) wants to eat, for each dish $k$ ($1 \le k \le N$) that Director K eats, find the minimum total amount the turntable must be rotated, in units of $(360/N)$ degrees.

Constraints

• $2 \le N \le 100\,000$ (Number of members of the Japanese Olympiad in Informatics committee)
• $1 \le A_i \le N$ (Dish that member $i$ wants to eat)

Input

Read the following input from standard input:

• The first line contains an integer $N$, representing the number of members of the Japanese Olympiad in Informatics committee.
• The following $N-1$ lines provide information about the dish each member wants to eat. The $i$-th line ($2 \le i \le N$) contains an integer $A_i$, which represents that the dish member $i$ wants to eat is $A_i$.

Output

The output should consist of $N$ lines. On the $k$-th line ($1 \le k \le N$), output an integer representing the minimum total amount the turntable is rotated when Director K eats dish $k$. Note that the rotation amount is in units of $(360/N)$ degrees.

Subtasks

• For $10\%$ of the test data, $N \le 10$ is satisfied.
• For $40\%$ of the test data, $N \le 1\,000$ is satisfied.

Examples

Input 1

5
3
5
3
2

Output 1

4
4
5
6
4

Note

In this case, there are 5 members sitting at the round table as shown in the figure.

For example, considering the case $k = 3$ (where Director K eats dish 3), the way to rotate the turntable to minimize the total rotation amount is as follows:

• Director K (member 1) rotates the turntable 2 units clockwise and eats dish 3.
• Member 3 eats dish 5 without rotating the turntable.
• Member 5 eats dish 2 without rotating the turntable.
• Member 2 rotates the turntable 1 unit counter-clockwise and eats dish 3.
• Member 4 rotates the turntable 2 units counter-clockwise and eats dish 3.

At this time, the total amount the turntable is rotated is $2 + 1 + 2 = 5$ units, so 5 is output on the 3rd line of the output.

Figure 1. The 5 members sitting at the round table.