题目描述

题目译自 PA 2025 Runda próbna Zbiory 2

在这道题中，我们考虑一个包含 $n+m$ 个集合的序列，这些集合都是 $\{1, \ldots, n\}$ 的子集。前 $n$ 个集合 $A_{1}, \ldots, A_{n}$ 的定义如下：对于 $1 \leq i \leq n$，数字 $i$ 属于集合 $A_{j}$ 当且仅当 $i$ 能被 $j$ 整除。

例如，当 $n=7$ 时，集合依次为：

• $A_{1}=\{1,2,3,4,5,6,7\}$
• $A_{2}=\{2,4,6\}$
• $A_{3}=\{3,6\}$
• $A_{4}=\{4\}$
• $A_{5}=\{5\}$
• $A_{6}=\{6\}$
• $A_{7}=\{7\}$

接下来的 $m$ 个集合 $A_{n+1}, A_{n+2}, \ldots, A_{n+m}$ 通过对已有集合进行并集、交集或补集运算生成：

• 并集 $A_{i} \cup A_{j}$：包含所有属于 $A_{i}$ 或 $A_{j}$ 的数字；
• 交集 $A_{i} \cap A_{j}$：包含所有同时属于 $A_{i}$ 和 $A_{j}$ 的数字；
• 补集 $A_{i}^{\prime}$：包含 $\{1, \ldots, n\}$ 中不属于 $A_{i}$ 的所有数字。

例如，一组可能的运算序列可能是：

• $A_{8}=A_{5} \cup A_{7}=\{5,7\}$
• $A_{9}=A_{2} \cap A_{3}=\{6\}$
• $A_{10}=A_{8}^{\prime}=\{1,2,3,4,6\}$
• $A_{11}=A_{10} \cap A_{8}=\{\}$
• $A_{12}=A_{3}^{\prime}=\{1,2,4,5,7\}$
• $A_{13}=A_{12} \cup A_{12}=\{1,2,4,5,7\}$
• $A_{14}=A_{10} \cap A_{13}=\{1,2,4\}$
• $A_{15}=A_{9} \cup A_{14}=\{1,2,4,6\}$

给定 $n$ 和目标集合 $B$，你的任务是确定一个操作次数 $m$ $(0 \leq m \leq 100000)$ 以及 $m$ 个运算步骤，使得最终得到的集合 $A_{n+m}$ 等于 $B$。可以证明，在任务限制下，任意 $\{1, \ldots, n\}$ 的子集都可通过不超过 $m$ 的操作构造出来。

输入格式

输入的第一行包含两个整数 $n, s$ $(1 \leq n \leq 50000, 1 \leq s \leq n)$，分别表示初始集合数量和目标集合 $B$ 的大小。第二行包含 $s$ 个递增的整数 $b_{1}, b_{2}, \ldots, b_{s}$ $(1 \leq b_{1} < b_{2} < \ldots < b_{s} \leq n)$，表示集合 $B$ 的元素。

输出格式

输出的第一行包含一个整数 $m$ $(0 \leq m \leq 100000)$，表示操作次数。接下来的 $m$ 行描述每次操作，每行对应生成集合 $A_{n+i}$ 的方式，格式为以下三种之一：

• 1 x y：表示并集 $A_{n+i}=A_{x} \cup A_{y}$；
• 2 x y：表示交集 $A_{n+i}=A_{x} \cap A_{y}$；
• 3 x：表示补集 $A_{n+i}=A_{x}^{\prime}$。

要求 $A_{n+m}=B$，且每次操作的 $x, y$ 必须满足 $1 \leq x, y < n+i$（仅引用之前的集合）。

7 4
1 2 4 6

3 1
3

第一个样例对应题目描述中的运算序列。

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

0

第二个样例不需要执行任何操作，因为 $A_n = B$。