Gophers

Dick Dastardly wants to torment the gophers living along a straight mountain ridge. The ridge has $n$ gopher holes in a row, indexed $1$ to $n$ from west to east. Hole $1$ sits at the origin (distance $0$), and hole $i$ (for $2 \le i \le n$) sits $x_i$ meters east of hole $1$, with $x_2 < x_3 < \cdots < x_n$.

Dick placed $m$ CD players along the ridge; player $j$ sits $z_j$ meters east of hole $1$. Each player disturbs every hole within $l$ meters of it: a hole at distance $p$ from hole $1$ is disturbed by a player at distance $z$ whenever $|p - z| \le l$. A hole's gopher cannot sleep if at least one CD player disturbs that hole.

Over $d$ days the players are rearranged. On the morning of day $i$, Dick moves the player currently located $p_i$ meters from hole $1$ to a point $r_i$ meters from hole $1$. Immediately before each move, position $p_i$ holds exactly one player and position $r_i$ holds none.

Report the number of holes whose gophers cannot sleep at the required moments.

The first line contains four integers $n$, $m$, $d$, $l$ ($2 \le n, m \le 500000$, $1 \le d \le 500000$, $1 \le l \le 10^9$): the number of holes, the number of CD players, the number of days, and each player's range.

The second line contains $n-1$ integers $x_2, x_3, \ldots, x_n$ ($0 < x_2 < x_3 < \cdots < x_n \le 10^9$): the distances of holes $2, 3, \ldots, n$ from hole $1$.

The third line contains $m$ integers $z_1, z_2, \ldots, z_m$ ($0 \le z_1 < z_2 < \cdots < z_m \le 10^9$): the distances of the CD players from hole $1$; every player lies east of hole $1$.

Each of the next $d$ lines contains two integers $p_i$ and $r_i$ ($0 \le p_i, r_i \le 10^9$, $p_i \ne r_i$): on day $i$ the player at distance $p_i$ is moved to distance $r_i$. Immediately before each move a player is guaranteed to be at position $p_i$ and no player is at position $r_i$.

Output $d + 1$ lines. For $i = 1, 2, \ldots, d$, line $i$ must contain the number of sleepless holes in the state just before the $i$-th move. Line $d + 1$ must contain the number of sleepless holes after the last move.

(Equivalently: print the count for the initial arrangement, then, after applying each of the $d$ moves in order, print the new count.)