Bài tập

Cho một cây có \(n\) đỉnh và \(n-1\) cạnh, các cạnh đánh số từ \(0\) đến \(n-2\). Mỗi cạnh \(i\) có trọng số ban đầu \(c_i\). Cây được mô tả bởi \(n-1\) cạnh và đảm bảo là một cây liên thông.

Có \(q\) cập nhật, mỗi cập nhật thay đổi trọng số của một cạnh. Sau mỗi lần cập nhật, yêu cầu tính và in ra đường kính của cây.

Đường kính của cây được định nghĩa là khoảng cách lớn nhất giữa hai đỉnh bất kỳ trong cây, với khoảng cách được tính theo trọng số của các cạnh.

Mỗi dòng cập nhật bao gồm hai số nguyên \(d_j\) và \(e_j\), sau đó được chuyển đổi thành \(d'_j\) và \(e'_j\) theo công thức:

• \(d'_j = (d_j + \text{last}) \mod (n - 1)\);
• \(e'_j = (e_j + \text{last}) \mod w\).

Tại đây, last là kết quả của đường kính được tính sau cập nhật trước đó, ban đầu last = 0.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(q\), và \(w\) \((2 \leq n \leq 10^5, 1 \leq q \leq 10^5, 1 \leq w \leq 2 \times 10^{13})\) -- số đỉnh của cây, số lượng cập nhật và giới hạn trọng số của các cạnh.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a_i\), \(b_i\), \(c_i\) \((1 \leq a_i, b_i \leq n, 0 \leq c_i < w)\) -- mô tả một cạnh nối hai đỉnh \(a_i\) và \(b_i\) với trọng số ban đầu \(c_i\).
• \(q\) dòng cuối cùng, mỗi dòng chứa hai số nguyên \(d_j\), \(e_j\) \((0 \leq d_j < n-1, 0 \leq e_j < w)\) -- các truy vấn cập nhật.

Output

• In ra \(q\) dòng, mỗi dòng chứa một số nguyên biểu diễn đường kính của cây sau mỗi cập nhật.

Example

4 3 2000
1 2 100
2 3 1000
2 4 1000
2 1030
1 1020
1 890

2030
2080
2050

10 10 10000
1 9 1241
5 6 1630
10 5 1630
2 6 853
10 1 511
5 3 760
8 3 1076
4 10 1483
7 10 40
8 2051
5 6294
5 4168
7 1861
0 5244
6 5156
3 3001
8 5267
5 3102
8 3623

6164
7812
8385
6737
6738
7205
6641
7062
6581
5155

Scoring

• Subtask 1 (13 điểm): \(n, q \leq 100\) và \(w \leq 10{,}000\).
• Subtask 2 (15 điểm): \(n, q \leq 5{,}000\) và \(w \leq 10{,}000\).
• Subtask 3 (18 điểm): \(w \leq 10{,}000\), và các cạnh của cây chính là tất cả các cạnh hợp lệ dạng \(\{i, 2i\}\) và \(\{i, 2i+1\}\) (tức cây là một cây nhị phân cân bằng nếu gốc tại đỉnh \(1\)).
• Subtask 4 (24 điểm): Đảm bảo rằng sau mỗi lần cập nhật, đường đi đơn dài nhất đi qua đỉnh \(1\).
• Subtask 5 (30 điểm): Không có ràng buộc thêm.

Trong một hệ thống xử lý tín hiệu số, có \(n\) bộ phát được đánh số từ \(1\) đến \(n\). Bộ phát thứ \(i\) có cường độ tín hiệu là \(a_i\).

Hệ thống sử dụng biểu diễn nhị phân của chỉ số các bộ phát để xác định những tín hiệu có liên quan đến một mã truy vấn \(x\). Một bộ phát thứ \(i\) được xem là phù hợp với mã \(x\) nếu tất cả các bit \(1\) trong biểu diễn nhị phân của \(i\) cũng xuất hiện trong biểu diễn nhị phân của \(x\).

Nói cách khác, bộ phát thứ \(i\) phù hợp với \(x\) khi \(x & i = i\), trong đó \(&\) là phép toán AND trên bit.

Với mỗi số nguyên dương \(x\), ta định nghĩa trọng số của \(x\) là:

tức là tổng cường độ của tất cả các bộ phát thứ \(i\) thỏa mãn \(x & i = i\).

Yêu cầu: Hãy tính lần lượt các giá trị \(f(1), f(2), \ldots, f(2^{\lfloor \log_2 n \rfloor + 1} - 1)\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) — số lượng bộ phát \((1 \leq n \leq 10^6)\).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) — cường độ tín hiệu của các bộ phát \((|a_i| \leq 10^9)\).

