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 N = (1 << 16) + 5;
int n, q, blng[N], L[N], R[N], ID, cnt, Q[N], X[N], res[N];
map<pair<int, pair<int, int> >, int> Set;
vector<pair<int, int> > opt;
struct node {
  int x, y, w, p, id;
} cur[N];
inline bool cmpy(const node &fir, const node &sec) { return fir.y < sec.y; }
inline bool cmpx(const node &fir, const node &sec) { return fir.x < sec.x; }
int Merge(int a, int b) {
  opt.push_back(make_pair(a, b));
  return ++cnt;
}
int Solve(int l, int r, int w) {
  if (l == r) {
    cur[l].w = w;
    cur[l].p = l;
    return cur[l].id;
  }
  int mid = l + r >> 1;
  int ls = Solve(l, mid, 0);
  int rs = Solve(mid + 1, r, 1);
  ID++;
  sort(cur + l, cur + r + 1, cmpx);
  for (int i = l; i <= r; i++) {
    int Lmn = -1, Lmx = -1, Rmn = -1, Rmx = -1;
    for (int j = i; j <= r; j++) {
      if (cur[j].w == 0) {
        if (Lmn == -1) Lmn = cur[j].p;
        if (Lmx == -1) Lmx = cur[j].p;
        Lmn = min(Lmn, cur[j].p);
        Lmx = max(Lmx, cur[j].p);
      } else {
        if (Rmn == -1) Rmn = cur[j].p;
        if (Rmx == -1) Rmx = cur[j].p;
        Rmn = min(Rmn, cur[j].p);
        Rmx = max(Rmx, cur[j].p);
      }
      if (Lmn == -1)
        Set[make_pair(ID, make_pair(i, j))] =
            Set[make_pair(rs, make_pair(Rmn, Rmx))];
      else if (Rmn == -1)
        Set[make_pair(ID, make_pair(i, j))] =
            Set[make_pair(ls, make_pair(Lmn, Lmx))];
      else
        Set[make_pair(ID, make_pair(i, j))] =
            Merge(Set[make_pair(ls, make_pair(Lmn, Lmx))],
                  Set[make_pair(rs, make_pair(Rmn, Rmx))]);
    }
  }
  for (int i = l; i <= r; i++) cur[i].w = w, cur[i].p = i;
  return ID;
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &cur[i].y);
    cur[i].x = cur[i].id = i;
  }
  cnt = ID = n;
  sort(cur + 1, cur + n + 1, cmpy);
  for (int i = 1; i <= n; i++)
    Set[make_pair(cur[i].id, make_pair(i, i))] = cur[i].id;
  int sz = (int)sqrt(q);
  for (int i = 1; i <= n; i++) {
    blng[i] = (i - 1) / sz + 1;
    if (blng[i] != blng[i - 1]) L[blng[i]] = i, R[blng[i - 1]] = i - 1;
  }
  R[blng[n]] = n;
  for (int i = 1; i <= blng[n]; i++) Q[i] = Solve(L[i], R[i], 0);
  for (int i = 1; i <= n; i++) X[i] = cur[i].x;
  for (int qry = 1; qry <= q; qry++) {
    int ql, qr, ans = -1;
    scanf("%d %d", &ql, &qr);
    for (int i = 1; i <= blng[n]; i++) {
      int p1 = lower_bound(X + L[i], X + R[i] + 1, ql) - X;
      int p2 = upper_bound(X + L[i], X + R[i] + 1, qr) - X - 1;
      if (p1 < L[i] || p1 > R[i] || p2 < L[i] || p2 > R[i] || p2 < p1) continue;
      if (ans == -1)
        ans = Set[make_pair(Q[i], make_pair(p1, p2))];
      else
        ans = Merge(ans, Set[make_pair(Q[i], make_pair(p1, p2))]);
    }
    res[qry] = ans;
  }
  printf("%d\n", cnt);
  for (int i = 0; i < opt.size(); i++)
    printf("%d %d\n", opt[i].first, opt[i].second);
  for (int i = 1; i <= q; i++) printf("%d ", res[i]);
  return 0;
}