题目描述

小 Y 的朋友小 G 在天文观测站工作，她接收了很多珍贵的宇宙信号。

每段信号由 $n$ 个量子比特构成，编号为 $0,1,\dots ,n-1$，每个量子比特的值可能是 $0$ 或 $1$，不过这些量子比特的值无法被观测。

小 Y 购买了一种量子比特的操作装置，这种装置由 $m$（$m\ge n+2$）个比特构成，每个比特的值可能是 $0$ 或 $1$，记为 $a_0,a_1,\dots,a_{m-1}$。

装置中编号为 $0,1,\dots,n-1$ 的比特和宇宙信号中对应编号的量子比特的值相同，而编号为 $n,n+1,\dots,m-1$ 的比特的值无法被观测。

这个装置支持如下的指令：输入 $k\in\{1,2,3\}$，然后输入 $k$ 个 $[0,m-1]$ 中两两不同的整数 $p_1,p_2,\dots,p_k$，如果 $k=1$ 或者装置中 $a_{p_1},a_{p_2},\dots,a_{p_{k-1}}$ 的值都为 $1$，那么反转装置中 $a_{p_k}$ 的值（$0$ 变成 $1$，$1$ 变成 $0$），否则什么也不做。

现在小 G 想知道宇宙信号中的量子比特中是否有 $0$，如果是，那么小 Y 不应该修改装置中任何一个比特的值，否则小 Y 应该恰好反转编号为 $n$ 的比特的值，并且保持其他比特的值不变。

换句话说，最终需要满足 $a_n\gets a_n\oplus\left(\bigwedge_{i=0}^{n-1}a_i\right)$，并保证所有 $i\ne n$ 的 $a_i$ 均保持不变。

由于装置执行指令需要花费经费，因此小 Y 希望你设计一个指令序列，包含不超过 $q$ 条指令，机器依次执行这些指令后能够满足小 G 的要求。

你输出的指令序列必须对装置的每一种合法初始状态均满足上述要求，除特殊性质明确限制的比特外，所有无法观测的辅助比特初值都可能是 $0$ 或 $1$。

输入格式

从文件 signal.in 中读入数据。

输入的第一行包含四个整数 $n,m,q,c$，表示信号的量子比特数，装置的比特数，你的指令序列可以使用的指令数量的最大值，以及测试点所属子任务编号（样例中 $c=0$）。

输出格式

输出到文件 signal.out 中。

第一行一个整数 $s$，表示你的指令序列使用的指令数。

输出的第 $i+1$（$1\le i\le s$）行，表示指令序列中第 $i$ 条指令。

每条指令先输出一个整数 $k\in\{1,2,3\}$，然后输出 $k$ 个 $[0,m-1]$ 中两两不同的整数 $p_1,p_2,\dots,p_k$，含义如题所述。

样例 1 输入

3 5 25 0

样例 1 输出

4
3 0 1 4
3 2 4 3
3 0 1 4
3 2 4 3

样例 1 解释

枚举所有可能的初始情况即可验证。

样例 2

见选手目录下的 signal/signal2.in 与 signal/signal2.ans。

该样例满足子任务 $1$ 的约束条件。

样例 3

见选手目录下的 signal/signal3.in 与 signal/signal3.ans。

该样例满足子任务 $2$ 的约束条件。

样例 4

见选手目录下的 signal/signal4.in 与 signal/signal4.ans。

该样例满足子任务 $3$ 的约束条件。

样例 5

见选手目录下的 signal/signal5.in 与 signal/signal5.ans。

该样例满足子任务 $4$ 的约束条件。

样例 6

见选手目录下的 signal/signal6.in 与 signal/signal6.ans。

该样例满足子任务 $5$ 的约束条件。

样例 7

见选手目录下的 signal/signal7.in 与 signal/signal7.ans。

该样例满足子任务 $6$ 的约束条件。

样例 8

见选手目录下的 signal/signal8.in 与 signal/signal8.ans。

该样例满足子任务 $7$ 的约束条件。

样例 9

见选手目录下的 signal/signal9.in 与 signal/signal9.ans。

该样例满足子任务 $8$ 的约束条件。

校验器

为方便选手测试，我们下发了 signal/sample_checker.exe 文件，选手可以使用该程序校验自己的输出文件，但请注意它与最终评测时所使用的校验器并不完全一致。

使用方式为：

.\sample_checker.exe <inputfile> <outputfile> <answerfile>

三个参数依次表示输入文件、待校验的输出文件和标准答案文件。

由于本题的校验器不使用标准答案内容，因此第三个参数可以再次填写你的输出文件。

数据范围

对于所有测试数据，保证：$1 \leq n \leq 100$，$m\ge n+2$，$q\ge 8n$，$c\in\{1,2,3,4,5,6,7,8\}$。

子任务编号	$n$	$m$	$q$	特殊性质	分值
$1$	$\leq 20$	$=2n+2$	$=8n$	特殊性质 A	$20$
$2$	$\leq 50$	^		^	$10$
$3$	^			无特殊性质	$20$
$4$	$\leq 20$	$=n+2$	$=\max(8n,n^2)$	特殊性质 A	$10$
$5$	^	^	^	无特殊性质
$6$	$\leq 50$		$=28n$	^
$7$	$\leq 100$		$=8n$	特殊性质 A
$8$	^		^	无特殊性质

特殊性质 A：保证每次使用装置时均满足 $a_{n+1}=a_{n+2}=\cdots=a_{m-1}=0$。

本题开启所有合理的子任务依赖。