#include <bits/stdc++.h>

using namespace std;

ifstream f("rmq.in");
ofstream g("rmq.out");

int n, m, x, y;
int sparseTable[100001][20];

vector < int > v;

int main() {
  f >> n >> m;
  v.resize(n);
  for (auto &element : v) {
    f >> element;
  }

  for (int i = 0; i < n; ++i) {
    sparseTable[i][0] = i;
  }

  // preprocesare
  for (int j = 1; (1 << j) <= n; ++j) {
    for (int i = 0; (i + (1 << j) - 1) < n; ++i) {
      if (v[sparseTable[i][j - 1]] < v[sparseTable[i + (1 << (j - 1))][j - 1]]) {
        sparseTable[i][j] = sparseTable[i][j - 1];
      }
      else {
        sparseTable[i][j] = sparseTable[i + (1 << (j - 1))][j - 1];
      }
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cout << sparseTable[i][j] << " ";
    }
    cout << '\n';
  }

  // query
  for (int i = 0; i < m; ++i) {
    f >> x >> y;
    if (x > y) swap(x, y);
    --x;
    --y;
    int j = (int)log2(y - x + 1);
    if (v[sparseTable[x][j]] <= v[sparseTable[y - (1 << j) + 1][j]]) {
      g << v[sparseTable[x][j]] << '\n';
    }
    else {
      g << v[sparseTable[y - (1 << j) + 1][j]] << '\n';
    }
  }
}