Due to global warming and the environmental crisis, we now need to make plans to survive the possible natural disasters. This time, we will make manuals for tsunamis.

Consider a map of the city on a two-dimensional coordinate plane. The ocean line can be represented as a line parallel to the Ox axis, $y = k$. Normally, $k$ would be $0$, but when a tsunami occurs, it will become a positive integer.

In our city, there are $n$ distinct evacuation spots represented as points $(p_i, q_i)$. For each evacuation spot, you know the time $r_i$ in minutes that you will need to arrive at that particular spot by yourself.

The evacuation manual consists of two steps:

1. You pick an evacuation spot $(p_i, q_i)$ and arrive there by yourself, spending $r_i$ minutes.
2. We gather at that spot, and then move to $y = k$ as a group, by the rules stated below.

There will be obstacles to evacuation. For simplicity, we assume obstacles are straight line segments parallel to the Ox axis.

A total of $m$ obstacles are given as $(s_i, e_i, y_i, t_i)$, which are line segments connecting $(s_i, y_i)$ and $(e_i, y_i)$ that take $t_i$ minutes to cross. Note that it takes $t_i$ minutes to cross the obstacle even at the endpoints. No obstacles coincide with evacuation spots.

However, obstacles themselves may overlap. In that case, the time crossing the overlapped obstacles is the sum of their $t_i$. For example, if there are two obstacles $(1, 4, 2, 5)$ and $(3, 5, 2, 7)$, crossing at $x = 1$ will take $5$ minutes, crossing at $x = 3$ will take $5 + 7 = 12$ minutes, and crossing at $x = 5$ will take $7$ minutes.

Along the $y$ axis, we will only be moving upwards, that is, increase our $y$ coordinate, until we reach $y = k$, which is the safe zone. However, while moving upwards, we can change our $x$ coordinate as well. When our current $y$ coordinate is strictly between $i$ and $i + 1$, it takes $c_i$ minutes to change our $x$ coordinate by $1$ in either direction. For example, when $c_3 = 5$ and we move from $x = 10$ to $x = 6$ while staying at height $y = 3.5$, it will take $5 \cdot |10 - 6| = 20$ minutes. We do not consider the time moving upwards; we only consider the time moving horizontally.

We can only move to integer $x$ coordinates, and we don't change $x$ coordinates at integer $y$ coordinates. There are no other constraints; for example, we can move to either $x = -100$ or $x = 10^{100}$.

Note that $c_1, \ldots, c_{k - 1}$ is a non-decreasing sequence: as the height $y$ increases, the number of people at height $y$ will also increase, and therefore it will get harder to move between them.

Calculate the minimum possible time in minutes to evacuate to $(1, k)$, $(2, k)$, $\ldots$, $(x, k)$, respectively.

Input

The first line contains two integers: $x$ and $k$ ($3 \leq x, k \leq 2 \cdot 10^5$).

The second line contains two integers: $n$ and $m$ ($1 \leq n \leq 2 \cdot 10^5$, $0 \leq m \leq 2 \cdot 10^5$).

Each of the following $n$ lines contains three integers, $p_i$, $q_i$, and $r_i$, which denote the $i$-th evacuation spot ($1 \leq p_i \leq x$, $1 \leq q_i < k$, $0 \leq r_i \leq 10^{15}$). All points $(p_i, q_i)$ are distinct.

Each of the following $m$ lines contains four integers, $s_i$, $e_i$, $y_i$, and $t_i$, which denote the $i$-th obstacle ($1 \leq s_i \leq e_i \leq x$, $2 \leq y_i < k$, $0 \leq t_i \leq 10^9$). Obstacles may have common points, but no evacuation spots lie on any obstacles.

The last line contains $k - 1$ integers: $c_1, c_2, \ldots, c_{k - 1}$ ($0 \leq c_1 \leq c_2 \leq \ldots \leq c_{k - 1} \leq 10^6$). Here, $c_i$ denotes the time in minutes needed to change the $x$ coordinate by $1$ when your $y$ coordinate is strictly between $i$ and $i + 1$.

Output

Print $x$ lines. On the $i$-th line, print a single integer denoting the minimum time to reach the point $(i, k)$.

Examples

Input 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

Output 1

13
15
17
19
19
17
15
13
11
9