题目描述

作为今年最后一道题，Kircho 想为你们准备一些特别的东西，所以今天大家要搭乐高。

Kircho 找来了一组共 $$N$$ 个人，编号为 $$0,1,\ldots,N-1$$。他们按照这个顺序顺时针围成一个圆，正在尝试用乐高积木搭建不同的物体。

我们只关心每个人当前已经使用的乐高积木数量。第 $$i$$ 个人当前使用的积木数记为正整数 $$A_i$$。

最开始时，每个人的物体都只由一块乐高积木组成，也就是：

$$A_i=1$$

构造过程如下：

• 每次操作中，恰好一个人可以“复制”他顺时针方向相邻的人的物体，并把复制出的物体加入自己的物体中。

形式化地说，每次操作选择一个下标 $$i$$，然后执行：

$$A_i \leftarrow A_i + A_{(i+1)\bmod N}.$$

Kircho 一时分神，没有看到这组人从一开始到现在的操作过程，只看到了当前的状态，即序列：

$$A_0,A_1,\ldots,A_{N-1}.$$

现在他想恢复出一组操作序列，使得从初始全为 $$1$$ 的状态可以到达当前状态。如果不存在这样的操作序列，也需要判断出来。

由于 Kircho 很忙，他请你写程序来完成这件事。

输入格式

第一行包含一个整数 $$T$$，表示测试数据中的子测试数量。

接下来依次给出 $$T$$ 个子测试。每个子测试格式如下：

第一行一个整数 $$N$$。

第二行 $$N$$ 个正整数：

$$A_0,A_1,\ldots,A_{N-1}.$$

输出格式

对于每个子测试，输出一种合法判断与构造。

如果无法从初始全为 $$1$$ 的状态到达给定状态，输出一行：

NO

如果可以到达，第一行输出：

YES K

其中 $$K$$ 表示你输出的压缩操作数量。

接下来输出 $$K$$ 行，每行两个整数：

u_j v_j

表示编号为 $$u_j$$ 的人连续执行 $$v_j$$ 次操作，然后再进行之后输出的操作。

也就是说，这一行表示连续执行 $$v_j$$ 次：

$$A_{u_j}\leftarrow A_{u_j}+A_{(u_j+1)\bmod N}.$$

输出的操作应按实际执行顺序给出。

如果存在多种合法操作序列，输出任意一种即可。

样例

输入

1
2
4 3

输出

YES 2
1 2
0 1

样例解释

初始状态为：

$$[1,1]$$

执行两次操作 $$u=1$$：

$$[1,1]\to[1,2]\to[1,3]$$

再执行一次操作 $$u=0$$：

$$[1,3]\to[4,3]$$

因此可以到达目标状态。

数据范围

对于所有数据，满足：

• 1\le T\le 2\times 10^5$$；
• 1\le A_i\le 10^9$$；
• 每个测试文件中，所有子测试的 $$N$$ 之和不超过 $$2\times 10^5$$。

子任务

子任务	分值	依赖子任务	$$N$$	$$T$$	其他限制
0		-		-	样例测试
1	13	0	$$\le 6$$		$$A_i\le 6$$
2	9	-	-		$$A_0=1$$
3	12	2			所有 $$A_i$$ 都是 2 的幂
4	21	0,1	$$\le 2\times 10^3$$	$$\le 3$$	-
5	19	0,1,4	$$\le 4\times 10^4$$	-
6	26	0,1,2,3,4,5	-

说明

本题原始版本为函数实现题，需要实现：

std::pair<bool, std::vector<std::pair<int,int>>> solve(std::vector<int> A);

本 Hydro OJ 版本已改为标准输入输出题。由于合法构造不唯一，评测使用 Special Judge 检查输出的判断和操作序列是否合法。