Bài tập

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.

Cho một cây có gốc gồm \(n\) đỉnh. Các đỉnh được đánh số từ \(1\) đến \(n\), và đỉnh \(1\) là gốc của cây. Mỗi đỉnh \(i\) có một giá trị nguyên dương \(v_i\).

Bạn cần thực hiện \(q\) truy vấn thuộc một trong hai loại sau:

• Thay đổi giá trị: Gán giá trị của đỉnh \(s\) thành \(x\).
• Tính tổng đường đi: Tính tổng giá trị của tất cả các đỉnh trên đường đi từ gốc (đỉnh \(1\)) đến đỉnh \(s\) (bao gồm cả hai đầu).

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \le n, q \le 2 \cdot 10^5)\) --- số lượng đỉnh của cây và số lượng truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(v_1, v_2, \ldots, v_n\) \((1 \le v_i \le 10^9)\) --- giá trị ban đầu của các đỉnh.

\(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \le a, b \le n)\) --- mô tả một cạnh nối giữa hai đỉnh \(a\) và \(b\). Đảm bảo các cạnh này tạo thành một cây.

\(q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• Dạng 1 s x \((1 \le s \le n, 1 \le x \le 10^9)\): thay đổi giá trị của đỉnh \(s\) thành \(x\).
• Dạng 2 s \((1 \le s \le n)\): tính tổng giá trị các đỉnh trên đường đi từ đỉnh \(1\) đến đỉnh \(s\).

Output

Với mỗi truy vấn loại 2, in ra một dòng chứa tổng giá trị cần tìm.

Example

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

11
8

Trong thời gian chờ vào tiết học, An và Lạc cùng nhau chơi một trò chơi đơn giản. An lấy một tờ giấy và học sinh hình chữ nhật kẻ ô vuông có chiều rộng \(W\), chiều cao \(H\) và vẽ một số điểm lên tờ giấy đó. Có thể xem góc dưới bên trái của tờ giấy có tọa độ \((0, 0)\) và góc trên bên phải có tọa độ \((W, H)\). Các điểm có thể vẽ trùng nhau nhưng được tính như các điểm phân biệt.

Lạc lấy ra một mảnh giấy hình chữ nhật có chiều rộng \(w\), chiều cao \(h\) và hai bạn tìm cách đặt mảnh giấy này lên tờ giấy sao cho các cạnh của mảnh giấy song song với các biên của tờ giấy đã vẽ các điểm, chiều rộng và chiều cao mảnh giấy tương ứng với chiều rộng và chiều cao của tờ giấy, và mảnh giấy phủ nhiều điểm nhất có thể. Các điểm nằm trên biên của mảnh giấy cũng được xem là bị phủ.

An, Lạc đã vào lớp. Bạn hãy tiếp tục trò chơi khi tờ giấy và mảnh giấy có kích thước lớn hơn.

Yêu cầu: Cho \(n\) điểm và kích thước \(w, h\) của mảnh giấy, hãy tìm số điểm lớn nhất bị phủ bởi mảnh giấy hình chữ nhật đó.

Input

• Dòng đầu chứa ba số nguyên \(n, w, h\) (\(1 \leq n \leq 10^5\), \(1 \leq w, h \leq 10^8\));
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i, y_i\) là tọa độ của điểm thứ \(i\) được vẽ trên tờ giấy (\(1 \leq x_i, y_i \leq 10^8\)).

Output

In ra một số là số lượng điểm lớn nhất bị phủ bởi mảnh giấy hình chữ nhật.

Example

6 2 3
1 1
3 1
2 2
3 3
5 3
3 5

4

10 8 8
8 9
20 14
3 9
7 8
3 4
7 8
10 19
6 11
5 10
8 2

7

Bạn được cho một cây có \(n\) đỉnh. Mỗi đỉnh trên cây được gán một ký tự là một dấu ngoặc đơn, có thể là ( hoặc ).

Một đường đi đơn giữa hai đỉnh \(u\) và \(v\) tạo ra một chuỗi ngoặc bằng cách ghép các ký tự ngoặc của các đỉnh trên đường đi theo thứ tự. Chuỗi ngoặc này được coi là hợp lệ nếu:

• Tổng số dấu ngoặc mở bằng tổng số dấu ngoặc đóng.
• Với bất kỳ tiền tố nào của chuỗi, số dấu ngoặc mở không nhỏ hơn số dấu ngoặc đóng.

Hãy tìm và đếm số cặp đỉnh \((u, v)\) (với \(u\) và \(v\) là hai đỉnh bất kỳ trên cây) sao cho chuỗi ngoặc được tạo từ đường đi giữa chúng là một chuỗi ngoặc hợp lệ.

Input

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

• Dòng đầu tiên chứa một số nguyên \(n\) (\(2 \le n \le 3 \cdot 10^5\)), là số đỉnh của cây.
• Dòng thứ hai chứa \(n\) ký tự \(s_1, s_2, \ldots, s_n\) (\(s_i \in \{'(', ')'\}\)), trong đó \(s_i\) là ký tự ngoặc tại đỉnh thứ \(i\).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le n, u \ne v\)), biểu thị một cạnh nối giữa hai đỉnh \(u\) và \(v\).

Output

In ra một số nguyên duy nhất là tổng số cặp đỉnh \((u, v)\) thỏa mãn yêu cầu.

Example

6
()()()
1 2
2 3
3 4
3 5
5 6

5

Scoring

• Subtask 1 (30 điểm): \(2 \le n \le 5000\).
• Subtask 2 (70 điểm): Không có ràng buộc bổ sung.