#include <bits/stdc++.h>
using namespace std;
#define file "a"
// #define int long long   
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define pf push_front
#define sz(a) (int)a.size()
#define mask(i) (1 << (int)(i))
const int N = 2e5, mod = 1e9 + 7, inf = 1e9, K = __lg(N);
void add(int &a, int b) { a += b; if (a >= mod) a -= mod; }
void MIN(int &a, int b) { a = min(a, b); }
int n, q;
int mx[N + 2][K + 2], lg[N + 2], mn[N + 2][K + 2], g[N + 2][K + 2];
int getmax(int l, int r)
{
  int k = lg[r - l + 1];
  return max(mx[l][k], mx[r - mask(k) + 1][k]);
}
int getmin(int l, int r)
{
  int k = lg[r - l + 1];
  return min(mn[l][k], mn[r - mask(k) + 1][k]);
}
int getgcd(int l, int r)
{
  int k = lg[r - l + 1];
  return __gcd(g[l][k], g[r - mask(k) + 1][k]);
}
signed main() 
{
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) 
  {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
  cin >> n >> q;
  for (int i = 1; i <= n; i++) 
    cin >> mx[i][0], mn[i][0] = g[i][0] = mx[i][0];
  lg[1] = 0;
  for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
  for (int j = 1; j <= lg[n]; j++) 
  for (int i = 1; i + mask(j) - 1 <= n; i++)
  {
    mx[i][j] = max(mx[i][j - 1], mx[i + mask(j - 1)][j - 1]);
    mn[i][j] = min(mn[i][j - 1], mn[i + mask(j - 1)][j - 1]);
    g[i][j] = __gcd(g[i][j - 1], g[i + mask(j - 1)][j - 1]);
  }
  while (q--)
  {
    int l, r;
    cin >> l >> r;
    cout << getmax(l, r) << " " << getmin(l, r) << "\n";
  }
}