Merging a Sequence and a Permutation

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk has a sequence \(a\) of \(n\) integers, each from 1 to \(n\) inclusive. The sequence may contain duplicate elements.

Marichka does not have her own sequence yet, but she wants to come up with one. As her sequence \(b\), she can choose any permutation of distinct integers from 1 to \(n\) inclusive.

After that, they will form a sequence \(c\) by performing \(2 \cdot n\) of the following steps: choose the leftmost element from \(a\) (if \(a\) is not empty) or from \(b\) (if \(b\) is not empty) and move it to the end of the sequence \(c\). Note that initially the sequence \(c\) is empty, and after the process finishes it will contain exactly \(2 \cdot n\) elements. At each step, they can independently decide which sequence to choose the element from.

Your task is to find such a sequence \(c\) that they can obtain, which has no equal adjacent elements, or report that no such sequence exists.

Input

The first line contains a single integer \(n\) — the size of the sequence \(a\) and the permutation \(b\).

The second line contains \(n\) integers separated by spaces — the sequence \(a\).

Output

In the first line, output Tak if the desired sequence exists, or Ni otherwise.

If the sequence exists, in the second line output \(2 \cdot n\) integers separated by spaces — the desired sequence \(c\). If there are multiple correct answers, output any of them.

Constraints

\(1 \le n \le 10^5\),

\(1 \le a_i \le n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 3 2 2	Tak 3 1 3 2 4 2 3 2

Input (stdin) сopy	Output (stdout) сopy
3 2 2 2	Ni

Input (stdin) сopy	Output (stdout) сopy
4 1 2 4 3	Tak 1 2 4 3 1 2 3 4

Notes

In the first example, Zenyk’s sequence is [3, 3, 2, 2]. Marichka can choose the permutation [1, 4, 3, 2]. After merging the sequences, they can obtain the sequence [3 1 3 2 4 2 3 2], in which no two adjacent elements are equal.