#include <bits/stdc++.h>
#define int long long
#define gcd(x, y) __gcd(x,y)
#define IOS cin.tie(0),cout.tie(0)->sync_with_stdio(0)
#define _ 0
#define ldb long double
using namespace std;
namespace FastIO{
// #define _gc() (St==Ed&&(Ed=(St=in)+fread(in,1,N,stdin),St==Ed)?EOF:*St++)
#define _gc() getchar()
#define _fl() (fwrite(ot,1,now-ot,stdout))
#define _pc(x) (now==ot+N&&(_fl(),now=ot),*now++=(x))
const int N=1<<20;char in[N],*St=in,*Ed=in,ot[N],*now=ot;
class __f{public:~__f(){_fl();}} _f;
#define TYPES template<typename T>
class In{
public:
#define Ipt(typ) inline In&operator>>(typ x)
TYPES Ipt(T&){bool f=0;x=0;char c=_gc();while(c<48||c>57)f|=(c=='-'),c=_gc();while(c>=48&&c<=57)x=x*10+(c^48),c=_gc();if(c=='.'){__float128 dot=1;for(c=_gc();c>=48&&c<=57;c=_gc())x+=(c^48)*(dot*=0.1);}return x=(f?-x:x),*this;}
Ipt(char&){while(isspace(x=_gc()));return*this;}
#define Instr(add) char c=_gc();for(;isspace(c);c=_gc());while(!isspace(c)&&~c)add,c=_gc();
#define Gline(add) char c=_gc();for(;!(c==' '||!isspace(c));c=_gc());while(c==' '||!isspace(c))add,c=_gc();
inline In&getline(char*x){Gline((*x++)=c);return*x=0,*this;}inline In&getline(string&x){x.clear();Gline(x.push_back(c));return*this;}
Ipt(char*){Instr((*x++)=c);return*x=0,*this;}Ipt(string&){x.clear();Instr(x.push_back(c));return*this;}Ipt(In&){return x;}
}fin;
TYPES inline In&getline(T&x,In&in=fin){return fin.getline(x),in;}
class Ot{
char buf[80];int dt=6,tp=0;public:
#define Wt(typ) inline Ot&operator<<(typ x)
TYPES Wt(T){if(x<0)_pc('-'),x=-x;do buf[++tp]=x%10,x/=10;while(x);while(tp)_pc(buf[tp--]^48);return*this;}Wt(char){return _pc(x),*this;}
Wt(const char*){while(*x)_pc(*(x++));return*this;}Wt(char*){return(*this)<<(const char*)x;}Wt(string){return(*this)<<x.c_str();}
Wt(long double){snprintf(buf,sizeof(buf),"%.*Lf",dt,x);return(*this)<<buf;}Wt(Ot&){return x;}
#define OD(typ) Wt(typ){return (*this)<<(long double)x;}
OD(double)OD(__float128)inline Ot&setdot(const int n){return dt=n,*this;}
}fout;
inline Ot&setdot(const int n,Ot&ot=fout){return ot.setdot(n),ot;}
} using FastIO::fin, FastIO::fout;
#define cin fin
#define cout fout
template<int P>
struct modint {
private:
template<typename T>
inline static const T Down(const T&x) {return x >= P ? x - P : x;}
public:
unsigned int v;
modint(unsigned int v=0) : v(v) {}
using mint = modint;
#define FI friend inline
FI ostream&operator<<(ostream&o, mint v) {return o<<v.v;}
FI istream&operator>>(istream&i, mint&v) {int x;return i>>x,v.v=Down(x%P+P),i;}
FI mint operator+(mint a, mint b) {return Down(a.v + b.v);}
FI mint operator-(mint a, mint b) {return Down(a.v - b.v + P);}
FI mint operator*(mint a, mint b) {return 1ull * a.v * b.v % P;}
FI mint operator/(mint a, mint b) {return a * ~b;}
FI mint operator^(mint a, int p) {mint r=1; for(; p; p >>= 1, a = a * a) if (p & 1) r = r * a; return r;}
FI mint operator~(mint a) {return a ^ (P - 2);}
FI mint operator-(mint a) {return a.v ? P - a.v : 0;}
FI mint&operator+=(mint&a, mint b) {return a=a+b;}
FI mint&operator-=(mint&a, mint b) {return a=a-b;}
FI mint&operator*=(mint&a, mint b) {return a=a*b;}
FI mint&operator/=(mint&a, mint b) {return a=a/b;}
FI mint&operator^=(mint&a, int b) {return a=a^b;}
FI mint&operator++(mint&a) {return a += 1;}
FI mint&operator--(mint&a) {return a -= 1;}
FI mint operator++(mint&a, signed) {mint x=a; return ++a, x;}
FI mint operator--(mint&a, signed) {mint x=a; return --a, x;}
FI bool operator==(mint a, mint b) {return a.v==b.v;}
FI bool operator!=(mint a, mint b) {return a.v!=b.v;}
};
typedef modint<(int)1e9 + 7> mint;
const int N(5e5+5), DN(N<<2);
int t[2][DN], laz[DN];
//0: max 1: min
#define lx (x<<1)
#define rx (lx|1)
void Add(int x, int l, int r, int v) {laz[x] += v, t[0][x] += v, t[1][x] += v;}
void pushdown(int x, int l, int r) {
if (laz[x]) {
int mid = l + r >> 1;
Add(lx, l, mid, laz[x]);
Add(rx, mid + 1, r, laz[x]);
laz[x] = 0;
}
}
void pushup(int x) {t[0][x] = max(t[0][lx], t[0][rx]), t[1][x] = min(t[1][lx], t[1][rx]);}
void build(int x=1, int l=1, int r=N-5) {
if (l == r) return void(t[0][x]=t[1][x]=l);
int mid = l + r >> 1;
build(lx, l, mid), build(rx, mid + 1, r);
pushup(x);
}
inline bool chkmx(int L, int R, int x) {return L <= t[0][x] && t[0][x] <= R;}
inline bool chkmi(int L, int R, int x) {return L <= t[1][x] && t[1][x] <= R;}
inline bool chk(int L, int R, int l, int r) {return !(R < l || r < L);}
void add(int L, int R, int x=1, int l=1, int r = N-5) {
if (chkmx(L, R, x) && chkmi(L, R, x)) return Add(x, l, r, 1);
int mid = l + r >> 1; pushdown(x, l, r);
if (chk(L, R, t[1][lx], t[0][lx])) add(L, R, lx, l, mid);
if (chk(L, R, t[1][rx], t[0][rx])) add(L, R, rx, mid + 1, r);
pushup(x);
}
int get(int p, int x=1, int l=1, int r=N-5) {
if (p == l && l == r) return t[0][x];
int mid = l + r >> 1; pushdown(x, l, r);
return p <= mid ? get(p, lx, l, mid) : get(p, rx, mid + 1, r);
}
void work() {
int n;
cin >> n;
build();
while (n--) {
int l, r;
cin >> l >> r;
add(l, r);
// for (int i = 1990; i <= 2000; i++) cout << get(i) << " \n"[i == 2000];
}
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
cout << get(x) << '\n';
}
}
signed main() {
// IOS;
int T(1);
// cin >> T;
while (T--) work();
return ~~(0^_^0);
}
Main.cpp: In member function ‘FastIO::Ot& FastIO::Ot::operator<<(long double)’:
Main.cpp:32:53: warning: field precision specifier ‘.*’ expects argument of type ‘int’, but argument 4 has type ‘long long int’ [-Wformat=]
32 | Wt(long double){snprintf(buf,sizeof(buf),"%.*Lf",dt,x);return(*this)<<buf;}Wt(Ot&){return x;}
| ~~^~~ ~~
| | |
| int long long int
Main.cpp: In function ‘void Add(long long int, long long int, long long int, long long int)’:
Main.cpp:77:21: warning: unused parameter ‘l’ [-Wunused-parameter]
77 | void Add(int x, int l, int r, int v) {laz[x] += v, t[0][x] += v, t[1][x] += v;}
| ^
Main.cpp:77:28: warning: unused parameter ‘r’ [-Wunused-parameter]
77 | void Add(int x, int l, int r, int v) {laz[x] += v, t[0][x] += v, t[1][x] += v;}
| ^
Main.cpp: In function ‘void pushdown(long long int, long long int, long long int)’:
Main.cpp:80:29: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
80 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function ‘void build(long long int, long long int, long long int)’:
Main.cpp:89:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
89 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function ‘void add(long long int, long long int, long long int, long long int, long long int)’:
Main.cpp:98:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
98 | int mid = l + r >> 1; pushdown(x, l, r);
| ~~^~~
Main.cpp: In function ‘long long int get(long long int, long long int, long long int, long long int)’:
Main.cpp:105:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
105 | int mid = l + r >> 1; pushdown(x, l, r);
| ~~^~~