먼 옛날, 폴리네시아의 탐험가들은 별의 인도를 따라 끝없는 바다를 건너 새로운 땅을 찾아 나섰다. 이 위대한 여정은 세상의 가장 서쪽, 모든 생명이 시작된 $1$번 섬 하와이키에서 시작되어, 세상의 끝이자 동쪽 가장 멀리 떨어진 $N$번 섬 테 피토에서 끝난다.

광활한 태평양에는 $N$개의 섬과 이들을 잇는 $M$개의 고대 항로가 존재한다. $i$번 섬은 2차원 평면 위의 점 $(X_i, Y_i)$로 표현되며, 각 섬은 서로 겹치지 않는 고유한 좌표를 갖는다. 두 섬을 잇는 항로는 언제나 직선이며, 항로들은 양 끝 섬이 아닌 곳에서 교차하지 않는다.

항해사들은 고대의 항로를 따라 이동하며 항로를 점검하는 임무를 맡았다. 강한 서풍으로 인해 항해사들은 반드시 동쪽으로, 즉 $x$좌표가 증가하는 방향으로만 항해해야 한다. 항해사들은 각자 하와이키에서 출발하여 항로를 따라 테 피토에 도착하는 경로를 하나씩 선택하여 이동한다.

$j$번 항로는 $U_j$번 섬과 $V_j$번 섬을 연결하며, 중요도에 따라 $W_j$명 이상의 항해사가 점검해야 한다. 이때, 모든 항로의 조건을 만족시키기 위해 필요한 항해사 수의 총합을 최소화하려고 한다.

총 항해사 수가 최소가 되도록 배치했을 때, 각 항로를 통과하는 항해사 수를 구하여라.

제약 조건

• $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$)
• 모든 항로의 조건을 만족시키는 항해사 구성이 존재한다.
• $1$번 섬에서 모든 섬에 도달 가능하다.
• 주어진 모든 수는 정수이다.

부분문제

1. (2점) $M = N - 1$
2. (14점) $\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점) $\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점) $N \le 300$
5. (44점) 추가 제약 조건 없음.

입력 형식

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

다음 $N$개의 줄의 $i$번째 줄에는 $X_i$, $Y_i$가 공백으로 구분되어 주어진다.

다음 $M$개의 줄의 $j$번째 줄에는 $U_j$, $V_j$, $W_j$가 공백으로 구분되어 주어진다.

출력 형식

총 $M$개의 줄을 출력한다. $j$번째 줄에는 $j$번 항로를 지나는 항해사 수를 출력한다.

가능한 정답이 여러 개라면 그 중 하나를 아무거나 출력한다.

예제

예제 1

입력

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

출력

3
2
1
2
3