쿠키 분배하기

처음에 $i\ (1 \leq i \leq N)$번 사람은 $A_i$개의 쿠키를 가지고 있다. 이때, $A_1 + A_2 + \cdots + A_N$은 $N$의 배수임이 보장된다.

한 번의 시행으로 양의 정수 $k \ (1 \leq k \leq N)$와 양의 정수 $x$를 골라, $k$번 사람이 가진 쿠키 $x$개를 $k + 1$번 사람에게 줄 수 있다. 단, 시행 직전에 $k$번 사람은 쿠키를 $x$개 이상 가지고 있어야 하며, $N + 1$번 사람은 $1$번 사람과 동일하다.

모든 사람이 동일한 개수의 쿠키를 갖도록 하는 시행 순서를 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1 \ A_2 \ \cdots \ A_N$

시행 횟수를 $S$라고 하자. $i \ (1 \leq i \leq S)$번째 시행에서 $k_i$번 사람이 $k_i + 1$번 사람에게 쿠키 $x_i$개를 주었다면, 다음과 같은 형식으로 출력한다.

$S$ $k_1 \ x_1$ $k_2 \ x_2$ $\vdots$ $k_S \ x_S$

• $2 \leq N \leq 200\ 000$.
• $0 \leq A_i \leq 1 \ 000 \ 000 \ 000 \ (1 \leq i \leq N)$.
• $A_1 + A_2 + \cdots + A_N$은 $N$의 배수이다.

출력은 $0 \leq S \leq 5N$, $1 \leq k_i \leq N$, $1 \leq x_i \leq 10^{18}$을 만족해야 한다. 또한 각 시행 직전에 $k_i$번 사람은 쿠키를 $x_i$개 이상 가지고 있어야 하며, 모든 시행이 끝난 뒤 모든 사람의 쿠키 개수가 같아야 한다.

서브태스크 $1, 2, 3$에서는 위 조건을 모두 만족하면 만점을 받는다.

서브태스크 $4$에서는 부분 점수가 주어진다. 각 테스트케이스에 대하여 시행 횟수를 $S$, 가능한 최소 시행 횟수를 $T$라 할 때 해당 테스트케이스의 점수는

이며, 서브태스크 $4$의 점수는 이에 속한 모든 테스트케이스의 점수 중 최솟값이다.