版权声明

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/T743372

题目描述

给定 $k,n_{\max}$ 和 $c_0,c_1,\ldots,c_k$，请构造 $n,m$ 和 $n$ 个结点 $m$ 条边的简单有向无环图 $G$。

设这张图的结点由 $1 \sim n$ 编号，边由 $1 \sim m$ 编号，第 $i$ 条边为 $(u_i,v_i)$。

这张图需要满足：

• $1 \le n \le n_{\max}$，$k \le m \le 6 \times 10^4$。
• $u_i < v_i$。
• $1 \rightarrow n$ 的路径有 $c_0$ 条。
• 删除边 $i$ 后，$1 \rightarrow n$ 的路径有 $c_i$ 条。

可以证明，在给定的数据范围下，构造方案一定存在。

输入格式

第一行两个非负整数 $k,n_{\max}$。

第二行 $k+1$ 个非负整数 $c_0,c_1,\ldots,c_k$。

输出格式

第一行两个非负整数 $n,m$。

接下来 $m$ 行，每行两个正整数 $u_i,v_i$。

样例

1 10000
2 1

3 3
1 3
1 2
2 3

数据范围

对于 $100\%$ 的数据，$0 \le k \le 32$，$0 \le c_i \le 2^{32} - 1$，$66 \le n_{\max} \le 10^4$，且对所有 $1 \le i \le k$ 有 $c_i \le c_0$。

• 特殊性质 A：保证本子任务中测试点的输入数据与样例输入相同。
• 特殊性质 B：$c_0$ 是 $2$ 的非负整数次幂。
• 特殊性质 C：$c_1 = c_2 = \ldots = c_k = 0$。
• 特殊性质 D：$c_1 = c_2 = \ldots = c_k = c_0$。