题目描述

题目译自XXII Olimpiada Informatyczna — II etap Trzy Wieże

Bajtazar 经营着一间化学实验室，存放着 $n$ 种编号从 $1$ 到 $n$ 的化学物质，第 $i$ 种物质有 $a_i$ 升。

Bajtazar 新购置了 $n$ 个容器，计划将所有物质分配其中。每个容器容量为 $k$ 升，最多可存放两种物质：要么一种物质最多 $k$ 升，要么两种物质总量不超过 $k$ 升。每种物质可任意分割，分配到任意多个容器。你的任务是帮助 Bajtazar 设计分配方案，或判断是否无法分配。

输入格式

第一行包含两个整数 $n$, $k$ $(1 \leq n \leq 1000000$, $1 \leq k \leq 10^{12})$，分别表示物质和容器数量，以及每个容器的容量（单位：升）。

接下来的 $n$ 行，第 $i$ 行包含一个整数 $a_i$ $(1 \leq a_i \leq 10^{12})$，表示第 $i$ 种物质的量（单位：升）。

输出格式

第一行输出 TAK 或 NIE，表示是否可按条件分配物质。

若为 TAK，接下来 $n$ 行描述分配方案。第 $i$ 行描述第 $i$ 个容器的内容：以整数 $m_i$ $(0 \leq m_i \leq 2)$ 开头，表示存放的物质份数，后跟 $m_i$ 对整数，每对包含物质编号和该物质的升数。

若 $m_i = 2$，两份物质可相同或不同，允许存放 $0$ 升（此时可用更小的 $m_i$ 等价表示）。

样例

输入：

5 6
1
11
3
4
2

输出：

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

在第一个容器中，我们放入全部编号为 $4$ 的物质（$4$ 升）和 $2$ 升的编号为 $2$ 的物质，完全填满容器。在第二个容器中，我们放入全部编号为 $5$ 的物质（$2$ 升）和 $3$ 升的编号为 $2$ 的物质，留有一些剩余空间。第三个容器装入编号为 $2$ 的物质的剩余量（$6$ 升）。第四个容器保持空置。在第五个容器中，我们放入编号为 $1$ 和 $3$ 的物质。前页的图示展示了这种分配方式。左侧为物质的原始体积（以升为单位），右侧为它们在容器中的分配情况。

附加样例

• $n=4$, $k=30$，$a_1, a_2, a_3, a_4 = 29, 29, 30, 31$，答案为 TAK。
• $n=100$, $k=100$，$a_1 = 9900$，$a_i = 1$ 对于 $i \neq 1$，答案为 TAK。
• $n=1000000$, $k=10^{10}+1$，$a_i = 10^{10}+1-i$ 对于 $i=1, 2, \ldots, n$，答案为 TAK。

数据范围与提示

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