该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

这是本题的困难版本，与简单版本相比，在本版本，你需要在每次操作后，都输出当前运行的程序数量

简单版本题目： https://ac.ccnuacm.com/p/146

题目描述

Sad有 $n$ 个开关，编号为 $1$ 到 $n$，此外，他还有 $m$ 个程序，每个程序都由一段编号连续的开关控制，即第 $i$ 个程序由第 $l_i$到第$r_i$ 个开关控制$(1\leq i \leq m, 1 \leq l_i \leq r_i \leq n)$ ,对于控制某个程序的开关，只有开启的数量严格大于关闭的数量，该程序才能运行。初始时刻，所有开关全部关闭，Sad会按顺序执行 $k$ 次操作，每次操作会将某个位置的开关打开(保证每次操作的开关互不相同)。求每次操作后，当前运行的程序数量

输入格式

第一行输入两个整数$n,m(1 \leq n,m \leq 200000)$，与题目描述所述相同。

第二到第 $m + 1$ 行，每行输入两个整数$l_i,r_i（1 \leq l_i \leq r_i \leq n)$，表示控制第 $i$ 个 程序的开关范围

第$m + 2$ 行输入一个整数$k(1 \leq k \leq n\leq 200000)$,表示操作的个数

第$m + 3$ 行到第$m + k + 2$行，每行输入一个整数，表示第$i$个操作打开的开关。保证每次打开的开关不同

输出格式

$k$行，每行一个整数，表示执行了第$i$ 个操作后，当前运行的程序数量

样例 #1

样例输入 #1

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

样例输出 #1

0
0
2
4
5

样例 #2

样例输入 #2

4 2
1 1
4 4
2
2
3

样例输出 #2

0
0