Dick Dastardly 想要折磨可怜的 Bytean 地鼠。这些可爱的小生物住在 High Bytemountains 高处的洞穴里。

Dick 在一条山脊上发现了一些地鼠洞，它们位于一条直线上（为了简化起见，我们将洞穴从 $1$ 到 $n$ 编号，从西向东排列）。Dick 计划用摇滚乐折磨地鼠。他买了 $m$ 台 CD 播放器，在每台播放器中放入不同的 Bytels 专辑，并将它们沿山脊排列。来自 CD 播放器的音乐会干扰距离它不超过 $l$ 米的洞穴中的地鼠。

地鼠们感到很困扰，请求你检查在今年冬天，它们在哪些洞穴里无法安睡。但现在 Dick Dastardly 想要制造更多的混乱……

他会不时地移动这些 CD 播放器。地鼠们窃取了 Dick 的秘密计划，现在它们准确地知道，在第 $i$ 天的早上，Dick 会把位于距离 1 号洞穴 $p_i$ 米处的 CD 播放器移到距离该洞穴 $r_i$ 米处。请帮助地鼠们，计算在每次这样的操作后，有多少个洞穴里的地鼠无法安睡。

输入格式

第一行包含四个整数 $n, m, d$ 和 $l$ ($2 \le n, m \le 500\,000$, $1 \le d \le 500\,000$, $1 \le l \le 10^9$)，分别表示地鼠洞的数量、Dick 的 CD 播放器数量、天数以及 CD 播放器的覆盖范围。

第二行包含 $n-1$ 个整数 $x_2, x_3, \dots, x_n$ ($0 < x_2 < x_3 < \dots < x_n \le 10^9$)，表示各洞穴距离 1 号洞穴的距离。

第三行包含 $m$ 个整数 $z_1, z_2, \dots, z_m$ ($0 \le z_1 < z_2 < \dots < z_m \le 10^9$)，表示各 CD 播放器距离 1 号洞穴的距离。所有 CD 播放器都位于该洞穴的东侧。

接下来 $d$ 行，第 $i$ 行包含两个整数 $p_i$ 和 $r_i$ ($0 \le p_i, r_i \le 10^9, p_i \neq r_i$)，表示在第 $i$ 天开始时，Dick 将把位于距离 1 号洞穴 $p_i$ 米处的 CD 播放器移动到距离该洞穴 $r_i$ 米处。你可以假设在每次操作前，位置 $p_i$ 处确实有一台 CD 播放器，且位置 $r_i$ 处没有 CD 播放器。

输出格式

你的程序应输出 $d+1$ 行。第 $i$ 行（对于 $i=1, 2, \dots, d$）应包含一个整数，表示在第 $i$ 次 Dick 的操作之前，有多少个洞穴里的地鼠无法安睡。最后一行应包含最后一次 Dick 的操作之后，无法安睡的洞穴数量。

样例

样例输入 1

5 3 4 1
2 5 6 11
2 4 8
2 1
4 10
8 6
1 8

样例输出 1

2
3
3
5
3