不含 $\epsilon$-转移的非确定性有限自动机是一个有向图，其节点称为状态，边称为转移。每个转移都有一个分配的标签，在本题中，该标签始终为 0 或 1。恰好有一个状态是起始状态，状态的某个子集（可能包含起始状态）称为终止状态。

一个单词是标签的序列，在本题中即由 0 和 1 组成的序列。如果存在一条从起始状态到某个终止状态的路径，使得该路径上的标签序列恰好构成该单词，则称该自动机接受给定的单词。

给定一个长度为 $n$ 的单词，请找出一个不含 $\epsilon$-转移的非确定性有限自动机，其状态数不超过 $\lfloor \frac{n}{2} \rfloor + 1$，使得它接受给定的单词，但不接受任何其他长度为 $n$ 的单词。$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

输入格式

输入文件的第一行包含测试用例的数量 $t$。接下来的 $t$ 行，每行包含一个由 0 和 1 组成的单词。每个单词的长度至少为 1，至多为 100，单个输入文件中所有单词的总长度不超过 $10^5$。输入文件中的所有单词各不相同。

输出格式

对于每个单词，输出一个自动机的描述，该自动机接受给定的单词但不接受任何其他相同长度的单词；如果不存在这样的自动机，则输出一行 -1。

自动机描述的第一行应包含四个数字 $k, m, s$ 和 $t$，分别表示状态数、转移数、起始状态的标识符以及终止状态的数量。状态的标识符从 1 到 $k$。第二行应包含 $t$ 个不同的终止状态标识符。接下来的 $m$ 行应包含转移，每个转移由三个数字描述：源状态标识符、目标状态标识符和标签。不应有重复的转移（但可能存在两个仅标签不同的转移）。$k$ 必须不超过 $\lfloor \frac{\text{len(word)}}{2} \rfloor + 1$。

每行中的所有数字应以空格分隔。

样例

输入 1

2
0
01

输出 1

1 1 1 1
1
1 1 0
2 2 1 1
2
1 2 0
2 2 1