Public Judge

pjudge

Time Limit: 3 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21657. 【PR #5】和平共处

Statistics

二维平面上有 $n$ 只黑蚂蚁。

在接下来的一段时间内,陆陆续续来了 $m$ 只白蚂蚁。然而,黑蚂蚁和白蚂蚁之间会打架,小 H 不希望看到这种现象。

小 H 可以给一只蚂蚁喂食,这样它就不想打架了。而如果有一只黑蚂蚁 $(x,y)$ 和白蚂蚁 $(x',y')$ 满足 $x\leq x',y\leq y'$,并且它们都没得到食物,它们就会打架。

小 H 想知道,在每只白蚂蚁到来后,他至少需要喂食多少蚂蚁才能使蚂蚁不会打架。

注意小 H 不会真的喂食,每次他需要计算时,所有蚂蚁都饥肠辘辘。

输入格式

第一行一个整数 $n$ 表示黑点个数。

接下来 $n$ 行每行两个整数 $x_i,y_i$ 表示第 $i$ 只黑蚂蚁的坐标。

接下来一行一个整数 $m$ 表示操作轮数。

接下来 $m$ 行每行两个整数 $x_i,y_i$ 表示第 $i$ 次加入的白蚂蚁坐标。

输出格式

$m$ 行,每行一个整数表示第 $i$ 只白蚂蚁加入后的答案。

样例一

input

3
1 1
2 2
3 3
4
1 1
2 2
1 1
4 4

output

1
2
2
3

样例二、三、四

见附件下载。

数据范围与提示

测试点编号 $n,m\leq$ 特殊性质
$1\sim 3$ $50$
$4\sim 8$ $1000$
$9\sim 11$ $100000$ 所有点 $x_i=y_i$
$12\sim 20$

对于所有数据,保证 $1\leq n,m\leq 100000,0\leq x_i,y_i\leq 10^9$。

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$