You are given a permutation $a_1, a_2, \dots, a_n$ of numbers from $1$ to $n$. Also, you have $n$ sets $S_1,S_2,\dots, S_n$, where $S_i=\{a_i\}$. Lastly, you have a variable $cnt$, representing the current number of sets. Initially, $cnt = n$.

We define two kinds of functions on sets:

$f(S)=\min\limits_{u\in S} u$;

$g(S)=\max\limits_{u\in S} u$.

You can obtain a new set by merging two sets $A$ and $B$, if they satisfy $g(A)<f(B)$ (Notice that the old sets do not disappear).

Formally, you can perform the following sequence of operations:

• $cnt\gets cnt+1$;

• $S_{cnt}=S_u\cup S_v$, you are free to choose $u$ and $v$ for which $1\le u, v < cnt$ and which satisfy $g(S_u)<f(S_v)$.

You are required to obtain some specific sets.

There are $q$ requirements, each of which contains two integers $l_i$,$r_i$, which means that there must exist a set $S_{k_i}$ ($k_i$ is the ID of the set, you should determine it) which equals $\{a_u\mid l_i\leq u\leq r_i\}$, which is, the set consisting of all $a_i$ with indices between $l_i$ and $r_i$.

In the end you must ensure that $cnt\leq 2.2\times 10^6$. Note that you don't have to minimize $cnt$. It is guaranteed that a solution under given constraints exists.

The first line contains two integers $n,q$ $(1\leq n \leq 2^{12},1 \leq q \leq 2^{16})$  — the length of the permutation and the number of needed sets correspondently.

The next line consists of $n$ integers $a_1,a_2,\cdots, a_n$ ($1\leq a_i\leq n$, $a_i$ are pairwise distinct)  — given permutation.

$i$-th of the next $q$ lines contains two integers $l_i,r_i$ $(1\leq l_i\leq r_i\leq n)$, describing a requirement of the $i$-th set.

It is guaranteed that a solution under given constraints exists.

The first line should contain one integer $cnt_E$ $(n\leq cnt_E\leq 2.2\times 10^6)$, representing the number of sets after all operations.

$cnt_E-n$ lines must follow, each line should contain two integers $u$, $v$ ($1\leq u, v\leq cnt'$, where $cnt'$ is the value of $cnt$ before this operation), meaning that you choose $S_u$, $S_v$ and perform a merging operation. In an operation, $g(S_u)<f(S_v)$ must be satisfied.

The last line should contain $q$ integers $k_1,k_2,\cdots,k_q$ $(1\leq k_i\leq cnt_E)$, representing that set $S_{k_i}$ is the $i$th required set.

Please notice the large amount of output.