Bajtek 决定认真准备今年的算法竞赛。为此，他在 BitForces 门户网站上注册了一个账号，该网站定期举办编程竞赛。

Bajtek 发现该门户网站使用一种排名积分系统（即 rating），通过该系统，他可以追踪自己相对于其他选手的进步情况。选手的排名是一个整数（可能是负数）。在注册账号后，Bajtek 的初始积分为 0，他参加的每场编程竞赛都会使他的积分增加或减少一个整数。此外，门户网站还提供了每场比赛后的积分变化历史记录。兴奋的 Bajtek 开始分析这些数据，并在纸上依次记下了 $n$ 个数字： 在单场比赛中发生的最大积分增长； 在连续两场比赛中发生的最大累计积分增长； 在连续三场比赛中发生的最大累计积分增长； 以此类推，最后他记下了在连续 $n$ 场比赛中发生的最大累计积分增长。

几天后，Bajtek 想回忆起积分变化的序列。然而，BitForces 门户网站恰好出现了技术故障。你能帮助 Bajtek 恢复出任何一个长度至少为 $n$ 的、符合他纸上记录数据的积分变化序列吗？

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 300$)，表示 Bajtek 在纸上记录的信息数量。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^6 \le a_i \le 10^6$)，即 Bajtek 纸上记录的数字。对于每个 $1 \le j \le n$，在连续 $j$ 场比赛中发生的最大累计积分增长恰好等于 $a_j$。

输出格式

如果存在满足题目描述中所有条件的积分变化序列，则在输出的第一行打印单词 TAK。接着给出该序列：在输出的第二行打印找到的序列长度 $k$ ($n \le k \le 100\,000$)，在第三行打印该序列的连续元素 $b_1, b_2, \dots, b_k$ ($-10^{13} \le b_i \le 10^{13}$)。如果存在多个正确解，输出其中任意一个即可。

如果不存在这样的积分变化序列，则在输出的第一行打印 NIE。

可以证明，如果对于满足给定限制的输入数据存在任何合法的积分变化序列，则也存在满足上述限制的合法积分变化序列。

样例

输入格式 1

4
3 4 5 -1

输出格式 1

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

说明 1

以下展示了积分变化序列，并标注了在连续一、二、三和四场比赛中的最大积分增长：

2 2 -7 0 3 -7 3 -1 3

输入格式 2

10
3 1 4 1 5 9 2 6 5 3

输出格式 2

NIE