#include <bits/stdc++.h> using namespace std; const int nmax = 1e5 + 5; const int inf = 1e9 + 9; int n, m, q, h[nmax], HeightMax[4 * nmax], lazy[4 * nmax]; void Push(int i) { lazy[i * 2] += lazy[i]; lazy[i * 2 + 1] += lazy[i]; HeightMax[i * 2] += lazy[i]; HeightMax[i * 2 + 1] += lazy[i]; lazy[i] = 0; } void build(int i, int l, int r) { if (l == r) return void(HeightMax[i] = h[l]); int mid = (l + r) >> 1; build(i * 2, l, mid); build(i * 2 + 1, mid + 1, r); HeightMax[i] = max(HeightMax[i * 2], HeightMax[i * 2 + 1]); } void Update(int i, int l, int r, int u, int v) { if (l > v || r < u) return; if (l >= u && r <= v) { lazy[i]++; HeightMax[i]++; return; } int mid = (l + r) >> 1; Push(i); Update(i * 2, l, mid, u, v); Update(i * 2 + 1, mid + 1, r, u, v); HeightMax[i] = max(HeightMax[i * 2], HeightMax[i * 2 + 1]); } int get(int i, int l, int r, int u, int v) { if (l > v || r < u) return -inf; if (l >= u && r <= v) return HeightMax[i]; int mid = (l + r) >> 1; Push(i); int L = get(i * 2, l, mid, u, v); int R = get(i * 2 + 1, mid + 1, r, u, v); return max(L, R); } void update(int u, int v) { Update(1, 1, n, u, v); } int GetMax(int u, int v) { return get(1, 1, n, u, v); } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m >> q; for (int i = 1; i <= n; ++i) cin >> h[i]; build(1, 1, n); while (m--) { int u, v; cin >> u >> v; update(u, v); } while (q--) { int u, v; cin >> u >> v; cout << GetMax(u, v) << ' '; } return 0; }