Long ago, Polynesian explorers crossed the endless ocean, guided by the stars, in search of new lands. This great journey began at the $1$st island, Hawaiki, the westernmost point where all life began, and ended at the $N$-th island, Te Pito, the easternmost edge of the world.

In the vast Pacific Ocean, there are $N$ islands and $M$ ancient sea routes connecting them. The $i$-th island is represented as a point $(X_i, Y_i)$ on a 2D plane, and no two islands share the same coordinates. Every route between two islands is a straight line, and these routes never intersect each other except at their endpoint islands.

A group of navigators has been tasked with inspecting these ancient routes by traveling along them. Due to strong westerly winds, navigators must always sail eastward. In other words, they must move in the direction of increasing $x$-coordinates. Each navigator starts from Hawaiki and chooses a path along the routes to reach Te Pito.

The $j$-th route connects islands $U_j$ and $V_j$, and at least $W_j$ navigators must pass through it, according to its importance. Your task is to minimize the total number of navigators required to satisfy the conditions for all routes.

Find the number of navigators passing through each route such that the total number of navigators is minimized.

Constraints

• $2 \le N \le 500,000$
• $1 \le M \le 1,000,000$
• $|X_i|, |Y_i| \le 10^9$ ($1 \le i \le N$)
• $X_i < X_{i+1}$ ($1 \le i \le N - 1$)
• $1 \le U_j < V_j \le N$ ($1 \le j \le M$)
• $1 \le W_j \le 10^9$ ($1 \le j \le M$)
• There exists at least one feasible assignment satisfying all route requirements.
• Every island is reachable from island 1.
• All input values are integers.

Subtasks

1. (2 points) $M = N - 1$
2. (14 points) $\frac{Y_i - Y_{i-1}}{X_i - X_{i-1}} < \frac{Y_{i+1} - Y_i}{X_{i+1} - X_i}$ ($2 \le i \le N - 1$), $W_j = 1$ ($1 \le j \le M$)
3. (14 points) $\frac{Y_i - Y_{i-1}}{X_i - X_{i-1}} < \frac{Y_{i+1} - Y_i}{X_{i+1} - X_i}$ ($2 \le i \le N - 1$)
4. (26 points) $N \le 300$
5. (44 points) No additional constraints.

Input

The first line contains two space-separated integers $N$ and $M$.

The $i$-th line of the next $N$ lines contains two space-separated integers $X_i$ and $Y_i$.

The $j$-th line of the next $M$ lines contains three space-separated integers $U_j$, $V_j$, and $W_j$.

Output

Output $M$ lines in total. On the $j$-th line, print the number of navigators who travel along the $j$-th sea route.

If there are multiple acceptable answers, output any of them.

Example

Example 1

Input

4 5
0 0
1 3
2 1
5 1
1 2 3
1 3 1
2 3 1
2 4 2
3 4 3

Output

3
2
1
2
3