Bài tập

Trong buổi lễ mừng chiến thắng tại học viện Chiến lược và Sáng tạo, các thí sinh được tham gia vào một trò chơi mang tên chia kho báu. Có \(N\) kho báu được đặt rải rác trên mặt phẳng tọa độ. Kho báu thứ \(i\) nằm tại ô có tọa độ \((x_i, y_i)\) và có giá trị \(w_i\).

BTC cho phép 4 người chơi chia kho báu theo cách đặc biệt: họ được chọn một cặp số \((X, Y)\) với \(1 \le i < N\). Sau đó, mỗi người sẽ nhận các kho báu nằm trong vùng tương ứng:

• Người thứ nhất nhận các kho báu tại ô có \(x_i < X\) và \(y_i < Y\)
• Người thứ hai nhận các kho báu tại ô có \(x_i < X\) và \(y_i > Y\)
• Người thứ ba nhận các kho báu tại ô có \(x_i > X\) và \(y_i < Y\)
• Người thứ tư nhận các kho báu tại ô có \(x_i > X\) và \(y_i > Y\)

Giá trị của mỗi người là tổng các \(w_i\) của những kho báu họ nhận được. Với mỗi cặp \((X, Y)\), họ sẽ tính chênh lệch lớn nhất giữa hai người bất kỳ. Trong trường hợp lý tưởng là họ nhận được cùng một giá trị thưởng, nhưng thực tế luôn phũ phàng và nếu đã không thể đồng đều, thì 4 người trên muốn chọn (X,Y) sao cho chênh lệch lớn nhất là nhỏ nhất có thể.

Yêu cầu: Với mỗi \(X = i + 0.5\) \((1 \le i < N)\), hãy tìm giá trị chênh lệch nhỏ nhất có thể giữa người nhận được nhiều kho báu nhất và người nhận được ít nhất.

Input

• Dòng đầu tiên chứa số nguyên \(N\) --- số kho báu \((1 \le N \le 2 \cdot 10^5)\).
• \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x_i\), \(y_i\), \(w_i\) --- tọa độ và giá trị của kho báu thứ \(i\) \((1 \le x_i, y_i \le n, 1 \le w_i \le 10^9)\).

Output

• In ra \(N - 1\) dòng, dòng thứ \(i\) chứa số nguyên duy nhất là chênh lệch nhỏ nhất có thể giữa hai người, khi \(X = i + 0.5\).

Example

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

9
8
2
6

Scoring

• Subtask 1 (11 điểm): \(1 \le N \le 200\)
• Subtask 2 (14 điểm): \(1 \le N \le 5000\)
• Subtask 3 (48 điểm): \(1 \le N \le 10^5\)
• Subtask 4 (27 điểm): Không có ràng buộc bổ sung

Bạn được cung cấp một đồ thị vô hướng, có trọng số và liên thông, bao gồm \(n\) đỉnh và \(m\) cạnh. Đảm bảo rằng đồ thị không có khuyên (self-loops) và các cạnh lặp.

Định nghĩa trọng số của một đường đi:

Giả sử đường đi có \(k\) cạnh với các chỉ số \(e_1, e_2, \ldots, e_k\). Trọng số của đường đi được xác định bởi công thức:

\(\text{weight of path} = \sum_{i=1}^k w_{e_i} - \max_{i=1}^k w_{e_i} + \min_{i=1}^k w_{e_i}\)

Nhiệm vụ:

Với mỗi đỉnh \(i\) (\(2 \le i \le n\)), hãy tìm trọng số nhỏ nhất của đường đi từ đỉnh \(1\) đến đỉnh \(i\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \leq n \leq 2 \cdot 10^5; 1 \leq m \leq 2 \cdot 10^5)\) --- số đỉnh và số cạnh của đồ thị.
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(v_i, u_i, w_i\) \((1 \leq v_i, u_i \leq n; 1 \leq w_i \leq 10^9; v_i \neq u_i)\) --- các đỉnh của cạnh thứ \(i\) và trọng số tương ứng.

Output

• In \(n-1\) số nguyên trên một dòng, mỗi số tương ứng với trọng số nhỏ nhất của đường đi từ đỉnh \(1\) đến đỉnh \(i\) \((2 \leq i \leq n)\).

Example

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

1 2 2 4 

6 8
3 1 1
3 6 2
5 4 2
4 2 2
6 1 1
5 2 1
3 2 3
1 5 4

2 1 4 3 1 

7 10
7 5 5
2 3 3
4 7 1
5 3 6
2 7 6
6 2 6
3 7 6
4 2 1
3 1 4
1 7 4

3 4 2 7 7 3 

Scoring

• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n, m \leq 10\).

• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n, m \leq 100\).

• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n, m \leq 500\), \(w_{i}= a\) hoặc \(w_{i} = b\) với \(a\), \(b\) là hằng số.

