这是本题的困难版本。两个版本之间唯一的区别在于 $N$ 的限制。 给定一个神秘的幺半群 $(M, \oplus)$ 和 4 个用于计算它的 CPU。 使用 4 个 CPU 并行计算序列 $A = (A_1, A_2, \dots, A_N)$ 的累积 $\oplus$ 和，并最小化操作次数。

实现细节

该程序可以处理 2004 个变量 $A[1], A[2], \dots, A[2000], C_1, C_2, C_3, C_4$。每个变量可以存储一个整数序列，且 $A[i]$ ($1 \le i \le 2000$) 初始化为 $A[i] = (i)$。（此处 $(i)$ 表示由单个整数 $i$ 组成的序列。）

在执行结束时，必须满足以下条件： * 对于每个 $i = 1, 2, \dots, N$，满足 $A[i] = (1, 2, \dots, i)$。

输入格式

输入格式如下：

$N$

• 输入中的所有值均为整数。
• $17 \le N \le 1000$

输出格式

设 $L$ 为最小指令数。按以下格式输出：

$L$ $op_1$ $op_2$ $\vdots$ $op_L$

其中 $op_i$ ($1 \le i \le L$) 表示第 $i$ 条指令。每条指令由 12 个整数 $c_1, a_1, b_1, c_2, a_2, b_2, c_3, a_3, b_3, c_4, a_4, b_4$ 组成，且每个整数必须在 1 到 2000 之间。

对于每条指令，按顺序执行以下操作：

1. 将 $\text{concat}(A[a_1], A[b_1])$ 赋值给 $C_1$。
2. 将 $\text{concat}(A[a_2], A[b_2])$ 赋值给 $C_2$。
3. 将 $\text{concat}(A[a_3], A[b_3])$ 赋值给 $C_3$。
4. 将 $\text{concat}(A[a_4], A[b_4])$ 赋值给 $C_4$。
5. 将 $C_1$ 赋值给 $A[c_1]$。
6. 将 $C_2$ 赋值给 $A[c_2]$。
7. 将 $C_3$ 赋值给 $A[c_3]$。
8. 将 $C_4$ 赋值给 $A[c_4]$。

此处，$\text{concat}(x, y)$ 表示将序列 $x$ 和 $y$ 按该顺序连接后得到的序列。

样例

输入格式 1

17

输出格式 1

(输出数据)