包含 K 理事长在内的 $N$ 名日本信息学奥林匹克委员会成员来到了一家中餐馆。

餐馆的餐桌是圆形的，有 $N$ 个等间距排列的座位。桌子中央有一个放置菜肴的转盘。$N$ 名委员坐在 $N$ 个座位上，以 K 理事长为 1 号，按逆时针方向依次编号为 $2, 3, \dots, N$。委员会点了 $N$ 种菜肴，每种各一份，并放置在转盘上。菜肴放置在委员面前，委员 $i$ ($1 \le i \le N$) 面前放置的是菜肴 $i$。除 K 理事长外，每位委员都决定好了一种想吃的菜肴，委员 $i$ ($2 \le i \le N$) 想吃的菜肴是 $A_i$。

转盘可以以 $(360/N)$ 度为单位，沿顺时针或逆时针方向旋转。 例如，将转盘逆时针旋转 1 个单位，K 理事长的面前会变为菜肴 $N$，委员 $i$ ($2 \le i \le N$) 的面前会变为菜肴 $i-1$。 某位委员要吃某道菜，必须转动转盘，使该菜肴移动到其面前。

由于 K 理事长在日本信息学奥林匹克委员会中备受尊敬，首先由 K 理事长转动转盘，使菜肴 $k$ ($1 \le k \le N$) 移动到其面前并食用。 在 K 理事长食用菜肴后，其他委员各自转动转盘，使自己想吃的菜肴移动到面前并食用。注意，除 K 理事长外，其他委员转动转盘的顺序可以是任意的。 此外，假设每种菜肴的量都充足，不会被吃完。

为了应对 K 理事长选择任何菜肴的情况，请针对每个 $k$，预先确定除 K 理事长外其他委员转动转盘的顺序和方式，使得所有人都能吃到菜，且转动转盘的总量最小。

任务

给定每位委员 $i$ ($2 \le i \le N$) 想吃的菜肴 $A_i$，对于 K 理事长吃的每种菜肴 $k$ ($1 \le k \le N$)，求出转动转盘的总量的最小值，单位为 $(360/N)$ 度。

输入格式

从标准输入读取以下内容： 第 1 行包含一个整数 $N$，表示日本信息学奥林匹克委员会的人数。 接下来 $N-1$ 行包含各委员想吃的菜肴信息。第 $i$ 行 ($2 \le i \le N$) 包含一个整数 $A_i$，表示委员 $i$ 想吃的菜肴是 $A_i$。

输出格式

输出共 $N$ 行。第 $k$ 行 ($1 \le k \le N$) 输出 K 理事长吃菜肴 $k$ 时，转动转盘总量的最小值。转动量以 $(360/N)$ 度为 1 个单位。

数据范围

• $2 \le N \le 100\,000$
• $1 \le A_i \le N$

子任务

• 对于 10% 的测试数据，满足 $N \le 10$。
• 对于 40% 的测试数据，满足 $N \le 1\,000$。

样例

输入 1

5
3
5
3
2
4

输出 1

4
4
5
6
4

在这种情况下，5 名委员在圆桌上的座位如图所示：

例如，考虑 $k=3$ 的情况（K 理事长吃菜肴 3），使转动总量最小的转动方式如下：

• K 理事长（委员 1）将转盘顺时针转动 2 个单位，吃掉菜肴 3。
• 委员 3 不转动转盘，吃掉菜肴 5。
• 委员 5 不转动转盘，吃掉菜肴 2。
• 委员 2 将转盘逆时针转动 1 个单位，吃掉菜肴 3。
• 委员 4 将转盘逆时针转动 2 个单位，吃掉菜肴 3。

此时，转动转盘的总量为 $2 + 1 + 2 = 5$ 个单位，因此在输出的第 3 行输出 5。