本题没有可用的提交语言。

题目背景

孩子们眼中的希望 是什么形状
是否醒来有面包当早餐 再喝碗热汤
农夫被烧毁土地跟村庄 终于拿起枪
她却慢慢习惯放弃了抵抗
孩子们眼中的希望 是什么形状
是否院子有秋千可以荡 口袋里有糖
刺刀的光被仇恨所擦亮 在远方野蛮
而她却微笑着不知道慌张
——《止战之殇》

题目描述

有 $n$ 个因为战争而历尽苦难的孩子，他们想要终止野蛮的战争。他们每人要选定一个整数作为自己的 天真值，第 $i$ 个孩子的 天真值 为 $a_i$，天真值 可以为负数。然后他们每次会选择两个孩子 $x,y$ 一起进行一次值为正整数 $k$ 的 祈祷，直到每人都进行了 $n-1$ 次 祈祷。一次由两个 天真值 分别为 $a_x$ 和 $a_y$ 的孩子一起进行一次值为 $k$ 的 祈祷 能够产生两个值分别为 $a_x+k$ 和 $a_y+k$ 的 殇歌。显然进行完所有 祈祷 后会产生 $n(n-1)$ 个 殇歌。如果这些 殇歌 的值 恰好 为 $1$ 到 $n(n-1)$ 的正整数 各一个，那么整个过程为一次 止战之殇，可以终止血腥的战争。现在孩子们想要知道他们怎样选择自己的 天真值 和每次 祈祷 的值才能制造出 止战之殇，由于他们还太小，所以就请你帮助他们。

题意简述

给定 $n$，构造一个长度为 $n$ 的整数列 $a_1,a_2,\dots,a_n$ 与 $\dfrac{n(n-1)}{2}$ 个三元组 $x_i,y_i,k_i(x_i \neq y_i,k_i \in \mathbb{Z_+})$，使得 $\forall i \in \{1,2,\dots,n\},\sum_{j=1}^{\frac{n(n-1)}{2}}([x_j==i]+[y_j==i])=n-1$ 且 $\left\{a_{x_i}+k_i:i=1,2,\dots,\frac{n(n-1)}{2}\right\}\cup\left\{a_{y_i}+k_i:i=1,2,\dots,\frac{n(n-1)}{2}\right\}=\{1,2,\dots,n(n-1)\}$。

输入格式

一行 $3$ 个整数 $n,op1,op2$。

如果 $op1=1$，那么必须满足每一对 $1 \le x<y \le n$ 的 $x,y$ 必须 恰好 一起进行一次 祈祷；否则没有特殊限制。

如果 $op2=1$，那么 天真值 必须为非负数；否则没有特殊限制。

输出格式

如果有解，第一行输出 $n$；否则输出 $-1$。

如果有解，第二行输出 $n$ 个非负整数表示编号为 $1$ 到 $n$ 的孩子分别的 天真值，接下来 $\dfrac{n(n-1)}{2}$ 行每行输出第 $i$ 次 祈祷 选定的 $x,y,k$。

输入输出样例

1 0 0

1
1

2 0 0

2
0 -1
1 2 2

3 0 1

-1

4 1 1

4
5 2 0 3
1 3 7
1 4 1
2 4 7
2 1 6
4 3 2
3 2 1

说明/提示

样例解释

对于第一组样例，最后没有生成任何 殇歌，满足要求。

对于第二组样例，$0+2=2,-1+2=1$，恰好为 $1$ 到 $2$ 各一个。

对于第三组样例，可以发现没有满足条件的方法。

对于第四组样例，有

$$5+7=12,0+7=7,5+1=6,3+1=4,2+7=9,3+7=10,$$ $$2+6=8,5+6=11,3+2=5,0+2=2,0+1=1,2+1=3,$$

恰好为 $1$ 到 $12$ 各一个。

---

数据范围

本题共有 $20$ 个数据点，每个数据点 $5$ 分，各个数据点的数据范围与限制如下。

Testdata No.	$n \le$	$op1$	$op2$	特殊限制
$1 \sim 4$	$300$	$0$	$1$	$n$ 为偶数
$5 \sim 10$				$n$ 为奇数
$11 \sim 17$	$3 \times 10^3$	$1$		无
$18 \sim 20$	$7$	$0$

对于 $100\%$ 的数据，$1 \le n \le 3 \times 10^3$，$op1,op2 \in \{0,1\}$。

---

提示

本题提供 $\texttt{Special Judge}$ 源码 和 checker.exe，使用方法为:
命令行在目标文件夹输入指令：

checker.exe input.txt output.txt output.txt

其中 input.txt 是输入数据文件，output.txt 是程序运行结果文件。观察评判结果即可。

• Accepted. 表示答案正确。
• Misjudgment of the existence of the answer. 表示有解性判断不正确。
• Negative ai. 表示 $a_i$ 为负数（$op2=1$ 时）。
• Invalid (x,y,k) No.i. 表示 $x_i$ 或 $y_i$ 不在 $[1,n]$ 中或 $x_i=y_i$ 或 $k_i$ 不为正整数。
• Invalid sum No.i. 表示 $a_{x_i}+k_i$ 或 $a_{y_i}+k_i$ 不在 $[1,n(n-1)]$ 中。
• Sum No.i already appeared. 表示 $a_{x_i}+k_i$ 或 $a_{y_i}+k_i$ 已经出现过。
• (x,y) No.i already appeared. 表示 $(x_i,y_i)$ 已经出现过（$op1=1$ 时）。

请务必保证输出格式正确，否则 $\texttt{Special Judge}$ 可能会返回 $\texttt{Unkown Error}$ 等不可预估的结果。