题目描述

1918 年捷克斯洛伐克建国时，政治局势总体有利，却极其混乱。许多高级官员还承担着国外事务，只能在有限的时间内留在布拉格。幸运的是，总统办公室整理出了一份日程表，为每名官员记录了他确定会在布拉格停留的一段连续日期。

捷克斯洛伐克战争部长 Milan Rastislav Štefánik 同时也是一名天文学家。他希望以更系统的方式安排政府日程，使内阁能够亲自会见尽可能多的官员。

日程表包含编号为

的各天。

对每名官员，已知他在布拉格的第一天和最后一天，因此他的在场日期构成一个闭区间。政府拥有固定数量的会议日。这些会议日可以任意选择，不要求连续；官员只要在自己的在场区间内遇到至少一个会议日，就能够参加会议。

Štefánik 首先随机选择了规定数量的会议日，并计算无法参会的官员数，即在自己的整个在场区间内都没有任何会议日的官员数量。

随后，他会反复进行调整：

• 选择当前的一个会议日；
• 将它移动到另一个尚未被选作会议日的日期；
• 每次移动后，重新计算无法参会的官员数。

同一个会议日可能被移动多次，也可能从未被移动。

请高效模拟这一过程。

输入格式

第一行包含三个整数 $N,C,Q$（$1\le N,C,Q\le 10^5$），分别表示官员数量、会议日数量和调整次数。

接下来 $N$ 行，每行包含两个整数 $x,y$，表示一名官员在布拉格的日期区间 $[x,y]$。保证：

下一行包含 $C$ 个互不相同的整数 $C_i$（$1\le C_i\le 10^5$），表示最初选择的会议日。

接下来 $Q$ 行，每行包含两个整数 $f,t$（$1\le f,t\le 10^5$），表示把会议日从日期 $f$ 移动到日期 $t$。

保证在执行该次操作之前：

• $f$ 当前是一个会议日；
• $t$ 当前不是会议日。

输出格式

首先输出一行，表示初始会议日安排下无法参会的官员数。

然后对每次调整输出一行，表示执行该次移动后无法参会的官员数。

总共输出 $Q+1$ 行。

样例

输入

2 1 3
1 4
2 7
3
3 5
5 1
1 10

输出

0
1
1
2