Colored necklace

Limits: 3 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk wants to give Marichka a necklace. But of course, the gift will be special only if Zenyk makes it with his own hands.

The boy wants the necklace to have \(n\) beads arranged in a row. The distance between each pair of adjacent beads must be 1 cm. Of course, the beads must be colored.

Also, Zenyk knows that Marichka will be happy if for the \(i\)-th bead, the nearest bead of the same color is at a distance of exactly \(d_i\) cm. If there shouldn’t be any more beads of the same color, then \(d_i=0\). True, Marichka is not interested in all the beads. For some beads \(d_i=-1\), which means it does not matter where the nearest bead of the same color is located. Help Zenyk check if he can make such a necklace.

Input

The first line contains a single integer \(n\) — the number of beads in the necklace.

The second line contains \(n\) integers \(d_i\). If \(d_i=0\), there must be no more beads of the same color. If \(d_i=-1\), it does not matter whether a bead of the same color exists and at what distance it is.

Output

Output TAK if such a necklace that Marichka likes exists, and NI if it does not.

If the necklace exists, output in the second line \(n\) integers \(C_i\) — the colors of the corresponding beads. All colors must be integers from 1 to \(10^9\). If there are several possible correct answers, output any of them.

Constraints

\(2 \le n \le 3 \cdot 10^5\),

\(-1 \le d_i \le n - 1\).

Samples