该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Day 1

MrPython：“能做出来这题的是 zak”

Day 2

MrPython：“%%% zak”

Description

对于一个长为 $n$ 的序列 $A$，定义一次操作 $\operatorname{CheckAndSwap}(i,j)(1\le i,j\le n)$ 为：

1. 检查是否有 $A_{i}\gt A_{j}$；
2. 若是，交换 $A_i$ 和 $A_j$。

现在，你有一个机器，可以在一个序列上对若干对不同位置，并行地进行 $\operatorname{CheckAndSwap}$ 操作。

形式地说，你每次可以指定 $m$ 个有序二元对 $(i_1,j_1),(i_2,j_2),\dots,(i_m,j_m)$，且这 $2m$ 个数互不相同，机器会同时进行 $m$ 次 $\operatorname{CheckAndSwap}$ 操作，第 $x$ 次操作为 $\operatorname{CheckAndSwap}(i_x,j_x)$，上述过程用时 $1$ 个单位时间。

你希望用尽量少的时间对长为 $N$ 的序列排序。

Constraints and Subtasks

对于全部测试点，满足：

• $1 \leq N \leq 100$

每个子任务的输入如下：

对于每个子任务，如果你的代码不正确，则获得 $0$ 分。

否则，如果代码耗时 $t$ 单位时间，设这个子任务的评分参数为 $t_1,t_2,t_3$，那么你的分数为

即 $f(t)$ 四舍五入后的结果。

Input

输入内容从标准输入中给出，格式如下：

$ \boxed{\begin{aligned} & n {\quad} t_1 {\quad} t_2 {\quad} t_3 \end{aligned}} $

Output

首先输出一行一个非负整数 $t$，表示你排序需要的时间。

接下来，若 $t\ne 0$，你需要按顺序输出 $t$ 组操作序列，对于每一组操作序列：

• 先输出 $m$，表示你要同时对 $m$ 对下标进行操作。

• 接下来 $m$ 行，每行两个正整数 $i_x,j_x$，表示对下标 $i_x,j_x$ 做操作。

Samples

4

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

以序列 3 1 4 2 为例：

• 第 $1$ 个单位时间内，对 $(1,2),(3,4)$ 操作，序列变为 1 3 2 4；
• 第 $2$ 个单位时间内，对 $(1,3),(2,4)$ 操作，序列没有变化；
• 第 $3$ 个单位时间内，对 $(2,3)$ 操作，序列变为 1 2 3 4。

可以验证，对于任何长为 $4$ 的序列，可以经上述操作后排序。

Note

判定答案是 $\text{co-NP}$ 的，因此 SPJ 只对部分序列检查你的答案是否能将其排序。

因此，也不保证赛时不会进行数据加强。