// hacky solution binary searching the slope (using double) // probably will TLE if the pragmas below don't work // O(60 Q m) complexity #include #include #include using namespace std; #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,sse4,abm,avx,avx2") namespace { #define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i) #define RARA(i, a, b) for (ll i = a, __##i = b; i > __##i; --i) #define VERA(x, seq) for (auto &x : seq) #define SIZE(x) ((ll)(x.size())) #define ALL(x) x.begin(), x.end() typedef long long ll; typedef double dd; ll __gcd(ll a, ll b) { if (b < a) swap(a, b) ; if (a == 0) return b ; return __gcd(b % a, a) ; } unordered_map memo, memo2; ll Calc2(dd mid, ll rows, ll cols) { auto& cnt = memo2[mid]; if (cnt > 0) return cnt; // mid*c+1 >= rows // c >= (rows-1)/mid const ll lim = min(cols, (ll) std::ceil((rows - 1) / mid)); cnt = (cols - lim) * rows + max(ll(0), lim - 1); for (int c = 1; c < (int) lim; ++c) { // r <= mid * c // r < mid*c+1 cnt += (ll) std::floor(mid * c); } // VEVE(c, 1, cols) { // cnt += min(rows, (ll) std::floor(mid * c + 1)); // } return cnt; } ll Calc(dd mid, ll rows, ll cols) { if (mid < 1 - 1e-13) { ll cnt = Calc2(1.0 / mid + 1e-13, cols, rows); cnt = rows * cols - 1 - cnt; return cnt; } auto& cnt = memo[mid]; if (cnt > 0) return cnt; // ll cnt = 0; // mid*c+1 >= rows // c >= (rows-1)/mid const ll lim = min(cols, (ll) std::ceil((rows - 1) / mid)); cnt = (cols - lim) * rows + max(ll(0), lim - 1); for (int c = 1; c < (int) lim; ++c) { // r <= mid * c // r < mid*c+1 cnt += (ll) std::floor(mid * c); } // VEVE(c, 1, cols) { // cnt += min(rows, (ll) std::floor(mid * c + 1)); // } return cnt; } void Solve(ll) { ll rows, cols, ques; cin >> rows >> cols >> ques; memo.reserve(200 * ques); memo2.reserve(200 * ques); VEVE(_, 0, ques) { ll rank; cin >> rank; if (rank > rows * (cols - 1)) { // vertical cout << (rank - rows * (cols - 1) + 1) << " 1\n"; continue; } // non-vertical // order (r/c) (1 <= c < cols; 0 <= r < rows dd low = 0, hig = rows - 1; VEVE(its, 0, 60) { if (hig - low < 1e-12) break; const dd mid = (low + hig) / 2.0; const ll cnt = Calc(mid, rows, cols); if (cnt >= rank) { hig = mid; } else { low = mid; } } ll best_num = 0, best_den = 1; /*const ll lim = min(cols, (ll) std::ceil((rows - 1) / hig)); const ll cnt = Calc(hig, rows, cols); VEVE(c, 1, lim) { const ll num = (ll) std::floor(hig * c); if (num * best_den >= best_num * c) { best_num = num; best_den = c; } } if (lim < cols and (rows - 1) <= lim * hig) { best_num = rows - 1; best_den = lim; }*/ ll cnt = 0; VEVE(c, 1, cols) { const ll num = min(rows - 1, (ll) std::floor(hig * c)); cnt += num + 1; if (num * best_den >= best_num * c) { best_num = num; best_den = c; } } // DEBUG(rank, cnt, cnt - rank); const ll gcd = __gcd(best_num, best_den); const ll row = best_num - (best_num / gcd) * (cnt - rank) + 1; const ll col = best_den - (best_den / gcd) * (cnt - rank) + 1; cout << row << ' ' << col << endl; } } void Init() { ios::sync_with_stdio(false); cin.tie(nullptr); } } int main() { #ifdef AZN freopen("input.txt", "r", stdin); #endif Init(); ll tests = 1; VEVE(test, 1, tests + 1) Solve(test); return 0; }