#define _USE_MATH_DEFINES #include using namespace std; vector order; struct Comp { bool operator() (const pair& x, const pair& y) const { if (x.first != y.first) return x.first < y.first; return order[x.second] < order[y.second]; } }; signed main() { ios::sync_with_stdio(false); cin.tie(0); int n, k1, k2; cin >> n >> k1 >> k2; order = vector(n + 1); order[k1] = 0; order[k2] = 1; if (k2 > k1) { int c = 2; for (int i = k1 - 1; i >= 1; i--) { order[i] = c; c += 2; } c = 3; for (int i = k2 + 1; i <= n; i++) { order[i] = c; c += 2; } } else { int c = 2; for (int i = k1 + 1; i <= n; i++) { order[i] = c; c += 2; } c = 3; for (int i = k2 - 1; i >= 1; i--) { order[i] = c; c += 2; } } set, Comp> available; vector occupy(n + 5); auto whenCome = [&] (int idx) { occupy[idx] = true; available.erase(make_pair(0, idx)); available.erase(make_pair(1, idx)); if (idx - 1 >= 1 && !occupy[idx - 1]) { available.erase(make_pair(0, idx - 1)); available.insert(make_pair(1, idx - 1)); } if (idx + 1 <= n && !occupy[idx + 1]) { available.erase(make_pair(0, idx + 1)); available.insert(make_pair(1, idx + 1)); } }; auto whenLeave = [&] (int idx) { occupy[idx] = false; if (!occupy[idx - 1] && !occupy[idx + 1]) available.insert(make_pair(0, idx)); else available.insert(make_pair(1, idx)); if (!occupy[idx - 1]) { if (idx - 1 >= 1 && !occupy[idx - 2]) { available.erase(make_pair(1, idx - 1)); available.insert(make_pair(0, idx - 1)); } } if (!occupy[idx + 1]) { if (idx + 1 <= n && !occupy[idx + 2]) { available.erase(make_pair(1, idx + 1)); available.insert(make_pair(0, idx + 1)); } } }; auto come = [&] () { if (available.empty()) return -1; int idx = available.begin()->second; whenCome(idx); return idx; }; for (int i = 1; i <= n; i++) available.insert(make_pair(0, i)); int q; cin >> q; vector a(q), b(q); for (int i = 0; i < q; i++) cin >> a[i] >> b[i]; { priority_queue, greater> que; for (int i = 0; i < q; i++) { while (!que.empty() && que.top() <= a[i]) que.pop(); if ((int) que.size() < n) { que.push(a[i] + b[i]); continue; } long long mx = que.top(); while (!que.empty() && que.top() <= mx) que.pop(); a[i] = mx; que.push(a[i] + b[i]); } } priority_queue, vector>, greater>> que; vector ans(q); for (int i = 0; i < q; i++) { while (!que.empty() && que.top().first <= a[i]) { int p = que.top().second; que.pop(); whenLeave(ans[p]); } int idx = come(); ans[i] = idx; que.emplace(a[i] + b[i], i); } for (auto& x : ans) cout << x << '\n'; return 0; }