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;
int n, q;
int a[5000];
int next_low[5000], next_high[5000];
int prev_low[5000], prev_high[5000];
map<pair<int, int>, int> block[20];
int nxt_op;
int from[20], to[20];
vector<pair<int, int> > op_seq;
int qry_ans[100000];
int prevblock[5000][20];
int nextblock[5000][20];
int add_op(int x, int y) {
  op_seq.push_back(make_pair(x, y));
  nxt_op++;
  return nxt_op - 1;
}
void work(int val_l, int val_r, vector<int>& pos,
          map<pair<int, int>, int>& set_id) {
  if (val_l == val_r) {
    set_id[make_pair(pos[0], pos[0])] = pos[0];
    return;
  }
  vector<int> low_pos, high_pos;
  map<pair<int, int>, int> low_set_id, high_set_id;
  for (int idx = 0; idx < pos.size(); idx++) {
    int i = pos[idx];
    if (a[i] <= (val_l + val_r) / 2) {
      low_pos.push_back(i);
    } else {
      high_pos.push_back(i);
    }
  }
  work(val_l, (val_l + val_r) / 2, low_pos, low_set_id);
  work((val_l + val_r) / 2 + 1, val_r, high_pos, high_set_id);
  for (int idx = 0; idx < pos.size(); idx++) {
    int i = pos[idx];
    if (a[i] <= (val_l + val_r) / 2) {
      prev_low[i] = i;
      prev_high[i] = (idx == 0 ? 0 : prev_high[pos[idx - 1]]);
    } else {
      prev_low[i] = (idx == 0 ? 0 : prev_low[pos[idx - 1]]);
      prev_high[i] = i;
    }
  }
  for (int idx = (int)pos.size() - 1; idx >= 0; idx--) {
    int i = pos[idx];
    if (a[i] <= (val_l + val_r) / 2) {
      next_low[i] = i;
      next_high[i] =
          (idx == ((int)pos.size() - 1) ? n + 1 : next_high[pos[idx + 1]]);
    } else {
      next_low[i] =
          (idx == ((int)pos.size() - 1) ? n + 1 : next_low[pos[idx + 1]]);
      next_high[i] = i;
    }
  }
  for (int idx1 = 0; idx1 < pos.size(); idx1++) {
    for (int idx2 = idx1; idx2 < pos.size(); idx2++) {
      int i = pos[idx1];
      int j = pos[idx2];
      int l1 = next_low[i], r1 = prev_low[j];
      int l2 = next_high[i], r2 = prev_high[j];
      if (l1 <= r1 && l2 <= r2) {
        set_id[make_pair(i, j)] = add_op(low_set_id[make_pair(l1, r1)],
                                         high_set_id[make_pair(l2, r2)]);
      } else if (l1 <= r1) {
        set_id[make_pair(i, j)] = low_set_id[make_pair(l1, r1)];
      } else {
        set_id[make_pair(i, j)] = high_set_id[make_pair(l2, r2)];
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &q);
  nxt_op = n + 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  int cur = 1;
  for (int i = 1; i <= 16; i++) {
    int blksiz = (n / 16) + ((i - 1 < n % 16) ? 1 : 0);
    if (!blksiz) continue;
    from[i] = cur;
    to[i] = cur + blksiz - 1;
    vector<int> pos_vec;
    for (int j = 1; j <= n; j++) {
      if (from[i] <= a[j] && a[j] <= to[i]) pos_vec.push_back(j);
    }
    work(from[i], to[i], pos_vec, block[i]);
    cur = to[i] + 1;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 16; j++) {
      if (from[j] <= a[i] && a[i] <= to[j]) {
        prevblock[i][j] = i;
      } else {
        prevblock[i][j] = prevblock[i - 1][j];
      }
    }
  }
  for (int i = 1; i <= 16; i++) nextblock[n + 1][i] = n + 1;
  for (int i = n; i >= 1; i--) {
    for (int j = 1; j <= 16; j++) {
      if (from[j] <= a[i] && a[i] <= to[j]) {
        nextblock[i][j] = i;
      } else {
        nextblock[i][j] = nextblock[i + 1][j];
      }
    }
  }
  for (int qry = 1; qry <= q; qry++) {
    int l, r;
    scanf("%d%d", &l, &r);
    int curset = -1;
    for (int i = 1; i <= 16; i++) {
      int cur_l = nextblock[l][i];
      int cur_r = prevblock[r][i];
      if (cur_l <= cur_r) {
        if (curset == -1) {
          curset = block[i][make_pair(cur_l, cur_r)];
        } else {
          curset = add_op(curset, block[i][make_pair(cur_l, cur_r)]);
        }
      }
    }
    qry_ans[qry] = curset;
  }
  printf("%d\n", nxt_op - 1);
  for (int i = 0; i < op_seq.size(); i++) {
    printf("%d %d\n", op_seq[i].first, op_seq[i].second);
  }
  for (int i = 1; i <= q; i++) {
    printf("%d ", qry_ans[i]);
  }
  return 0;
}