题目描述

题目译自 PA 2020 Runda 1 Punkty rankingowe。

Bytie 决定认真准备今年的 PA。为了训练，他创建了一个 BitForces 账号，BitForces 是一个定期举办编程竞赛的平台。

Bytie 知道这个平台使用一种积分系统（也称为 rating），这个系统会让他知道自己的进步，也可以将自己的成绩与其他选手比较。选手的 rating 是一个整数（可能为负数）。在账号创建后，Bytie 的 rating 是 $0$，参加每场比赛后，他的 rating 都会加或减某一个整数。此外，在每场比赛后的 rating 变化历史是可以在平台上看到的。兴奋的 Bytie 开始分析这些数据。他在纸上写下了 $n$ 个连续的数字：

• 在一场比赛之后的最大 rating 上升；
• 在连续两场比赛之后的 rating 上升之和的最大值；
• 在连续三场比赛之后的 rating 上升之和的最大值；
• 以此类推，直到他写到在连续 $n$ 场比赛之后的 rating 上升之和的最大值；

几天后 Bytie 想要回想起 rating 变化的序列。然而，此时 BitForces 正出现技术问题。请帮助 Bytie 还原一个合法的 rating 变化序列，使其长度至少为 $n$ 并且符合写在纸上的数据。

输入格式

输入第一行包含一个整数 $n\ (1\le n\le 300)$，表示写在纸上的数字个数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (-10^6\le a_i\le 10^6)$。对于每个 $1\le j\le n$，连续 $j$ 场比赛的 rating 最大增幅恰好为 $a_j$。

输出格式

如果存在一个 rating 变化序列满足所有题目描述中的条件，输出一行 TAK。之后输出一行一个整数 $k\ (n\le k\le 10^5)$。第三行输出找到的 rating 变化序列 $b_1,b_2,\ldots,b_k\ (-10^{13}\le b_k\le 10^{13})$。如果有多种答案，输出任意一种均可。

如果不存在这样的变化序列，输出一行 NIE 即可。

可以证明对于输入如果存在一个 rating 变化序列，那么一定存在一个满足以上限制的序列。

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