Bitek has developed a new encryption scheme for binary sequences of length $n$. Given such a sequence $a_1, a_2, \dots, a_n$, we create a sequence of $n+1$ integers $b_1, b_2, \dots, b_{n+1}$, where the element $b_i$ is the number of ones at positions $1, 2, \dots, i-1$ minus the number of ones at positions $i, i+1, \dots, n$ in the original sequence.

Bitek wants to convince Bajtek that his scheme is error-resistant. To do this, instead of sending him the sequence $b_1, b_2, \dots, b_{n+1}$, he sent him a sequence $c_1, c_2, \dots, c_{n+1}$ with the property that $|b_1 - c_1| + |b_2 - c_2| + \dots + |b_{n+1} - c_{n+1}| \le k$, where $k$ is a certain parameter. Bajtek is now wondering whether the received sequence $c_1, c_2, \dots, c_{n+1}$ is valid, meaning whether it can be obtained in the manner described above.

Your task is to find any sequence $a_1, a_2, \dots, a_n$ from which the given sequence $c_1, c_2, \dots, c_{n+1}$ can be obtained in the manner described above, or to state that no such sequence exists.

Input

The first line of input contains two integers $n$ and $k$ ($1 \le n \le 200\,000$, $0 \le k \le 200$). The second line contains $n+1$ integers representing the consecutive terms of the sequence $c_i$ ($-10^9 \le c_i \le 10^9$).

Output

If the sought sequence $a_1, \dots, a_n$ does not exist, output the single word NIE. Otherwise, in the first line of output, print the word TAK. In the second line of output, print the sequence of $n$ numbers $a_1, a_2, \dots, a_n$ separated by single spaces. This should be (any) binary sequence from which the sequence $c_1, c_2, \dots, c_{n+1}$ can be obtained in the manner described in the problem statement.

Examples

Input 1

4 1
-2 0 0 0 1

Output 1

TAK
1 0 0 1

Input 2

4 0
-2 -1 0 0 1

Output 2

NIE

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.