Problem: You are given a permutation a_1, a_2, ..., a_n of numbers from 1 to n. Also, you have n sets S_1,S_2,..., 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_{u∈ S} u;

g(S)=max_{u∈ 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← cnt+1;

  * S_{cnt}=S_u∪ S_v, you are free to choose u and v for which 1≤ 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∣ l_i≤ u≤ 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≤ 2.2× 10^6. Note that you don't have to minimize cnt. It is guaranteed that a solution under given constraints exists.

Input

The first line contains two integers n,q (1≤ n ≤ 2^{12},1 ≤ q ≤ 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,⋅⋅⋅, a_n (1≤ a_i≤ n, a_i are pairwise distinct) — given permutation.

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

Output

It is guaranteed that a solution under given constraints exists.

The first line should contain one integer cnt_E (n≤ cnt_E≤ 2.2× 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≤ u, v≤ 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,⋅⋅⋅,k_q (1≤ k_i≤ cnt_E), representing that set S_{k_i} is the ith required set.

Please notice the large amount of output.

Examples

Input


3 2
1 3 2
2 3
1 3


Output


6
3 2
1 3
5 2
4 6 

Input


2 4
2 1
1 2
1 2
1 2
1 1


Output


5
2 1
2 1
2 1
5 3 3 1

Note

In the first sample:

We have S_1=\{1\},S_2=\{3\},S_3=\{2\} initially.

In the first operation, because g(S_3)=2<f(S_2)=3, we can merge S_3,S_2 into S_4=\{2,3\}.

In the second operation, because g(S_1)=1<f(S_3)=2, we can merge S_1,S_3 into S_5=\{1,2\}.

In the third operation, because g(S_5)=2<f(S_2)=3, we can merge S_5,S_2 into S_6=\{1,2,3\}.

For the first requirement, S_4=\{2,3\}=\\{a_2,a_3\}, satisfies it, thus k_1=4.

For the second requirement, S_6=\{1,2,3\}=\\{a_1,a_2,a_3\}, satisfies it, thus k_2=6

Notice that unused sets, identical sets, outputting the same set multiple times, and using sets that are present initially are all allowed.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int Q = 1 << 19;
vector<pair<int, int>> ad;
vector<int> va[Q], bel[Q], nxt[Q], pos[Q];
unordered_map<int, int> rem[Q];
int L[Q], R[Q];
int tot, p[Q];
void Init(int now, int l, int r) {
  if (l == r) {
    va[now].push_back(p[l]);
    rem[now][0] = p[l];
    return;
  }
  int mid = (l + r) >> 1;
  Init((now << 1), l, mid), Init((now << 1 | 1), mid + 1, r);
  int sl = mid - l + 1, sr = r - mid, pl = 0, pr = 0;
  pos[now].resize(r - l + 1);
  va[now].resize(r - l + 1), bel[now].resize(r - l + 1),
      nxt[now].resize(r - l + 1);
  for (int o = 0; o < r - l + 1; o++)
    if (pr == sr || (pl < sl && va[(now << 1)][pl] < va[(now << 1 | 1)][pr]))
      pos[now][o] = pl, va[now][o] = va[(now << 1)][pl++], bel[now][o] = 0;
    else
      pos[now][o] = pr, va[now][o] = va[(now << 1 | 1)][pr++], bel[now][o] = 1;
  if (!bel[now].back())
    nxt[now][r - l] = sr;
  else
    nxt[now][r - l] = sl;
  for (int i = r - l - 1; i >= 0; --i)
    if (bel[now][i] != bel[now][i + 1])
      nxt[now][i] = pos[now][i + 1];
    else
      nxt[now][i] = nxt[now][i + 1];
}
void Get(int now, int l, int r, int x, int y) {
  if (rem[now].count((((x) << 13) + (y)))) return;
  assert(l < r);
  int mid = (l + r) >> 1;
  int lx = pos[now][x], rx = nxt[now][x], ly = pos[now][y],
      ry = nxt[now][y] - 1;
  if (bel[now][x]) swap(lx, rx);
  if (bel[now][y]) swap(ly, ry);
  if (lx <= ly) Get((now << 1), l, mid, lx, ly);
  if (rx <= ry) Get((now << 1 | 1), mid + 1, r, rx, ry);
  if (lx > ly)
    rem[now][(((x) << 13) + (y))] = rem[(now << 1 | 1)][(((rx) << 13) + (ry))];
  else if (rx > ry)
    rem[now][(((x) << 13) + (y))] = rem[(now << 1)][(((lx) << 13) + (ly))];
  else
    rem[now][(((x) << 13) + (y))] = ++tot,
                            ad.push_back(make_pair(
                                rem[(now << 1)][(((lx) << 13) + (ly))],
                                rem[(now << 1 | 1)][(((rx) << 13) + (ry))]));
}
char pbuf[1 << 20], *pp = pbuf;
void push(const char c) {
  if (pp - pbuf == (1 << 20)) fwrite(pbuf, 1, (1 << 20), stdout), pp = pbuf;
  *pp++ = c;
}
inline void W(int x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) push(sta[--top] + '0');
}
int main() {
  int n, qaq;
  scanf("%d%d", &n, &qaq);
  tot = n;
  for (int i = 1, x; i <= n; i++) scanf("%d", &x), p[x] = i;
  Init(1, 1, n);
  for (int i = 1; i <= qaq; i++)
    scanf("%d%d", &L[i], &R[i]), --L[i], --R[i], Get(1, 1, n, L[i], R[i]);
  W(tot), push('\n');
  for (auto p : ad) W(p.first), push(' '), W(p.second), push('\n');
  for (int i = 1; i <= qaq; i++)
    W(rem[1][(((L[i]) << 13) + (R[i]))]), push(' ');
  fwrite(pbuf, 1, pp - pbuf, stdout);
  return 0;
}