题目描述

题目译自 XXXII Olimpiada Informatyczna – III etap Szum

Bitek 发明了一种新颖的二进制序列加密方案，专门处理长度为 $n$ 的二进制序列 $a_1, a_2, \ldots, a_n$。他将序列转化为一个长度为 $n+1$ 的整数序列 $b_1, b_2, \ldots, b_{n+1}$，其中 $b_i$ 表示原序列中位置 $1$ 到 $i-1$ 的 $1$ 的个数，减去位置 $i$ 到 $n$ 的 $1$ 的个数。

为了向好友 Bajtek 证明该方案的容错能力，Bitek 并未直接发送序列 $b_1, b_2, \ldots, b_{n+1}$，而是发送了一个稍有偏差的序列 $c_1, c_2, \ldots, c_{n+1}$，满足 $\left|b_1 - c_1\right| + \left|b_2 - c_2\right| + \ldots + \left|b_{n+1} - c_{n+1}\right| \leq k$，其中 $k$ 是一个容错参数。Bajtek 现在需要验证这个序列 $c_1, c_2, \ldots, c_{n+1}$ 是否有效，即是否能由某个二进制序列 $a_1, a_2, \ldots, a_n$ 通过上述方式生成。

你的任务是找到一个二进制序列 $a_1, a_2, \ldots, a_n$，能够生成符合条件的序列 $c_1, c_2, \ldots, c_{n+1}$，或者明确指出这样的序列不存在。

输入格式

第一行包含两个整数 $n, k$ $(1 \leq n \leq 200000, 0 \leq k \leq 200)$，分别表示二进制序列长度和容错参数。

第二行包含 $n+1$ 个整数 $c_i$ $(-10^9 \leq c_i \leq 10^9)$，表示接收到的序列。

输出格式

若不存在满足条件的二进制序列 $a_1, \ldots, a_n$，输出 NIE。

否则，第一行输出 TAK，第二行输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$，以空格分隔，表示一个符合条件的二进制序列。若存在多种解，输出任意一种。

4 1
-2 0 0 0 1

TAK
1 0 0 1

4 0
-2 -1 0 0 1

NIE

附加样例

1. $n=200000, k=200$，对于奇数 $i$，$c_i = -100001 + i$，对于偶数 $i$，$c_i = -100000 + i$。

数据范围与提示

详细子任务附加限制及分值如下表所示。