Bajtek has decided to prepare diligently for this year's Algorithmic Contests. To this end, he created an account on the BitForces portal, where programming contests are held regularly.

Bajtek realized that the portal uses a ranking point system (so-called rating), which allows him to track his progress compared to the achievements of other competitors. A competitor's ranking is an integer (possibly negative). Immediately after creating the account, Bajtek's ranking was 0, and each programming contest he participated in increased or decreased his ranking by a certain integer. Moreover, the portal provides the entire history of ranking changes after each contest. Excited, Bajtek began analyzing this data. He wrote down $n$ numbers on a piece of paper in sequence: the maximum ranking increase that occurred in a single contest; the maximum total ranking increase in two consecutive contests; the maximum total ranking increase in three consecutive contests; and so on, until he finally wrote down the maximum total ranking increase in $n$ consecutive contests.

A few days later, Bajtek wanted to recall the sequence of ranking changes. However, it turned out that the BitForces portal was having technical problems. Can you help Bajtek and recover any valid sequence of ranking changes of length at least $n$ that is consistent with the data written on the paper?

Input

The first line of input contains a single integer $n$ ($1 \le n \le 300$) corresponding to the number of pieces of information written down by Bajtek. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^6 \le a_i \le 10^6$) found on Bajtek's paper. For each $1 \le j \le n$, the maximum total ranking increase that occurred over $j$ consecutive contests is, according to Bajtek, exactly $a_j$.

Output

If there exists a sequence of ranking changes satisfying all the conditions described in the problem, print the word TAK in the first line of the output. Then, provide an example sequence of changes. In the second line of the output, print the length of the found sequence $k$ ($n \le k \le 100\,000$), and in the third line – the consecutive elements of this sequence $b_1, b_2, \dots, b_k$ ($-10^{13} \le b_i \le 10^{13}$). If there are multiple valid solutions, print any one of them.

If, on the other hand, the given sequence of changes does not exist, print NIE in the first and only line of the output.

It can be proven that if a valid sequence of changes exists for the given input satisfying the constraints, then there also exists a valid sequence of changes satisfying the above constraints.

Examples

Input 1

4
3 4 5 -1

Output 1

TAK
9
2 2 -7 0 3 -7 3 -1 3

Note 1

Explanation of the first example: Below is the sequence of changes with the maximum ranking increases in one, two, three, and four consecutive contests marked:

2 2 −7 0 3 −7 3 −1 3 +4 +3 +5 −1

Input 2

10
3 1 4 1 5 9 2 6 5 3

Output 2

NIE