Problem Description

This problem is translated from PA 2020 Round 1 Punkty rankingowe.

Bytie decided to seriously prepare for this year's PA. For training, he created a BitForces account. BitForces is a platform that regularly hosts programming contests.

Bytie knows that the platform uses a points system (also called rating). This system lets him see his progress and compare his results with other contestants. A contestant's rating is an integer (it may be negative). After creating the account, Bytie's rating is $0$. After each contest, his rating increases or decreases by some integer. Also, after each contest, the history of rating changes can be viewed on the platform. Excited, Bytie started analyzing this data. He wrote down $n$ consecutive numbers on paper:

• the maximum rating increase after one contest;
• the maximum value of the sum of rating increases over two consecutive contests;
• the maximum value of the sum of rating increases over three consecutive contests;
• and so on, until he wrote down the maximum value of the sum of rating increases over $n$ consecutive contests.

A few days later, Bytie wanted to recall the sequence of rating changes. However, BitForces is currently having technical problems. Help Bytie reconstruct a valid rating change sequence, with length at least $n$, that matches the data written on the paper.

Input Format

The first line contains an integer $n$, the number of values written on the paper.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$. For each $1\le j\le n$, the maximum total rating increase over $j$ consecutive contests is exactly $a_j$.

Output Format

If there exists a rating change sequence that satisfies all conditions in the statement, output one line TAK. Then output a line with one integer $k$. In the third line output the found rating change sequence $b_1,b_2,\ldots,b_k$. If there are multiple answers, output any one of them.

If no such change sequence exists, output one line NIE.

It can be proven that if a rating change sequence exists for the given input, then there must exist one that satisfies the limits above.

4
3 4 5 -1

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

10
3 1 4 1 5 9 2 6 5 3

NIE

Hint

Explanation of Sample 1

Below are the intervals where the rank increase is the largest for $1$, $2$, $3$, and $4$ consecutive contests.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 300$, $-10^6\le a_i\le 10^6$, $n\le k\le 10^5$, $-10^{13}\le b_k\le 10^{13}$.

Translated by ChatGPT 5