#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } template struct SegmentTree { const Op op; const T idT; int n; vector ts; SegmentTree(int n_, const Op op, const T &idT) : op(op), idT(idT) { for (n = 1; n < n_; n <<= 1) {} ts.assign(n << 1, idT); } SegmentTree(const vector &ts_, const Op op, const T &idT) : op(op), idT(idT) { const int n_ = ts_.size(); for (n = 1; n < n_; n <<= 1) {} ts.assign(n << 1, idT); for (int a = 0; a < n_; ++a) ts[n + a] = ts_[a]; build(); } T &at(int a) { return ts[n + a]; } void build() { for (int a = n; --a; ) ts[a] = op(ts[a << 1], ts[a << 1 | 1]); } void set(int a, const T &val) { ts[a += n] = val; for (; a >>= 1; ) ts[a] = op(ts[a << 1], ts[a << 1 | 1]); } void mulL(int a, const T &val) { set(a, op(val, ts[a + n])); } void mulR(int a, const T &val) { set(a, op(ts[a + n], val)); } T query(int a, int b) const { T prodL = idT, prodR = idT; for (a += n, b += n; a < b; a >>= 1, b >>= 1) { if (a & 1) prodL = op(prodL, ts[a++]); if (b & 1) prodR = op(ts[--b], prodR); } return op(prodL, prodR); } // min b s.t. pred(prod of [a, b)) (or n + 1 if no such b) // 0 <= a <= n // assume pred(prod of [a, b)) is non-decreasing in b template int binarySearchR(int a, Pred pred) const { if (pred(idT)) return a; if (a == n) return n + 1; T prod = idT; for (a += n; ; a >>= 1) { if (a & 1) { if (pred(op(prod, ts[a]))) { for (; a < n; ) { a <<= 1; if (!pred(op(prod, ts[a]))) { prod = op(prod, ts[a++]); } } return a - n + 1; } prod = op(prod, ts[a++]); if (!(a & (a - 1))) return n + 1; } } } // max a s.t. pred(prod of [a, b)) (or -1 if no such a) // 0 <= b <= n // assume pred(prod of [a, b)) is non-increasing in a template int binarySearchL(int b, Pred pred) const { if (pred(idT)) return b; if (b == 0) return -1; T prod = idT; for (b += n; ; b >>= 1) { if ((b & 1) || b == 2) { if (pred(op(prod, ts[b - 1]))) { for (; b <= n; ) { b <<= 1; if (!pred(op(prod, ts[b - 1]))) { prod = op(prod, ts[--b]); } } return b - n - 1; } prod = op(prod, ts[--b]); if (!(b & (b - 1))) return -1; } } } }; constexpr Int INF = 1001001001001001001LL; // x -> max{x + c, d} struct Info { Int c, d; }; Info mul(const Info &t0, const Info &t1) { return Info{t0.c + t1.c, max(t0.d + t1.c, t1.d)}; } Int L; int N, Q; vector A; Int solveSlow(Int X, Int T) { // cerr<<"solveSlow "< *seg1, *seg0; void init() { seg1 = new SegmentTree(N + 1, mul, Info{0, -INF}); seg0 = new SegmentTree(N + 1, mul, Info{0, -INF}); for (int i = 0; i <= N; ++i) { const Int len = A[i + 1] - A[i]; seg1->at(i) = Info{((i & 1) ? +1 : -1) * len, 0}; seg0->at(i) = Info{((i & 1) ? -1 : +1) * len, 0}; } seg1->build(); seg0->build(); } Int solve(Int X, Int T) { // cerr<<"solve "<binarySearchR(i0, [&](const Info &t) { return (-max(-p + t.c, t.d) <= xp); }) - 1; // cerr<<" seg1 i = "<query(i0, i); const Int pp = -max(-p + t.c, t.d); chmin(ans, A[i] + (pp - xp) - T); } } { const int i = seg0->binarySearchR(i0, [&](const Info &t) { return (xq <= max(q + t.c, t.d)); }) - 1; // cerr<<" seg0 i = "<query(i0, i); const Int qq = max(q + t.c, t.d); chmin(ans, A[i] + (xq - qq) - T); } } return ans; } int main() { for (; ~scanf("%lld%d%d", &L, &N, &Q); ) { A.resize(N + 2); A[0] = 0; for (int i = 1; i <= N; ++i) { scanf("%lld", &A[i]); } A[N + 1] = A[N] + 2 * L; init(); Int ans = 0; for (; Q--; ) { Int b, c; scanf("%lld%lld", &b, &c); const Int x = (b + ans) % L; const Int t = (c + ans) % 1'000'000'000'000'000LL; ans = solve(x, t); printf("%lld\n", ans); #ifdef LOCAL const Int slw=solveSlow(x,t); if(slw!=ans){cerr<<"slw = "<