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;
template <typename T>
inline void ckmax(T& x, T y) {
  x = (y > x ? y : x);
}
template <typename T>
inline void ckmin(T& x, T y) {
  x = (y < x ? y : x);
}
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
  if (S == T) {
    T = (S = buf) + fread(buf, 1, SIZE, stdin);
    if (S == T) return '\n';
  }
  return *S++;
}
}  // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
  fwrite(buf, 1, S - buf, stdout);
  S = buf;
}
inline void putchar(char c) {
  *S++ = c;
  if (S == T) flush();
}
struct NTR {
  ~NTR() { flush(); }
} ztr;
}  // namespace Fwrite
namespace Fastio {
struct Reader {
  template <typename T>
  Reader& operator>>(T& x) {
    char c = Fread ::getchar();
    T f = 1;
    while (c < '0' || c > '9') {
      if (c == '-') f = -1;
      c = Fread ::getchar();
    }
    x = 0;
    while (c >= '0' && c <= '9') {
      x = x * 10 + (c - '0');
      c = Fread ::getchar();
    }
    x *= f;
    return *this;
  }
  Reader& operator>>(char& c) {
    c = Fread ::getchar();
    while (c == '\n' || c == ' ') c = Fread ::getchar();
    return *this;
  }
  Reader& operator>>(char* str) {
    int len = 0;
    char c = Fread ::getchar();
    while (c == '\n' || c == ' ') c = Fread ::getchar();
    while (c != '\n' && c != ' ') {
      str[len++] = c;
      c = Fread ::getchar();
    }
    str[len] = '\0';
    return *this;
  }
  Reader() {}
} cin;
const char endl = '\n';
struct Writer {
  template <typename T>
  Writer& operator<<(T x) {
    if (x == 0) {
      Fwrite ::putchar('0');
      return *this;
    }
    if (x < 0) {
      Fwrite ::putchar('-');
      x = -x;
    }
    static int sta[45];
    int top = 0;
    while (x) {
      sta[++top] = x % 10;
      x /= 10;
    }
    while (top) {
      Fwrite ::putchar(sta[top] + '0');
      --top;
    }
    return *this;
  }
  Writer& operator<<(char c) {
    Fwrite ::putchar(c);
    return *this;
  }
  Writer& operator<<(char* str) {
    int cur = 0;
    while (str[cur]) Fwrite ::putchar(str[cur++]);
    return *this;
  }
  Writer& operator<<(const char* str) {
    int cur = 0;
    while (str[cur]) Fwrite ::putchar(str[cur++]);
    return *this;
  }
  Writer() {}
} cout;
}  // namespace Fastio
const int MAXN = 1 << 12;
const int MAXQ = 1 << 16;
const int BLOCK_SIZE = 1 << 8, BLOCK_NUM = MAXN / BLOCK_SIZE;
const int MAXOP = 2200000;
int n, q, a[MAXN + 5];
pair<int, int> qs[MAXQ + 5];
int ans[MAXQ + 5];
int cnt_block, bel[MAXN + 5];
int cnt_set;
pair<int, int> op[MAXOP + 5];
int merge(int s1, int s2) {
  op[++cnt_set] = make_pair(s1, s2);
  return cnt_set;
}
struct PresidentTree {
  int rt[BLOCK_SIZE + 5];
  int sum[(BLOCK_SIZE * 20) + 5];
  int ls[(BLOCK_SIZE * 20) + 5], rs[(BLOCK_SIZE * 20) + 5], cnt;
  void insert(int& x, int y, int l, int r, int pos) {
    x = ++cnt;
    sum[x] = sum[y] + 1;
    ls[x] = ls[y];
    rs[x] = rs[y];
    if (l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
      insert(ls[x], ls[y], l, mid, pos);
    } else {
      insert(rs[x], rs[y], mid + 1, r, pos);
    }
  }
  int _find_nxt(int x, int y, int l, int r) {
    if (l == r) {
      return l;
    }
    int mid = (l + r) >> 1;
    if (sum[ls[x]] - sum[ls[y]]) {
      return _find_nxt(ls[x], ls[y], l, mid);
    } else {
      return _find_nxt(rs[x], rs[y], mid + 1, r);
    }
  }
  int find_nxt(int x, int y, int l, int r, int st) {
    if (!x || sum[x] - sum[y] == 0) {
      return 1000000000;
    }
    if (l >= st) {
      return _find_nxt(x, y, l, r);
    }
    assert(r >= st);
    int mid = (l + r) >> 1;
    if (st > mid || sum[ls[x]] - sum[ls[y]] == 0) {
      return find_nxt(rs[x], rs[y], mid + 1, r, st);
    }
    int res;
    res = find_nxt(ls[x], ls[y], l, mid, st);
    if (res != 1000000000) return res;
    return find_nxt(rs[x], rs[y], mid + 1, r, st);
  }
  int _find_pre(int x, int y, int l, int r) {
    if (l == r) {
      return l;
    }
    int mid = (l + r) >> 1;
    if (sum[rs[x]] - sum[rs[y]]) {
      return _find_pre(rs[x], rs[y], mid + 1, r);
    } else {
      return _find_pre(ls[x], ls[y], l, mid);
    }
  }
  int find_pre(int x, int y, int l, int r, int ed) {
    if (!x || sum[x] - sum[y] == 0) {
      return 0;
    }
    if (r <= ed) {
      return _find_pre(x, y, l, r);
    }
    assert(l <= ed);
    int mid = (l + r) >> 1;
    if (ed <= mid || sum[rs[x]] - sum[rs[y]] == 0) {
      return find_pre(ls[x], ls[y], l, mid, ed);
    }
    int res;
    res = find_pre(rs[x], rs[y], mid + 1, r, ed);
    if (res != 0) return res;
    return find_pre(ls[x], ls[y], l, mid, ed);
  }
  void clear(int len) {
    cnt = 0;
    for (int i = 1; i <= len; ++i) {
      rt[i] = 0;
    }
  }
  PresidentTree() {}
} T;
int rev[MAXN + 5];
struct Block {
  int L, R;
  int pos[BLOCK_SIZE + 5], cnt_pos;
  int res[BLOCK_SIZE + 5][BLOCK_SIZE + 5];
  int tmp_res[BLOCK_SIZE + 5][BLOCK_SIZE + 5];
  void solve(int l, int r, const vector<int>& p) {
    assert(((int)(p).size()) == r - l + 1);
    if (l == r) {
      res[p[0]][p[0]] = pos[p[0]];
      return;
    }
    int mid = (l + r) >> 1;
    vector<int> pl, pr;
    for (int _i = 0; _i < ((int)(p).size()); ++_i) {
      int i = p[_i];
      assert(a[pos[i]] >= l + L - 1 && a[pos[i]] <= r + L - 1);
      if (a[pos[i]] <= mid + L - 1) {
        pl.push_back(i);
      } else {
        pr.push_back(i);
      }
    }
    solve(l, mid, pl);
    solve(mid + 1, r, pr);
    for (int _i = 0; _i < ((int)(p).size()); ++_i) {
      int i = p[_i];
      for (int _j = _i; _j < ((int)(p).size()); ++_j) {
        int j = p[_j];
        tmp_res[i][j] = res[i][j];
      }
    }
    for (int _i = 0; _i < ((int)(p).size()); ++_i) {
      int i = p[_i];
      for (int _j = _i; _j < ((int)(p).size()); ++_j) {
        int j = p[_j];
        if (a[pos[i]] <= mid + L - 1 && a[pos[j]] <= mid + L - 1) {
          int x = T.find_nxt(T.rt[r], T.rt[mid], 1, cnt_pos, i);
          int y = T.find_pre(T.rt[r], T.rt[mid], 1, cnt_pos, j);
          if (x <= y) {
            res[i][j] = merge(tmp_res[i][j], tmp_res[x][y]);
          }
        } else if (a[pos[i]] > mid + L - 1 && a[pos[j]] > mid + L - 1) {
          int x = T.find_nxt(T.rt[mid], T.rt[l - 1], 1, cnt_pos, i);
          int y = T.find_pre(T.rt[mid], T.rt[l - 1], 1, cnt_pos, j);
          if (x <= y) {
            res[i][j] = merge(tmp_res[x][y], tmp_res[i][j]);
          }
        } else if (a[pos[i]] <= mid + L - 1 && a[pos[j]] > mid + L - 1) {
          int x = T.find_nxt(T.rt[r], T.rt[mid], 1, cnt_pos, i);
          assert(x <= j);
          int y = T.find_pre(T.rt[mid], T.rt[l - 1], 1, cnt_pos, j);
          assert(y >= i);
          res[i][j] = merge(tmp_res[i][y], tmp_res[x][j]);
        } else if (a[pos[i]] > mid + L - 1 && a[pos[j]] <= mid + L - 1) {
          int x = T.find_nxt(T.rt[mid], T.rt[l - 1], 1, cnt_pos, i);
          assert(x <= j);
          int y = T.find_pre(T.rt[r], T.rt[mid], 1, cnt_pos, j);
          assert(y >= i);
          res[i][j] = merge(tmp_res[x][j], tmp_res[i][y]);
        }
      }
    }
  }
  void build(int _L, int _R) {
    L = _L;
    R = _R;
    cnt_pos = 0;
    for (int i = 1; i <= n; ++i) {
      if (a[i] >= L && a[i] <= R) {
        pos[++cnt_pos] = i;
        rev[a[i]] = cnt_pos;
      }
    }
    assert(cnt_pos == R - L + 1);
    for (int i = L; i <= R; ++i) {
      int v = i - L + 1;
      T.rt[v] = T.rt[v - 1];
      T.insert(T.rt[v], T.rt[v], 1, cnt_pos, rev[i]);
    }
    vector<int> p;
    for (int i = 1; i <= cnt_pos; ++i) {
      p.push_back(i);
    }
    solve(1, cnt_pos, p);
    T.clear(cnt_pos);
  }
  int query(int l, int r) {
    int x = lower_bound(pos + 1, pos + cnt_pos + 1, l) - pos;
    int y = upper_bound(pos + 1, pos + cnt_pos + 1, r) - pos - 1;
    if (x > y) return 0;
    return res[x][y];
  }
  Block() {}
} blo[BLOCK_NUM + 5];
int main() {
  Fastio ::cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    Fastio ::cin >> a[i];
  }
  cnt_set = n;
  for (int i = 1; i <= n; i += BLOCK_SIZE) {
    int j = min(i + BLOCK_SIZE - 1, n);
    ++cnt_block;
    for (int k = i; k <= j; ++k) {
      bel[k] = cnt_block;
    }
    blo[cnt_block].build(i, j);
  }
  for (int i = 1; i <= q; ++i) {
    Fastio ::cin >> qs[i].first >> qs[i].second;
    int l = qs[i].first, r = qs[i].second;
    ans[i] = 0;
    for (int b = 1; b <= cnt_block; ++b) {
      int s = blo[b].query(l, r);
      if (!s) continue;
      if (!ans[i]) {
        ans[i] = s;
      } else {
        ans[i] = merge(ans[i], s);
      }
    }
  }
  Fastio ::cout << cnt_set << Fastio ::endl;
  for (int i = n + 1; i <= cnt_set; ++i) {
    Fastio ::cout << op[i].first << " " << op[i].second << Fastio ::endl;
  }
  for (int i = 1; i <= q; ++i) {
    Fastio ::cout << ans[i] << " \n"[i == q];
  }
  return 0;
}