#include <bits/stdc++.h> using namespace std; #define int long long #define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--)) #define all(a) a.begin(), a.end() #define srtvc(a) sort(all(a)) #define bcsrtvc(a) sort(all(a), greater<__typeof__(a[0])>()) #define ppf pop_front #define ppb pop_back #define pf push_front #define pb push_back #define ef emplace_front #define eb emplace_back #define fr first #define sc second #define pq priority_queue #define pii pair<int, int> #define vc vector #define dq deque #define sz(a) a.size() #define mnto(x,y) x = min(x, (__typeof__(x))y) #define mxto(x,y) x = max(x, (__typeof__(x))y) #define setval(arr, x) memset(arr, x, sizeof(arr)) template<typename T> using vv = vc<vc<T>>; struct Segment { int left, right, last_use; Segment(int _l, int _r, int _lst) : left(_l), right(_r), last_use(_lst) {} bool operator<(const Segment &other) const { return right < other.right; } }; using SSI = set<Segment>::iterator; inline int is_cut(const Segment &cur, const Segment &nex) { if (cur.right < nex.left || cur.left > nex.right) return 1; if (cur.left <= nex.left && nex.right <= cur.right) return 2; if (nex.left <= cur.left && cur.right <= nex.right) return 3; if (nex.left <= cur.left && cur.left <= nex.right && nex.right <= cur.right) return 4; return 5; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M, Q; cin >> N >> M >> Q; vc<int> L(M+1), R(M+1), S(Q+1); rep(i, 1, M+1) cin >> L[i] >> R[i]; rep(i, 1, Q+1) cin >> S[i]; set<Segment> ranges; unordered_map<int, int> cnt_dist; cnt_dist.reserve(M*2); vc<Segment> cuts, to_insert; vc<SSI> to_delete; cuts.reserve(16); to_insert.reserve(16); to_delete.reserve(16); int tim = 0; rep(i, 1, M+1) { Segment nex(L[i], R[i], tim); cuts.clear(); to_insert.clear(); to_delete.clear(); auto it = ranges.lower_bound(Segment(L[i], L[i], 0)); while (it != ranges.end() && it -> left <= R[i]) { cuts.pb(*it); to_delete.pb(it); ++it; } for (auto &d : to_delete) ranges.erase(d); to_insert.pb(nex); for (auto &cur : cuts) { int type = is_cut(cur, nex); if (type == 1) continue; int overlap = 0; int time_dist = nex.last_use - cur.last_use + cur.left - nex.left - 1; switch (type) { case 2: { int ls = cur.left, le = nex.left - 1; int rs = nex.right + 1, re = cur.right; if (ls <= le) to_insert.eb(ls, le, cur.last_use); if (rs <= re) to_insert.eb(rs, re, cur.last_use+rs-ls); overlap = nex.right - nex.left + 1; break; } case 3: { overlap = cur.right - cur.left + 1; break; } case 4: { int rs = nex.right + 1, re = cur.right; if (rs <= re) to_insert.eb(rs, re, cur.last_use+rs-cur.left); overlap = nex.right - cur.left + 1; break; } case 5: { int ls = cur.left, le = nex.left - 1; if (ls <= le) to_insert.eb(ls, le, cur.last_use); overlap = cur.right - nex.left + 1; break; } } cnt_dist[time_dist] += overlap; } for (auto &seg : to_insert) ranges.insert(seg); tim += (R[i] - L[i] + 1); } vc<pii> dists; dists.reserve(sz(cnt_dist)); for (auto &p : cnt_dist) dists.eb(p.fr, p.sc); srtvc(dists); vc<pii> pref; pref.reserve(sz(dists)+1); int tot = 0; pref.eb(-1, 0); for (auto &[dist, cnt] : dists) { tot += cnt; pref.eb(dist, tot); } rep(i, 1, Q+1) { auto it = lower_bound(all(pref), pii(S[i], 0)); if (it == pref.begin()) cout << tot << ' '; else { --it; cout << tot - it -> sc << ' '; } } }