#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

int n, t, l, r, a[1000009], f_min[1000009][30], f_max[1000009][30];

int main() {
//    freopen("/Users/meizhenchen/Desktop/data/9.in", "rt", stdin);
//    freopen("/Users/meizhenchen/Desktop/data/9.out", "wt", stdout);
    cin >> t >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        f_min[i][0] = f_max[i][0] = a[i];
    }
    for (int j = 1; j <= log2(n); j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f_min[i][j] = min(f_min[i][j - 1], f_min[i + (1 << (j - 1))][j - 1]);
            f_max[i][j] = max(f_max[i][j - 1], f_max[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 1; i <= t; i++) {
        cin >> l >> r;
        if (l > r) {
            swap(l, r);
        }
        int k = log2(r - l + 1);
        cout << min(f_min[l][k], f_min[r - (1 << k) + 1][k]) << " "
        << max(f_max[l][k], f_max[r - (1 << k) + 1][k]) << endl;
    }
}