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 = 4100;
const int B = 256;
int n, q, a[N], bel[N], cnt, tt, k[65540], mx[2200010];
vector<int> pos[N];
vector<vector<int> > s[N];
vector<pair<int, int> > ans;
int merge(int x, int y) {
  if (mx[x] > mx[y]) swap(x, y);
  ans.push_back(make_pair(x, y));
  ++cnt;
  mx[cnt] = max(mx[x], mx[y]);
  return cnt;
}
vector<vector<int> > solve(vector<int> pos) {
  if (pos.empty()) return vector<vector<int> >();
  int l = 1e9, r = -1e9;
  for (auto p : pos) l = min(l, a[p]), r = max(r, a[p]);
  if (l == r) {
    vector<vector<int> > ret = {{pos[0]}};
    return ret;
  }
  int mid = (l + r) >> 1;
  vector<int> pos_ls, pos_rs;
  for (auto p : pos)
    if (a[p] <= mid)
      pos_ls.push_back(p);
    else
      pos_rs.push_back(p);
  auto ret_ls = solve(pos_ls), ret_rs = solve(pos_rs);
  vector<vector<int> > ret(int(pos.size()), vector<int>(int(pos.size())));
  for (int i = 0, s1 = 0, s2 = 0; i < int(pos.size()); i++) {
    while (s1 < int(pos_ls.size()) && pos_ls[s1] < pos[i]) ++s1;
    while (s2 < int(pos_rs.size()) && pos_rs[s2] < pos[i]) ++s2;
    for (int j = i, p1 = s1, p2 = s2; j < int(pos.size()); j++) {
      while (p1 < int(pos_ls.size()) && pos_ls[p1] <= pos[j]) ++p1;
      while (p2 < int(pos_rs.size()) && pos_rs[p2] <= pos[j]) ++p2;
      if (p1 == s1)
        ret[i][j] = ret_rs[s2][p2 - 1];
      else if (p2 == s2)
        ret[i][j] = ret_ls[s1][p1 - 1];
      else
        ret[i][j] = merge(ret_ls[s1][p1 - 1], ret_rs[s2][p2 - 1]);
    }
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++)
    cin >> a[i], bel[i] = (i - 1) / B + 1, mx[i] = a[i];
  for (int i = 1; i <= n; i++) pos[bel[a[i]]].push_back(i);
  cnt = n;
  tt = bel[n];
  for (int i = 1; i <= tt; i++) s[i] = solve(pos[i]);
  for (int T = 1; T <= q; T++) {
    int l, r, ret = 0;
    cin >> l >> r;
    for (int i = 1; i <= bel[n]; i++) {
      int L = 1e9, R = -1e9;
      for (int j = 0; j < int(pos[i].size()); j++)
        if (l <= pos[i][j] && pos[i][j] <= r) L = min(L, j), R = max(R, j);
      if (L > R) continue;
      if (!ret)
        ret = s[i][L][R];
      else
        ret = merge(ret, s[i][L][R]);
    }
    k[T] = ret;
  }
  cout << cnt << '\n';
  for (auto t : ans) cout << t.first << ' ' << t.second << '\n';
  for (int i = 1; i <= q; i++) cout << k[i] << ' ';
  return 0;
}