Prof. Pang 正在玩《植物大战僵尸》。
想象游戏是在数轴上进行的。游戏中的元素如下：
- $n$ 只僵尸。第 $i$ 只僵尸在时间 $t_i$ 出现在数轴的 $0$ 位置，生命值为 $h_i$。所有僵尸的移动速度均为 $V$，且都向右移动。
- $m$ 个地刺。第 $i$ 个地刺的位置为 $p_i$，攻击力为 $a_i$。
- 一个豌豆射手位于 $10^{100}$ 的位置。它每秒发射 $K$ 颗攻击力为 $D$ 的豌豆。
游戏中的每一秒按如下步骤处理：
- 当第 $x$ 秒开始时，所有 $t_i$ 等于 $x$ 的僵尸出现在位置 $0$。
- 此后，对于每只已出现且存活的僵尸 $u$，它会受到位置在 $(P_u, P_u + V]$ 范围内的地刺攻击，其中 $P_u$ 是第 $u$ 只僵尸当前的位置。因此，它的生命值会减少 $\sum_{1 \le i \le m, P_u < p_i \le P_u + V} a_i$。如果僵尸的生命值小于等于 $0$，则该僵尸死亡。否则，它仍然存活，且其位置增加 $V$。
- 当第 $x$ 秒结束时，豌豆射手连续发射 $K$ 颗豌豆。对于每一颗豌豆，它会击中当前存活且位置最靠前的僵尸。如果存在多只位置相同的僵尸，豌豆会击中索引最小的那一只。被击中僵尸的生命值减少 $D$。如果该僵尸的生命值降至 $0$ 或以下，则该僵尸死亡。豌豆是逐一处理的，而不是同时处理的。（例如，如果一只僵尸被第一颗豌豆击杀，第二颗豌豆就不能击中它，因为它在第二颗豌豆发射前就已经死亡了。）如果不存在存活的僵尸，剩余的豌豆将不会击中任何目标。
Prof. Pang 想知道所有 $n$ 只僵尸的死亡时间（以秒为单位）。
输入格式
第一行包含五个整数 $n, m, V, K, D$ ($1 \le n, m \le 10^5, 1 \le V, K, D \le 10^9$)，用空格分隔。
接下来 $n$ 行，每行包含两个整数 $t_i, h_i$ ($1 \le t_i, h_i \le 10^9$)，用空格分隔。
接下来 $m$ 行，每行包含两个整数 $p_i, a_i$ ($1 \le p_i, a_i \le 10^9$)，用空格分隔。
输出格式
输出一行，包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 只僵尸的死亡时间（以秒为单位）。
样例
输入 1
3 2 1 2 2 1 11 2 8 1 1 1 2 2 4
输出 1
2 3 1
说明
在第一秒期间： 第一只僵尸出现并移动到位置 $1$。它受到 $6$ 点伤害（$2$ 点来自第一个地刺，$4$ 点来自两颗豌豆）。 第三只僵尸出现并移动到位置 $1$。它受到 $2$ 点伤害（来自第一个地刺）并死亡（因为其生命值变为 $-1$）。
在第二秒期间： 第一只僵尸移动到位置 $2$，受到 $6$ 点伤害（$4$ 点来自第二个地刺，$2$ 点来自第一颗豌豆）并死亡（因为其生命值变为 $-1$）。 第二只僵尸出现并移动到位置 $1$。它受到 $4$ 点伤害（$2$ 点来自第一个地刺，$2$ 点来自第二颗豌豆）。
在第三秒期间： 第二只僵尸移动到位置 $2$，受到 $4$ 点伤害（来自第二个地刺）并死亡（因为其生命值变为 $0$）。 豌豆在这一秒内没有击中任何僵尸。
因此，僵尸的死亡时间分别为 $2, 3, 1$。