题目描述

小艾想要挑战分治乘法。TA 将策略抽象成了如下问题：

现在给定一个目标集合 $T$，该集合是 $\{1,\dots,n\}$ 的一个子集（$1\leq n\leq 5\times 10^5$）。你需要通过一系列操作构造一些集合最后得到 $T$，具体来说有以下三种操作：

• 创造一个大小为一的集合 $|S|=1$。
• 将已经被构造出的两个不交集合 $A, B$ 并起来，得到 $A\cup B$。
• 将已经被构造出的一个集合 $A$ 进行平移，也即 $A+x = \{ a+x : a\in A \}$。

一个已经被构造出的集合可以在之后被使用多次。同时你需要保证操作过程中出现的所有集合都是 $\{1,\dots,n\}$ 的子集。

你的代价是构造出的所有集合的大小之和，你不需要最小化代价，只需要让代价控制不超过 $5\times 10^6$ 即可。你用的操作数量也不应超过 $10^6$。

输入格式

第一行输入一个正整数 $n$。

接下来一行输入一个 01 串，长度为 $n$，第 $x$ 位为 1 表示 $x\in T$，否则 $x\notin T$，保证 $T$ 非空。

输出格式

第一行输出一个正整数 $m$ 表示你使用的操作数量。

接下来 $m$ 行，每行描述一个操作，设第 $i$ 次操作得到的集合为 $T_i$：

• 1 x 表示创造一个大小为一的集合 $\{x\}$。
• 2 x y 表示将不交集合 $T_x, T_y$ 并起来。
• 3 x y 表示将已经被构造出的一个集合进行平移，也即 $T_x+y$。

你需要保证所有操作满足题目要求，并且最后一次操作产生的集合是 $T$。

5
11011

5
1 1
1 4
2 1 2
3 3 1
2 3 4

提示

样例 #1 解释

• 第一次操作：创造集合 $T_1=\{1\}$。
• 第二次操作：创造集合 $T_2=\{4\}$。
• 第三次操作：将 $T_1, T_2$ 并起来，得到 $T_3=\{1,4\}$。
• 第四次操作：将 $T_3$ 平移 $1$，得到 $T_4=\{2,5\}$。
• 第五次操作：将 $T_3, T_4$ 并起来，得到 $T_5=\{1,2,4,5\}$。这就得到了 $T$。

这个方案的总代价是 $1 + 1 + 2 + 2 + 4 = 10$。

提示

如果你的复杂度是好的，请相信常数。

题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（https://github.com/ckw20/thupc2024_pre_public）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。