• \(25\%\) số test tương ứng với \(25\%\) số điểm còn lại không có ràng buộc gì thêm.

Có \(n\) học sinh tham gia một kì thi gồm hai phần: Toán học và Tin học. Học sinh thứ \(i\) (\(1 \le i \le n\)) đạt \(S_i\) điểm phần Toán và \(T_i\) điểm phần Tin.

Hai giáo sư là giáo sư T và giáo sư I sẽ cùng đưa ra quyết định xem học sinh đó có được coi là qua môn hay không, dựa trên các tiêu chí như sau:

• Giáo sư T yêu cầu mỗi học sinh đạt ít nhất \(A\) điểm Toán và ít nhất \(B\) điểm Tin để được qua.
• Giáo sư I chỉ quan tâm tổng điểm: học sinh cần có tổng điểm \(S_i + T_i\) lớn hơn hoặc bằng \(C\) để được qua.
• Một học sinh chỉ được coi là qua môn nếu thỏa mãn cả hai tiêu chí trên.

Tuy nhiên, bạn không biết giá trị cụ thể của \(A\), \(B\), và \(C\). Thay vào đó, bạn nhận được \(q\) bộ ba số nguyên \((X_j, Y_j, Z_j)\) tương ứng với các bộ tiêu chí \((A, B, C)\).

Với mỗi bộ tiêu chí \((X_j, Y_j, Z_j)\), hãy tính xem có bao nhiêu học sinh qua môn.

\InputFile

• Dòng đầu chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(S_i\) và \(T_i\) (\(0 \le S_i, T_i \le 10^9\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(X_j, Y_j, Z_j\) (\(0 \le X_j, Y_j \le 10^9\), \(0 \le Z_j \le 2 \cdot 10^9\)).

\OutputFile

In ra \(q\) dòng, dòng thứ \(j\) là số học sinh qua môn ứng với bộ tiêu chí \((A = X_j, B = Y_j, C = Z_j)\).

\Scoring

• Subtask 1 (10%): \(n, q \le 3000\)
• Subtask 2 (22%): \(S_i, T_i \le 10^5\), \(X_j, Y_j \le 10^5\), \(Z_j = 0\)
• Subtask 3 (40%): \(S_i, T_i \le 10^5\), \(X_j, Y_j \le 10^5\), \(Z_j \le 2 \cdot 10^5\)
• Subtask 4 (28%): Không có ràng buộc bổ sung

\Examples

\beginexample
\exmp
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
2
4
1
1

\endexample

Kể từ khi IOI, thành phố Pattaya sẽ tổ chức cuộc đua Olympic quốc tế về đua tốc độ (IOR) 2011. Ban tổ chức phải tìm ra vòng đua tốt nhất cho cuộc thi này.

Ở vùng Pattaya - Chonburi, có \(N\) thành phố được nối với nhau bởi mạng gồm \(N-1\) đường cao tốc. Mỗi đường cao tốc đều cho phép đi theo cả hai chiều, nối hai thành phố phân biệt và có độ dài đo bằng kilomet là số nguyên. Ngoài ra, có đúng một đường đi giữa cặp hai thành phố bất kỳ, nghĩa là đây là một cấu trúc cây.

Cuộc thi IOR có quy tắc đặc biệt: một vòng đua phải có độ dài đúng \(K\) kilomet, bắt đầu và kết thúc ở hai thành phố phân biệt. Để tối ưu hóa việc tổ chức, vòng đua phải sử dụng ít đường cao tốc nhất có thể.

Yêu cầu: Bạn hãy cho biết số lượng đường cao tốc nhỏ nhất trên vòng đua hợp quy tắc có độ dài đúng \(K\). Nếu không tìm được vòng đua nào như vậy, kết quả sẽ là \(-1\).

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 2 \cdot 10^5\), \(1 \le K \le 10^9\)).
• \(N-1\) dòng tiếp theo, mỗi dòng ghi 3 số \(u, v, l\) (\(1 \le u, v \le N\)), với \(u\) và \(v\) là hai thành phố nối với nhau bằng một đường cao tốc có độ dài \(l\) (\(1 \le l \le 10^9\)).

Output

In ra một số nguyên duy nhất là kết quả của bài toán.

Example

4 3
0 1 1
1 2 2
1 3 4

2

3 3
0 1 1
1 2 1

-1

11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7

2

Scoring

• Subtask 1 (9 điểm): \(1 \le N \le 100, 1 \le K \le 100\). Đỉnh \(i\) sẽ nối đến đỉnh \(i + 1\).
• Subtask 2 (12 điểm): \(1 \le N \le 1000, 1 \le K \le 1000000\).
• Subtask 3 (22 điểm): \(1 \le N \le 200\,000, 1 \le K \le 100\).
• Subtask 4 (57 điểm): Không có giới hạn gì thêm.