Description

庞教授正在玩「植物大战僵尸」。

假设游戏在数轴上进行。游戏中有以下元素：

• $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\limits_{1\le i\le m, P_u < p_i \le P_u + V} a_i$。如果僵尸的生命值不超过零，它就会死亡。否则，它仍然存活并且位置增加 $V$。
• 当第 $x$ 秒结束时，豌豆射手连续发射 $K$ 颗豌豆。对于每颗豌豆，它会击中当前存活且位置最大的僵尸。如果有多个位置最大的僵尸，豌豆会击中索引最小的那个。被击中的僵尸的生命值减少 $D$。如果僵尸的生命值减少到不超过 $0$，它就会死亡。豌豆是逐个处理的，而不是同时处理的。（例如，如果一个僵尸被第一颗豌豆击杀，第二颗豌豆无法击中它，因为它在第二颗豌豆发射前已经死亡。）如果没有存活的僵尸，剩下的豌豆将击中空处。

庞教授想知道所有 $n$ 个僵尸的死亡时间（以秒为单位）。

Input Format

第一行包含五个整数 $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$)，用单个空格分隔。

Output Format

输出一行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个僵尸的死亡时间（以秒为单位）。

3 2 1 2 2
1 11
2 8
1 1
1 2
2 4

2 3 1

Hint

在第一秒：

• 第一个僵尸出现并移动到位置 1。它受到 $6$ 点伤害（$2$ 点来自第一个地刺，$4$ 点来自两颗豌豆）。
• 第三个僵尸出现并移动到位置 1。它受到 $2$ 点伤害（来自第一个地刺）并死亡（因为它的生命值变为 $-1$）。

在第二秒：

• 第一个僵尸移动到位置 $2$，受到 $6$ 点伤害（$4$ 点来自第二个地刺，$2$ 点来自第一颗豌豆）并死亡（因为它的生命值变为 $-1$）。
• 第二个僵尸出现并移动到位置 $1$。它受到 $4$ 点伤害（$2$ 点来自第一个地刺，$2$ 点来自第二颗豌豆）。

在第三秒：

• 第二个僵尸移动到位置 $2$，受到 $4$ 点伤害（$4$ 点来自第二个地刺）并死亡（因为它的生命值变为 $0$）。
• 这一秒内豌豆没有击中任何僵尸。

因此，僵尸的死亡时间分别是 $2$，$3$，$1$。（由 ChatGPT 4o 翻译）