在 DoubleDog 和SinglePig 所在的宇宙中，物理法则与我们并不相同。在年复一年的宅化过程中，SinglePig 开发出了简单的 pig 计算机，DoubleDog 通过揣摩其变化，观察出其数学模型如下：

这些 pig 计算机有且仅有一个长为 $n(n\ge 3)$ 的布尔数组 $a$ （下标从 $0$ 开始），操作者可以为计算机写一个程序，程序即为一个固定长度的操作序列，每个操作形如：从 $a$ 中选择三个不同的位置 $i,j,k$ ，对他们执行一个门操作 $g$ ，其中 $g$ 是一个输入三个布尔值且输出三个布尔值的一一映射（即对于不同的两组输入， $g$ 产生不同的两组输出）。

DoubleDog 也想使用 pig 计算机来进行加法运算，但是苦于没有 SinglePig 们提供的程序，于是只好拜托你。如果我们视数组 $a$ 的前 $l$ 位为一个二进制数的话，其数值为 $\sum _{i=0}^{l-1}{a}_i{2}^i$ 。现在 DoubleDog 想实现一个程序，完成对数组 $a$ 的前 $l$ 位所表示的二进制数进行模 $2^l$ 的意义下加一个常数 $c$ 的操作。你需要对 DoubleDog 提供的常数 $c$ 设计出一个 pig 计算机上的程序。

根据测试点的不同，数组 $a$ 的后 $n-l$ 位中的初值和输出值为不同类型的值。对于每个测试点，你都需要提供一个给定格式的长度不超过 $m$ 的程序。有数个测试数据作为输入，如果你的程序能通过该测试点下的所有测试数据，则你通过此测试点。

输入格式

第一行包括一个正整数，表示子任务编号。

第二行包括三个正整数 $n,m,l$，表示数组的长度，你的输出的最多行数和数字的长度。

接下来一行一个长度为 $l$ 的 01 字符串，从低到高表示 $c$ 的每一位。

输出格式

输出第一行包含一个数 $L$，表示你的程序的行数，你必须保证 $L\le m$ 。

接下来共输出 $L$ 行，每行四个整数，前三个为操作位 $i,j,k$，你必须保证 $i,j,k$ 互不相同。第四个整数由一个长度 $24$ 的 01 串表示，每三位表示真值表中一个输入的对应输出。

给定一个输入三个布尔值 $a,b,c$ 且输出三个布尔值 $x,y,z$ 的门 gate，我们可以通过以下函数得到该门所对应的输出：

void gate(bool a, bool b, bool c, bool &x, bool &y, bool &z);
string gate_str(){
    string res = "";
    for (int w = 0; w < 8; ++w) {
        bool a = (w & 4) > 0;
        bool b = (w & 2) > 0;
        bool c = (w & 1) > 0;
        bool x, y, z;
        gate(a, b, c, x, y, z);
        res += char(x) + '0';
        res += char(y) + '0';
        res += char(z) + '0';
    }
    return res;
}

样例一

input

0
10 50000 1
1

output

1
0 1 2 100101110111000001010011

explanation

对于任意的 $a$，该程序都会将 $a_0$ 取反 (0 变 1, 1 变 0)。

限制与约定

对于 $100\mathrm{\%}$ 的数据，$l=100,c<2^l$ 。

在下发文件中我们下发了模拟器的源代码。

模拟器从 in.txt 中读入一个数 $n$ 和一个长度为 $n$ 的数组 $a$ 表示输入，从 out.txt 中读入你的程序，向 ans.txt 输出最终的 $a$ 数组。

时间限制：$\mathtt{\text{1s}}$

空间限制：$\mathtt{\text{512MB}}$

下载

样例数据及模拟器下载