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>
#pragma GCC optimize("Ofast")
using std::array;
using std::cin;
using std::cout;
using std::endl;
using std::lower_bound;
using std::prev;
using std::streambuf;
using std::tuple;
using std::upper_bound;
using std::vector;
const auto fast = (cin.tie(0), cout.tie(0), std::ios::sync_with_stdio(0));
constexpr int maxn = 1 << 12 | 1, maxm = 1 << 4 | 1, maxp = 1 << 8 | 1,
              maxq = 1 << 16 | 1, blkSiz = 1 << 8;
inline void read(char& c) {
  static const int len = 1 << 22;
  static char buf[len], *st = buf, *ed = buf;
  static streambuf* in = cin.rdbuf();
  if (st == ed) ed = (st = buf) + in->sgetn(buf, len);
  c = *st++;
  return;
}
template <class T>
inline void read(T& x) {
  static char c;
  x = 0, read(c);
  while (isspace(c)) read(c);
  while (isdigit(c)) x = x * 10 + c - '0', read(c);
  return;
}
template <class T, class... Args>
void read(T& x, Args&... args) {
  return read(x), read(args...);
}
inline void write(const char& c) {
  static streambuf* out = cout.rdbuf();
  out->sputc(c);
  return;
}
template <class T>
inline void write(const T& x) {
  static const int len = 22;
  static char buf[len], *st = buf, *ed = buf;
  if (!x) write('0');
  for (int c = x; c; c /= 10) *st++ = c % 10 + '0';
  while (st != ed) write(*--st);
  return;
}
template <class T, class... Args>
void write(const T& x, const Args&... args) {
  return write(x), write(args...);
}
array<int, maxq> ans;
array<int, maxn> arr, blk;
int n, m, q, l, r, setCnt, base;
array<int, maxm> st, ed, cnt;
vector<tuple<int, int>> add;
array<vector<int>, maxm> pos;
array<array<int, maxp>, maxp> sub;
array<int, maxp> lPre, rPre, lNxt, rNxt;
array<array<array<int, maxp>, maxp>, maxm> set;
inline int merge(int x, int y) {
  return (x && y) ? (add.emplace_back(x, y), ++setCnt) : (x | y);
}
void build(int blk, int st, int ed, const vector<int>& que) {
  if (ed - st == 1)
    set[blk][que.front()][que.front()] = pos[blk][que.front()] + 1;
  else {
    int mid = (st + ed) >> 1;
    vector<int> lQue, rQue;
    for (int x : que)
      (arr[pos[blk][x]] < base + mid) ? lQue.emplace_back(x)
                                      : rQue.emplace_back(x);
    build(blk, st, mid, lQue), build(blk, mid, ed, rQue);
    for (auto it = que.begin(); it != que.end(); it++)
      if (arr[pos[blk][*it]] < base + mid)
        lPre[it - que.begin()] = it - que.begin(),
                  rPre[it - que.begin()] =
                      (it == que.begin() ? -1 : rPre[prev(it) - que.begin()]);
      else
        rPre[it - que.begin()] = it - que.begin(),
                  lPre[it - que.begin()] =
                      (it == que.begin() ? -1 : lPre[prev(it) - que.begin()]);
    for (auto it = que.rbegin(); it != que.rend(); it++)
      if (arr[pos[blk][*it]] < base + mid)
        lNxt[que.rend() - it - 1] = que.rend() - it - 1,
                               rNxt[que.rend() - it - 1] =
                                   (it == que.rbegin()
                                        ? que.size()
                                        : rNxt[que.rend() - prev(it) - 1]);
      else
        rNxt[que.rend() - it - 1] = que.rend() - it - 1,
                               lNxt[que.rend() - it - 1] =
                                   (it == que.rbegin()
                                        ? que.size()
                                        : lNxt[que.rend() - prev(it) - 1]);
    for (int x = 0; x < que.size(); x++)
      for (int y = x; y < que.size(); y++)
        sub[que[x]][que[y]] = set[blk][que[x]][que[y]];
    for (int x = 0; x < que.size(); x++)
      for (int y = x; y < que.size(); y++)
        if (arr[pos[blk][que[x]]] < base + mid)
          if (arr[pos[blk][que[y]]] < base + mid)
            set[blk][que[x]][que[y]] =
                (rNxt[x] <= rPre[y]) ? merge(sub[que[x]][que[y]],
                                             sub[que[rNxt[x]]][que[rPre[y]]])
                                     : sub[que[x]][que[y]];
          else
            set[blk][que[x]][que[y]] =
                merge(sub[que[x]][que[lPre[y]]], sub[que[rNxt[x]]][que[y]]);
        else if (arr[pos[blk][que[y]]] < base + mid)
          set[blk][que[x]][que[y]] =
              merge(sub[que[lNxt[x]]][que[y]], sub[que[x]][que[rPre[y]]]);
        else
          set[blk][que[x]][que[y]] =
              (lNxt[x] <= lPre[y])
                  ? merge(sub[que[lNxt[x]]][que[lPre[y]]], sub[que[x]][que[y]])
                  : sub[que[x]][que[y]];
  }
  return;
}
int query(int blk, int l, int r) {
  auto x = lower_bound(pos[blk].begin(), pos[blk].end(), l),
       y = prev(upper_bound(pos[blk].begin(), pos[blk].end(), r));
  return x <= y ? set[blk][x - pos[blk].begin()][y - pos[blk].begin()] : 0;
}
int main() {
  read(n, q), setCnt = n;
  for (int i = 0; i < n; i++) read(arr[i]), --arr[i];
  for (int i = 0; i < n; i++) blk[i] = i / blkSiz;
  for (int i = 1; i < n; i++)
    if (blk[i] != blk[i - 1]) st[blk[i]] = i, ed[blk[i - 1]] = i - 1;
  ed[m = blk[n - 1]] = n - 1;
  for (int i = 0; i <= m; i++) {
    vector<int> que;
    for (int j = 0; j < n; j++)
      if (st[i] <= arr[j] && arr[j] <= ed[i])
        pos[i].emplace_back(j), que.emplace_back(cnt[i]++);
    base = st[i], build(i, 0, cnt[i], que);
  }
  for (int i = 1; i <= q; i++) {
    read(l, r), --l, --r;
    for (int j = 0; j <= m; j++) ans[i] = merge(ans[i], query(j, l, r));
  }
  write(setCnt, '\n');
  for (auto&& [x, y] : add) write(x, ' ', y, '\n');
  for (int i = 1; i <= q; i++) write(ans[i], i == q ? '\n' : ' ');
  return 0;
}