/**
 *    author:  tourist
 *    created: 16.09.2022 16:14:15       
**/
#undef _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n;
  cin >> n;
  vector<vector<int>> at(n + 1);
  for (long long x = 2; x <= n; x++) {
    at[x].push_back(x);
  }
  for (long long x = 2; x * x * (x + 1) <= n; x++) {
    for (long long z = 0; z < x; z++) {
      if (__gcd(x, z) == 1) {
        for (long long k = x + 1; (x * x + z) * k <= n; k++) {
          at[(x * x + z) * k].push_back(x * k);
        }
      }
    }
  }
  for (long long k = 1; k * k <= n; k++) {
    function<void(long long, long long, int)> Dfs = [&](long long a, long long b, int steps) {
      if (b % k != 0 && a * b > n) {
        return;
      }
      if (a % k != 0 && a * a * b > n) {
        return;
      }
      if (a != b && __gcd(a, b) == k && steps > 3) {
        at[a].push_back(b);
      }
      for (long long r = 0; r < a; r++) {
        if (a * b + r > n) {
          break;
        }
        Dfs(a * b + r, a, steps + 1);
      }
    };
    for (long long x = 1; x < k; x++) {
      if (x * x * x * k * k > n) {
        break;
      }
      Dfs(x, k, 1);
    }
  }
  vector<pair<int, int>> all;
  for (int i = 1; i <= n; i++) {
    sort(at[i].begin(), at[i].end());
    for (int j : at[i]) {
      all.emplace_back(i, j);
    }
  }
  int tt;
  cin >> tt;
  while (tt--) {
    long long id;
    cin >> id;
    --id;
    if (0 <= id && id < (int) all.size()) {
      cout << all[id].first << " " << all[id].second << '\n';
    } else {
      cout << -1 << " " << -1 << '\n';
    }
  }
  return 0;
}
