/** VanhG **/ #include <bits/stdc++.h> using namespace std; //#include <ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; #define ll long long #define ld long double #define ii pair<int, int> #define tkn "va" #define X first #define Y second #define FORU(i, a, b) for (int i = a; i <= b; i++) #define FFOR(i, a, b) for (int i = a; i < b; i++) #define FORD(i, a, b) for (int i = a; i >= b; i--) mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll Rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } const int N = 1e5 + 7; const int M = 6e6 + 3; const int base = 1e9 + 7; const ll mod = 1e9 + 9; const int logmax = 25; ll n, m, a[N]; void input() { cin >> n >> m; FORU(i, 1, m) cin >> a[i]; } void init() {} struct trie { int fi; int a[2]; int& operator[](int i) { return a[i]; } trie() { a[0] = a[1] = 0; fi = 0; } }; vector<trie> c; int getbit(ll x, int i) { return (x >> i) & 1; } void add(ll x) { int pos = 0, bit; FORD(i, 63, 0) { bit = getbit(x, i); if (!c[pos][bit]) { c.push_back(trie()); c[pos][bit] = c.size() - 1; } c[pos].fi++; pos = c[pos][bit]; } c[pos].fi++; } ll sum(ll x) { return (n - 1 + x) * (n - x) / 2; } ll get_pos(ll x) { ll res = 0, pos = 0, bit; FORD(i, 63, 0) { bit = getbit(x, i); if (bit == 1 && c[pos][0]) res += c[c[pos][0]].fi; if (!c[pos][bit]) return res; pos = c[pos][bit]; } // cout << x << " " << res<< '\n'; return res + 1; } ll real_pos(ll x) { ll lo = 1, hi = n * (n - 1) / 2, res = 1; while (lo <= hi) { ll mid = (lo + hi) >> 1; ll ad = get_pos(mid); if (x + ad <= mid) { res = mid; hi = mid - 1; } else lo = mid + 1; } return res; } void get_res(ll x) { ll lo = 1, hi = n - 1, res = 0; while (lo <= hi) { ll mid = (lo + hi) / 2; if (sum(n - mid) < x) { res = mid; lo = mid + 1; } else hi = mid - 1; } ll ad = x - sum(n - res); // cout << '\n' << x << " "<< res <<" " << ad << '\n'; cout << res + 1 << " " << res + ad + 1 << '\n'; } void sub2() { c.push_back(trie()); // add(3); // cout << real_pos(3); FORU(i, 1, m) { ll pos = real_pos(a[i]); get_res(pos); add(pos); } } void sol() { // if (n <= 500) sub1(); // else sub2(); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen(tkn".inp","r", stdin); // freopen(tkn".out", "w", stdout); input(); init(); sol(); return 0; }