두더지

딕 대스터들리(Dick Dastardly)는 곧은 직선 능선을 따라 사는 두더지들을 괴롭히려 한다. 능선에는 두더지 굴 $n$개가 일직선으로 늘어서 있으며, 서쪽에서 동쪽 방향으로 $1$번부터 $n$번까지 번호가 매겨져 있다. $1$번 굴은 원점(거리 $0$)에 있고, $i$번 굴($2 \le i \le n$)은 $1$번 굴에서 동쪽으로 $x_i$미터 떨어진 곳에 있으며 $x_2 < x_3 < \cdots < x_n$을 만족한다.

딕은 능선을 따라 CD 플레이어 $m$개를 놓았다. $j$번째 플레이어는 $1$번 굴에서 동쪽으로 $z_j$미터 떨어진 곳에 있다. 각 플레이어는 자신으로부터 $l$미터 이내에 있는 모든 굴을 방해한다. 즉, $1$번 굴로부터의 거리가 $p$인 굴은 거리가 $z$인 어떤 플레이어에 대해 $|p - z| \le l$일 때 그 플레이어에게 방해를 받는다. 어떤 굴이 적어도 하나의 플레이어에게 방해받으면 그 굴의 두더지는 잠을 잘 수 없다.

$d$일 동안 플레이어들이 재배치된다. $i$일째 아침에 딕은 현재 $1$번 굴로부터 $p_i$미터 떨어진 곳에 있는 플레이어를 $1$번 굴로부터 $r_i$미터 떨어진 지점으로 옮긴다. 매 이동 직전에 위치 $p_i$에는 정확히 하나의 플레이어가 있고 위치 $r_i$에는 플레이어가 없음이 보장된다.

요구되는 각 시점에서 두더지가 잠들 수 없는 굴의 개수를 구하라.

첫째 줄에 네 정수 $n$, $m$, $d$, $l$ ($2 \le n, m \le 500000$, $1 \le d \le 500000$, $1 \le l \le 10^9$)이 주어진다. 각각 굴의 개수, CD 플레이어의 개수, 날의 수, 플레이어의 사정거리이다.

둘째 줄에 $n-1$개의 정수 $x_2, x_3, \ldots, x_n$ ($0 < x_2 < x_3 < \cdots < x_n \le 10^9$)이 주어진다. $2, 3, \ldots, n$번 굴의 $1$번 굴로부터의 거리이다.

셋째 줄에 $m$개의 정수 $z_1, z_2, \ldots, z_m$ ($0 \le z_1 < z_2 < \cdots < z_m \le 10^9$)이 주어진다. CD 플레이어들의 $1$번 굴로부터의 거리이며, 모든 플레이어는 $1$번 굴의 동쪽에 있다.

이어지는 $d$개의 줄 중 $i$번째 줄에는 두 정수 $p_i$와 $r_i$ ($0 \le p_i, r_i \le 10^9$, $p_i \ne r_i$)가 주어진다. $i$일째에 거리 $p_i$에 있는 플레이어를 거리 $r_i$로 옮긴다는 뜻이다. 매 이동 직전에 위치 $p_i$에는 플레이어가 존재하고 위치 $r_i$에는 플레이어가 없음이 보장된다.

$d + 1$개의 줄을 출력한다. $i = 1, 2, \ldots, d$에 대해 $i$번째 줄에는 $i$번째 이동을 하기 직전 상태에서 두더지가 잠들 수 없는 굴의 개수를 출력한다. $d + 1$번째 줄에는 마지막 이동을 마친 후의 개수를 출력한다.

(다시 말해, 처음 배치의 개수를 먼저 출력하고, $d$번의 이동을 순서대로 적용할 때마다 새로 생긴 개수를 출력하면 된다.)