Bajtazar runs a chemical laboratory. He stores $n$ substances, numbered from $1$ to $n$, where the $i$-th substance has exactly $a_i$ bajtoliters.

Bajtazar has purchased $n$ new containers in which he wants to place all the substances he owns. Each container has a capacity of $k$ bajtoliters and can hold at most two substances. In other words, a container can hold at most $k$ bajtoliters of one substance, or any amount of one substance and any amount of another substance, provided that these amounts sum to at most $k$ bajtoliters. Each substance can be divided in any way among any number of containers. Help Bajtazar distribute the substances among the containers or determine that it is not possible.

Input

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 1\,000\,000$, $1 \le k \le 10^{12}$); the first is the number of substances and also the number of containers, and the second is the capacity of each container (in bajtoliters). The next $n$ lines describe the substances: the $i$-th of these contains an integer $a_i$ ($1 \le a_i \le 10^{12}$) describing the amount of the $i$-th substance in bajtoliters.

Output

In the first line of the output, print the word TAK or NIE as the answer to the question of whether it is possible to distribute the substances according to the problem conditions.

If the answer is TAK, you must also describe any way to distribute the substances among the containers such that each container holds at most two portions of substances with a total amount of at most $k$ bajtoliters. The next $n$ lines should describe such a distribution. The $i$-th of these lines should contain the description of the contents of the $i$-th container. The first number $m_i$ ($0 \le m_i \le 2$) denotes the number of portions of substances to be placed in the $i$-th container. This should be followed by $m_i$ pairs of integers; in each pair, the first number is the substance index, and the second is the number of bajtoliters of that substance to be placed in the $i$-th container.

If $m_i = 2$, the two given substances can be different or they can be two portions of the same substance. Furthermore, we allow placing $0$ bajtoliters of a substance in a container. (Although in both cases, one could just as well provide an answer with a smaller $m_i$).

Examples

Input 1

5 6
1
11
3
4
2

Output 1

TAK
2 4 4 2 2
2 5 2 2 3
1 2 6
0
2 1 1 3 3

Note

Explanation of the example: In the first container, we place the entire substance number 4 (4 bajtoliters) and 2 bajtoliters of substance number 2, completely filling the container. In the second container, we place the entire substance number 5 (2 bajtoliters) and 3 bajtoliters of substance number 2, leaving some free space. The third container is filled with the remaining amount of substance number 2 (6 bajtoliters). The fourth container is left empty. In the fifth container, we place substances number 1 and 3. The figure below illustrates this arrangement. On the left side, we have the original volumes of the substances (in bajtoliters), and on the right side, their arrangement in the containers.

Input 2

2 10
20
1

Output 2

NIE

Note

Explanation of the example: The substances do not fit in the containers: the very first substance would fill both containers, leaving no room for the second substance.