题目背景

PA 2025 trial round t2.

请注意本题非同寻常的时空限制。

题目描述

问题。

给定正整数 $n$ 和非负整数 $m$。定义全集 $U=\{1,2,\ldots,n\}$。

构造 $(n+m)$ 个集合 $A_1,A_2,\ldots,A_{n+m}$：

1. 对于 $1\le i\le n$，$A_i$ 里的元素为 $U$ 中 $i$ 的倍数。
2. 对于 $n+1\le i\le m$，给定参数 $op_i$：

• 当 $op_i=1$ 时，给定参数 $x,y$（$x,y\lt n+i$），则 $A_{i} =A_x\cup A_y$；
• 当 $op_i=2$ 时，给定参数 $x,y$（$x,y\lt n+i$），则 $A_{i}=A_x\cap A_y$；
• 当 $op_i=3$ 时，给定参数 $x$（$x\lt n+i$），则 $A_{i}=U\backslash A_x$（即 $A_i=\{j:j\in U,j\not\in A_x\}$）。

定义问题的答案为 $A_{n+m}$。

给定正整数 $n$ 和目标集合 $B\subseteq \{1,2,\ldots,n\}$。构造非负整数 $m$ 和一组对应的参数，使得上述问题的答案为 $B$。

你需要保证 $0\le m\le 10^5$。可以证明本题一定有解。

输入格式

第一行，两个正整数 $n,k$，其中 $|B|=k$。

第二行，$k$ 个正整数 $B_1,B_2,\ldots,B_k$，描述 $B$ 中的元素。

输出格式

输出 $(m+1)$ 行：

第一行，一个非负整数 $m$。

接下来 $m$ 行，第 $i$ 行两个或三个正整数（格式见上），描述集合 $A_{n+i}$ 的生成方式。

你需要保证 $0\le m\le 10^5$，且格式符合【题目描述】中的限制。

7 4
1 2 4 6

8
1 5 7
2 2 3
3 8
2 10 8
3 3
1 12 12
2 10 13
1 9 14

3 1
3

0

提示

• $1\le n\le 5\times 10^4$;
• $B\subseteq \{1,2,\ldots,n\}$。