Space Pirate

In a distant galaxy there are $N$ stars, numbered $1$ through $N$. Every star holds one teleporter, and each teleporter has a single fixed destination star. A teleporter carries you in that one direction only.

The galactic art museum runs its exhibitions on these stars. The current exhibition is on star $1$. The next exhibition will be held on the star you reach by using teleporters $K$ times starting from star $1$.

The space police learned that a space pirate is after the museum collection. The pirate breaks into the teleporter system and overwrites the destination of the teleporter on star $a$ so that it points to star $b$. The pirate breaks into exactly one star, but the police could not work out the values of $a$ and $b$.

To predict where the next exhibition lands, the police want to know, for each $i$, how many pairs $(a, b)$ put the next exhibition on star $i$.

Given the destination of every teleporter, compute that count for each $i$.

The first line contains $N$ and $K$, separated by a space. The galaxy holds $N$ stars, and the next exhibition is held on the star reached by using teleporters $K$ times from star $1$.

The $i$-th of the next $N$ lines contains an integer $A_i$, meaning that the teleporter on star $i$ currently sends you to star $A_i$.

Every input satisfies the following conditions.

• $1 \le N \le 2\,000$
• $N \le K \le 10^{18}$
• $1 \le A_i \le N$

Print $N$ lines. The $i$-th line contains the number of pairs $(a, b)$ that put the next exhibition on star $i$.

The destination of the teleporter on star $i$ may be star $i$ itself. In that case you stay on star $i$ no matter how many times you use that teleporter.

Even when the teleporter on star $a$ already points to star $b$, the pirate may still overwrite its destination with star $b$. The destination then stays star $b$ and nothing changes. Such pairs $(a, b)$ are still counted.

Pairs with $a = b$ are counted too. All $N^2$ pairs with $1 \le a \le N$ and $1 \le b \le N$ are considered, so the $N$ printed numbers always add up to $N^2$.