Bitek 开发了一种新的二进制序列加密方案，长度为 $n$。给定一个序列 $a_1, a_2, \dots, a_n$，我们构造一个包含 $n+1$ 个整数的序列 $b_1, b_2, \dots, b_{n+1}$，其中元素 $b_i$ 定义为原始序列中位置 $1, 2, \dots, i-1$ 的 $1$ 的个数减去位置 $i, i+1, \dots, n$ 的 $1$ 的个数。

Bitek 想要向 Bajtek 证明他的方案是抗错误的。为此，他没有发送原始序列 $b_1, b_2, \dots, b_{n+1}$，而是发送了一个序列 $c_1, c_2, \dots, c_{n+1}$，该序列满足 $|b_1 - c_1| + |b_2 - c_2| + \dots + |b_{n+1} - c_{n+1}| \le k$，其中 $k$ 是一个参数。Bajtek 现在想知道收到的序列 $c_1, c_2, \dots, c_{n+1}$ 是否合法，即是否存在一个序列 $a_1, a_2, \dots, a_n$ 可以通过上述方式得到该序列。

你的任务是找到任意一个满足条件的序列 $a_1, a_2, \dots, a_n$，或者判断这样的序列不存在。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 200\,000, 0 \le k \le 200$)。 第二行包含 $n+1$ 个整数，表示序列 $c_i$ 的项 ($-10^9 \le c_i \le 10^9$)。

输出格式

如果不存在满足条件的序列 $a_1, \dots, a_n$，输出一行 NIE。 否则，第一行输出 TAK。第二行输出序列 $a_1, a_2, \dots, a_n$，数字之间用空格分隔。这应当是一个（任意）二进制序列，通过题目描述的方式可以得到序列 $c_1, c_2, \dots, c_{n+1}$。

样例

样例输入 1

4 1
-2 0 0 0 1

样例输出 1

TAK
1 0 0 1

样例输入 2

4 0
-2 -1 0 0 1

样例输出 2

NIE

子任务

测试集分为以下子任务。每个子任务的测试数据由一组或多组独立的测试用例组成。