长度为 $n$ 的整数数组 $a$ 的前缀和数组是一个长度为 $n$ 的数组 $b$，满足 $b_i = a_1 + a_2 + \dots + a_i$。

长度为 $n$ 的整数数组 $a$ 的后缀和数组是一个长度为 $n$ 的数组 $b$，满足 $b_i = a_n + a_{n-1} + \dots + a_i$。

我们将长度为 $n$ 的整数数组 $a$ 的归一化定义为执行赋值操作 $a_i \leftarrow \max(\min(a_i, 10^{18}), -10^{18})$，其中 $1 \le i \le n$。

给定一个长度为 $n$ 的整数数组 $a$。

我们可以执行三种类型的操作：

1. 将数组 $a$ 中的每个元素替换为其相反数（执行赋值 $a_i \leftarrow (-a_i)$，其中 $1 \le i \le n$）；
2. 选择数组 $a$ 的任意子段，将其替换为该子段的前缀和数组，然后对数组 $a$ 进行归一化；
3. 选择数组 $a$ 的任意子段，将其替换为该子段的后缀和数组，然后对数组 $a$ 进行归一化。

求使数组 $a$ 中所有元素均为非负数所需的最短操作序列。

注意，对于某些测试块，允许找到非最短的操作序列。

输入格式

第一行包含两个整数 $n$ 和 $g$（$1 \le n \le 2 \cdot 10^5$，$0 \le g \le 8$），分别表示数组长度和测试组编号。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-1 \le a_i \le 1$），表示数组元素。

输出格式

第一行输出一个整数 $m$，表示使数组 $a$ 中所有元素均为非负数所需的最少操作次数。

接下来的 $m$ 行，输出操作描述。第一类操作的描述格式为 “1”。第二类和第三类操作的描述格式分别为 “2 l r” 和 “3 l r”，其中 $l$ 和 $r$（$1 \le l \le r \le n$）表示对应操作的子数组的左右边界。

如果存在多个正确答案，输出其中任意一个即可。

说明

在第一个样例中，数组 $a$ 发生了两次变化：

1. 执行第三类操作，参数为 $l = 1, r = 3$ 后，数组 $a$ 变为 $[1, 1, 1, -1, -1, -1, 1]$；
2. 执行第二类操作，参数为 $l = 1, r = 7$ 后，数组 $a$ 变为 $[1, 2, 3, 2, 1, 0, 1]$。

样例

样例 1

7 0
0 0 1 -1 -1 -1 1

样例 1 输出

2
3 1 3
2 1 7

子任务

设对于某个测试，使数组 $a$ 中所有元素均为非负数所需的最少操作次数为 $m_{ans}$，你的程序使用的操作次数为 $m_{user}$。

1. (14 分): $m_{ans} \le 1$；
2. (17 分): 如果 $m_{user} \le 100$，则你的解法被视为正确。可以证明在给定约束下，总是存在不超过 100 次操作的序列；
3. (18 分): 如果 $m_{user} \le m_{ans} + 3$，则你的解法被视为正确；
4. (7 分): 如果 $m_{user} \le m_{ans} + 1$，则你的解法被视为正确；
5. (7 分): $n \le 3000$；保证所有最短操作序列仅包含第二类操作；
6. (19 分): 保证所有最短操作序列仅包含第二类操作；
7. (17 分): $n \le 3000$；
8. (1 分): 无额外约束。