这是本题的困难版本。两个版本之间唯一的区别在于 $N$ 的限制。 给定一个神秘的幺半群 $(M, \oplus)$ 和 4 个用于计算它的 CPU。 使用 4 个 CPU 并行计算序列 $A = (A_1, A_2, \dots, A_N)$ 的累积 $\oplus$ 和，并最小化操作次数。
给定一个整数 $N$。编写一个自定义语言的程序来执行以下任务，并最小化程序中的指令数量。
规范
该程序可以处理 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)$。
格式
程序的第一行包含一个整数 $L$，表示程序中的指令数。
这 $L$ 条指令从第 $2$ 行到第 $(4L + 1)$ 行给出，每条指令占 $4$ 行，并从上到下按顺序执行。
每条指令由 $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$（含）之间。
对于每条指令，按顺序执行以下操作：
- 将 $\text{concat}(A[a_1], A[b_1])$ 赋值给 $C_1$。
- 将 $\text{concat}(A[a_2], A[b_2])$ 赋值给 $C_2$。
- 将 $\text{concat}(A[a_3], A[b_3])$ 赋值给 $C_3$。
- 将 $\text{concat}(A[a_4], A[b_4])$ 赋值给 $C_4$。
- 将 $C_1$ 赋值给 $A[c_1]$。
- 将 $C_2$ 赋值给 $A[c_2]$。
- 将 $C_3$ 赋值给 $A[c_3]$。
- 将 $C_4$ 赋值给 $A[c_4]$。
此处，$\text{concat}(x, y)$ 表示将序列 $x$ 和 $y$ 按该顺序连接后得到的序列。
输入格式
输入格式如下：
$N$
- 输入中的所有值均为整数。
- $17 \le N \le 1000$
输出格式
设 $L$ 为最小指令数。按以下格式输出：
$L$ $op_1$ $op_2$ $\vdots$ $op_L$
$op_i$ ($1 \le i \le L$) 表示第 $i$ 次操作，应按以下格式输出：
$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 之间。