题目描述

定义一种三维图形 corner：它由四个大小相同的立方体组成，其中一个立方体分别与另外三个立方体共面相邻，并且四个立方体恰好有一个公共点，这个公共点是每个立方体的一个顶点。

每个 corner 有两个属性：

• 颜色；
• 大小。若组成它的立方体边长为 $2^j$，则称其大小指数为 $j$。

现在有 $c$ 种颜色。对于每种颜色 $i$ 和每个大小指数 $j$，给出可用的 corner 数量 $a_{i,j}$。

你需要用这些小 corner 拼成一个大小为 $2^k$ 的大 corner，并使得所使用的不同颜色数量最少。

一个大小为 $2^j$ 的 corner 可以恰好分解成 $8$ 个大小为 $2^{j-1}$ 的 corner，因此不同大小的零件可以递归组合。

输入格式

第一行两个整数 $c,k$，满足 $1\le c,k\le1000$。

接下来 $c$ 行，每行 $k$ 个整数。第 $i$ 行第 $j+1$ 个整数为 $a_{i,j}$，表示颜色 $i$、大小指数 $j$ 的 corner 数量，其中：

$0\le a_{i,j}\le1000,\quad 0\le j<k$。

目标大 corner 的大小为 $2^k$。

输出格式

若无法构造，输出：

NO SOLUTION

否则第一行输出整数 $n$，表示实际使用了多少种“颜色 + 大小指数”的零件类型。

接下来 $n$ 行，每行三个整数 $a,b,c$：

• $a$：颜色编号；
• $b$：大小指数；
• $c$：使用这种零件的数量。

同一种类型在输出中至多出现一次。必须满足输入给出的数量限制，并且构造使用的不同颜色数最少。若有多个最优方案，输出任意一个。

样例 1

1 1
8

1
1 0 8

样例 2

2 2
1 7
7 0

3
1 1 7
1 0 1
2 0 7