Output

• In ra lần lượt các giá trị \(f(1), f(2), \ldots, f(2^{\lfloor \log_2 n \rfloor + 1} - 1)\) trên một dòng, các giá trị cách nhau bởi một dấu cách.

Example

3
3 2 1

3 2 6

Scoring

• Subtask 1 (30 điểm): \(1 \leq n \leq 1000\).

• Subtask 2 (30 điểm): \(1 \leq n \leq 100000\).

• Subtask 3 (40 điểm): Không có ràng buộc gì thêm.

Cho một dãy \(A\) gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\).

Yêu cầu: Hãy tìm đoạn con \([l, r]\) \((1 \le l \le r \le n)\) gồm các phần tử liên tiếp \(A_l, A_{l+1}, \dots, A_{r-1}, A_r\) của dãy \(A\) sao cho tổng \(A_l + A_{l+1} + \dots + A_{r-1} + A_r\) là lớn nhất

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng tiếp theo chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\).

Dữ liệu đảm bảo: \(1 \le N \le 10^5\) và \(|A_i|\le 10^9\).

Output

Một số nguyên là tổng lớn nhất tìm được.

Example

6
2 -3 8 4 -5 3

12

Scoring

• Subtask 1: \(20\%\) số test ứng với \(1 \le N \le 100\)
• Subtask 2: \(20\%\) số test ứng với \(1 \le N \le 10^4\)
• Subtask 3: \(20\%\) số test ứng với \(A_i \ge 0\).
• Subtask 4: \(40\%\) số test không có ràng buộc gì thêm.

Trong một lớp có \(n\) bạn và \(n - 1\) cặp bạn trực tiếp, giữa hai bạn bất kỳ luôn tồn tại một mối quan hệ gián tiếp qua các cặp bạn trung gian này.

Qua một bài kiểm tra, cô giáo nhận thấy bạn thứ \(i\) đã làm được \(a_i\) bài của bài kiểm tra. Bằng một phép thần kỳ nào đó, không có hai bạn nào làm được cùng số lượng bài và mỗi bạn (trừ bạn chỉ làm được 1 bài) đều có ít nhất một người bạn trực tiếp làm được ít bài hơn.

Cô giáo muốn chấm điểm cho các bạn dựa trên thang điểm nguyên từ \(1 \rightarrow k\) sao cho không có hai bạn nào có cùng điểm. Sẽ rất bất công nếu như trong một cặp bạn trực tiếp, bạn này làm ít bài hơn nhưng lại nhận được điểm cao hơn.

Yêu cầu: Hãy tìm số cách chấm điểm hợp lý giúp cô giáo. Hay nói cách khác, gọi \(b_i\) là điểm của bạn thứ \(i\), cô giáo muốn tìm số cách chấm điểm sao cho với mọi cặp bạn trực tiếp gồm bạn \(i\) và bạn \(j\), nếu \(a_i > a_j\) thì \(b_i > b_j\) và ngược lại.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n \leq 10^5\), \(1 \leq k \leq 10^9\)) lần lượt là số bạn và thang điểm của cô giáo.
• Mỗi dòng trong số \(n - 1\) dòng tiếp theo chứa hai số nguyên \(i\) và \(j\) (\(1 \leq i, j \leq n, i \ne j\)) thể hiện một cặp bạn trực tiếp.
• Dòng cuối cùng chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq n\), \(a_i \ne a_j\) \(\forall\) \(i \ne j\)) là số bài làm được mỗi bạn.

Output

• In ra một số nguyên duy nhất là số cách chấm điểm hợp lệ modulo \(10^9 + 7\).

Example

1 4
1

4

3 4
1 2
1 3
1 2 3

8

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

1

Scoring

• Subtask 1 (20% số điểm): \(k \leq 10\).
• Subtask 2 (20% số điểm): \(k \leq 10^2\).
• Subtask 3 (20% số điểm): \(k \leq 10^3\).
• Subtask 4 (20% số điểm): \(k = n\).
• Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.