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;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
int f, qr;
char getc() {
  return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                      (iS == iT ? EOF : *iS++))
                   : *iS++);
}
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
template <class I>
inline void gi(I &x) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-') f = -1;
  for (x = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = x * 10 + (c & 15);
  x *= f;
}
template <class I>
inline void print(I x) {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = -x;
  while (x) qu[++qr] = x % 10 + '0', x /= 10;
  while (qr) putc(qu[qr--]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::getc;
using io ::gi;
using io ::print;
using io ::putc;
template <class T>
void upmax(T &x, T y) {
  x = x > y ? x : y;
}
template <class T>
void upmin(T &x, T y) {
  x = x < y ? x : y;
}
const int N = 1 << 12, Q = 1 << 16;
const unsigned long long P1 = 180143985094819841, P2 = 1945555039024054273;
template <>
struct std::hash<pair<int, int>> {
  unsigned long long operator()(pair<int, int> p) const {
    return (unsigned long long)p.first * P1 + (unsigned long long)p.second * P2;
  }
};
unsigned long long _hash_mask =
    std::chrono::steady_clock::now().time_since_epoch().count();
template <class T, class Hash>
struct safe_hash {
  unsigned long long operator()(const T &x) const {
    return Hash()(x) ^ _hash_mask;
  }
};
template <class T, class Hash = std::hash<T>>
using safe_unordered_set = std::unordered_set<T, safe_hash<T, std::hash<T>>>;
template <class Kt, class Vt, class Hash = std::hash<Kt>>
using safe_unordered_map =
    std::unordered_map<Kt, Vt, safe_hash<Kt, std::hash<Kt>>>;
int a[N], res[Q], pos[N];
safe_unordered_map<pair<int, int>, int> tr[N << 2];
vector<int> p[N << 2], suml[N << 2];
pair<int, int> op[2200005];
int oc = 0, cnt;
void build(int x, int l, int r) {
  if (l + 1 == r) return;
  int mid = (l + r) >> 1;
  suml[x].resize(r - l);
  p[x << 1].reserve(mid - l), p[x << 1 | 1].reserve(r - mid);
  suml[x][0] = p[x][0] < mid;
  if (p[x][0] < mid)
    p[x << 1].push_back(p[x][0]);
  else
    p[x << 1 | 1].push_back(p[x][0]);
  for (int i = 1; i < r - l; i++) {
    suml[x][i] = suml[x][i - 1] + int(p[x][i] < mid);
    if (p[x][i] < mid)
      p[x << 1].push_back(p[x][i]);
    else
      p[x << 1 | 1].push_back(p[x][i]);
  }
  build(x << 1, l, mid);
  build(x << 1 | 1, mid, r);
}
int query(int x, int l, int r, int ql, int qr) {
  if (l + 1 == r) return pos[p[x][0]];
  int &res = tr[x][{ql, qr}];
  assert(ql < r - l && qr <= r - l);
  if (res) return res;
  int mid = (l + r) >> 1;
  int l0 = ql == 0 ? 0 : suml[x][ql - 1], r0 = suml[x][qr - 1];
  int l1 = ql == 0 ? 0 : ql - suml[x][ql - 1], r1 = qr - suml[x][qr - 1];
  if (l0 == r0) return query(x << 1 | 1, mid, r, l1, r1);
  if (l1 == r1) return query(x << 1, l, mid, l0, r0);
  op[++oc] = {query(x << 1, l, mid, l0, r0), query(x << 1 | 1, mid, r, l1, r1)};
  return res = ++cnt;
}
int main() {
  int n, q;
  gi(n);
  gi(q);
  for (int i = 0; i < n; i++) gi(a[i]), --a[i], pos[a[i]] = i + 1;
  p[1].resize(n);
  copy(a, a + n, p[1].begin());
  build(1, 0, n);
  cnt = n;
  for (int i = 0; i < q; i++) {
    int l, r;
    gi(l);
    gi(r);
    --l;
    res[i] = query(1, 0, n, l, r);
  }
  print(oc + n);
  putc('\n');
  for (int i = 1; i <= oc; i++)
    print(op[i].first), putc(' '), print(op[i].second), putc('\n');
  for (int i = 0; i < q; i++) print(res[i]), putc(' ');
  putc('\n');
  return 0;
}