由于全球变暖和环境危机，我们现在需要制定计划以在可能发生的自然灾害中幸存。这一次，我们将制作海啸避难手册。

考虑二维坐标平面上的城市地图。海岸线可以表示为一条平行于 Ox 轴的直线 $y = k$。通常情况下，$k$ 为 $0$，但当海啸发生时，它会变成一个正整数。

在我们的城市中，有 $n$ 个不同的避难点，表示为点 $(p_i, q_i)$。对于每个避难点，你已知自己到达该特定避难点所需的时间 $r_i$（以分钟为单位）。

避难手册包含两个步骤：

1. 你选择一个避难点 $(p_i, q_i)$ 并自行到达该点，耗时 $r_i$ 分钟。
2. 我们在该点集合，然后按照下面所述的规则集体移动到 $y = k$。

避难过程中会遇到障碍物。为简单起见，我们假设障碍物是平行于 Ox 轴的线段。

共有 $m$ 个障碍物，给出形式为 $(s_i, e_i, y_i, t_i)$，表示连接 $(s_i, y_i)$ 和 $(e_i, y_i)$ 的线段，穿过该障碍物需要花费 $t_i$ 分钟。请注意，即使在端点处穿过障碍物也需要花费 $t_i$ 分钟。没有障碍物与避难点重合。

然而，障碍物本身可能会重叠。在这种情况下，穿过重叠障碍物的时间是它们各自 $t_i$ 的总和。例如，如果有两个障碍物 $(1, 4, 2, 5)$ 和 $(3, 5, 2, 7)$，在 $x = 1$ 处穿过将花费 $5$ 分钟，在 $x = 3$ 处穿过将花费 $5 + 7 = 12$ 分钟，在 $x = 5$ 处穿过将花费 $7$ 分钟。

沿着 $y$ 轴，我们只会向上移动，即增加我们的 $y$ 坐标，直到到达安全区 $y = k$。然而，在向上移动的同时，我们也可以改变我们的 $x$ 坐标。当当前的 $y$ 坐标严格介于 $i$ 和 $i + 1$ 之间时，在任一方向上将 $x$ 坐标改变 $1$ 需要花费 $c_i$ 分钟。例如，当 $c_3 = 5$ 且我们在保持高度 $y = 3.5$ 的同时从 $x = 10$ 移动到 $x = 6$ 时，将花费 $5 \cdot |10 - 6| = 20$ 分钟。我们不考虑向上移动的时间；我们只考虑水平移动的时间。

我们只能移动到整数 $x$ 坐标，并且我们不在整数 $y$ 坐标处改变 $x$ 坐标。没有其他限制；例如，我们可以移动到 $x = -100$ 或 $x = 10^{100}$。

请注意，$c_1, \ldots, c_{k - 1}$ 是一个非递减序列：随着高度 $y$ 的增加，高度 $y$ 处的人数也会增加，因此在它们之间移动会变得更加困难。

分别计算疏散到 $(1, k)$, $(2, k)$, $\ldots$, $(x, k)$ 所需的最小可能时间（以分钟为单位）。

输入格式

第一行包含两个整数：$x$ 和 $k$（$3 \leq x, k \leq 2 \cdot 10^5$）。

第二行包含两个整数：$n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^5$，$0 \leq m \leq 2 \cdot 10^5$）。

接下来的 $n$ 行，每行包含三个整数 $p_i$、$q_i$ 和 $r_i$，表示第 $i$ 个避难点（$1 \leq p_i \leq x$，$1 \leq q_i < k$，$0 \leq r_i \leq 10^{15}$）。所有点 $(p_i, q_i)$ 互不相同。

接下来的 $m$ 行，每行包含四个整数 $s_i$、$e_i$、$y_i$ 和 $t_i$，表示第 $i$ 个障碍物（$1 \leq s_i \leq e_i \leq x$，$2 \leq y_i < k$，$0 \leq t_i \leq 10^9$）。障碍物可能有公共点，但没有任何避难点位于任何障碍物上。

最后一行包含 $k - 1$ 个整数：$c_1, c_2, \ldots, c_{k - 1}$（$0 \leq c_1 \leq c_2 \leq \ldots \leq c_{k - 1} \leq 10^6$）。这里，$c_i$ 表示当你的 $y$ 坐标严格介于 $i$ 和 $i + 1$ 之间时，将 $x$ 坐标改变 $1$ 所需的时间（以分钟为单位）。

输出格式

输出 $x$ 行。在第 $i$ 行中，输出一个整数，表示到达点 $(i, k)$ 的最小时间。

样例

输入格式 1

10 10
3 5
9 3 5
5 2 34
2 1 43
6 10 2 19
7 9 2 86
2 10 4 87
2 3 2 17
2 2 2 49
1 1 1 2 7 7 8 10 10

输出格式 1

13
15
17
19
19
17
15
13
11
9