Plants vs Zombies on a Number Axis

Prof. Pang is playing \(\textit{Plants\,vs\,Zombies}\).

Imagine that the game is played on a number axis. The following elements are in the game:

• \(n\) zombies. The \(i\)-th zombie appears at position \(0\) at time \(t_i\) with health \(h_i\). All zombies move to the right with a constant speed \(V\).
• \(m\) spikeweeds. The \(i\)-th spikeweed is located at position \(p_i\) and has an attack power \(a_i\).
• A peashooter located at \(10^{100}\) that shoots \(K\) peas per second; each pea has damage \(D\).

The game proceeds in discrete seconds. At each second \(x\), the following events occur in order:

1. Appearance: All zombies with \(t_i = x\) appear at position \(0\).
2. Damage and Movement: For each alive zombie \(u\) at current position \(P_u\), compute the total damage from all spikeweeds located in the interval \((P_u,\,P_u+V]\), i.e. \(\sum_{\{i\,|\,P_u < p_i \le P_u+V\}} a_i\). Deduct this damage from \(u\)'s health. If the health becomes \(\le 0\), the zombie dies immediately and its death time is recorded as \(x\). Otherwise, the zombie survives and its position is increased by \(V\).
3. Peashooting: At the end of second \(x\), the peashooter fires \(K\) peas sequentially. For each pea, if there is at least one alive zombie, the pea hits the one at the maximum position (if several zombies share the maximum position, the one with the smallest index is chosen). The hit zombie loses \(D\) health; if its health drops to \(\le 0\), it dies instantly with death time recorded as \(x\), and subsequent peas will not target that zombie.

Prof. Pang wants to know, for each zombie, at which second it dies. Output the death time for each zombie in the order of their indices.

inputFormat

The input is given as follows:

 n m K D V
 t_1 h_1
 t_2 h_2
 ...
 t_n h_n
 p_1 a_1
 p_2 a_2
 ...
 p_m a_m

Where:

• \(n\): The number of zombies.
• \(m\): The number of spikeweeds.
• \(K\): The number of peas shot every second.
• \(D\): The damage of each pea.
• \(V\): The moving speed of zombies (and also the length of the interval for spikeweed damage computation).
• For each zombie, \(t_i\) is the appearance time and \(h_i\) is its health.
• For each spikeweed, \(p_i\) is its position and \(a_i\) is its attack power.

outputFormat

Output \(n\) lines. The \(i\)-th line should contain a single integer representing the second at which the \(i\)-th zombie dies.

sample

1 1 1 10 5
1 20
3 5

2