Bài tập

Quốc gia Zortax bao gồm \(N\) thành phố, được đánh số từ \(1\) đến \(N\), kết nối bởi \(N-1\) con đường hai chiều. Mỗi con đường nối giữa hai thành phố và cho phép di chuyển hai chiều. Toàn bộ hệ thống giao thông tạo thành một mạng lưới liên thông.

Hiện tại, Zortax được chia thành \(K\) vùng, đánh số từ \(1\) đến \(K\). Mỗi thành phố thuộc đúng một vùng. Thành phố thứ \(j\) thuộc vùng \(S_j\) \((1 \le j \le N)\). Mỗi vùng có ít nhất một thành phố.

Tổng thống đương nhiệm -- bà Zelia -- lo ngại rằng đất nước có thể bị chia rẽ bởi mâu thuẫn chính trị giữa các vùng. Zortax được gọi là có nguy cơ ly khai nếu tồn tại cách chia toàn bộ \(N\) thành phố thành hai phe \(X\) và \(Y\) sao cho thỏa mãn tất cả các điều kiện sau:

• Mỗi thành phố thuộc hoặc phe \(X\) hoặc phe \(Y\).
• Cả hai phe đều có ít nhất một thành phố.
• Các thành phố trong cùng một vùng thuộc cùng một phe.
• Có thể di chuyển giữa bất kỳ hai thành phố thuộc phe \(X\) chỉ qua các thành phố thuộc phe \(X\).
• Có thể di chuyển giữa bất kỳ hai thành phố thuộc phe \(Y\) chỉ qua các thành phố thuộc phe \(Y\).

Để đảm bảo sự thống nhất quốc gia, tổng thống Zelia muốn thực hiện các cuộc sáp nhập vùng: mỗi lần, bà chọn hai vùng bất kỳ và gộp lại thành một vùng duy nhất (mọi thành phố của hai vùng sẽ cùng thuộc vùng mới).

Bạn hãy giúp tổng thống tính số lần sáp nhập tối thiểu cần thiết để đảm bảo Zortax không thể ly khai.

Lưu ý: nếu ban đầu chỉ có một vùng (\(K = 1\)), thì quốc gia chắc chắn không thể bị chia rẽ.

\InputFile

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) \((1 \le N \le 5 \times 10^5, 1 \le K \le N)\).
• \(N - 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(A_i, B_i\) \((1 \le A_i, B_i \le N)\), biểu diễn một con đường nối hai thành phố.
• \(N\) dòng tiếp theo, dòng thứ \(j\) chứa số \(S_j\) \((1 \le S_j \le K)\) --- mã vùng của thành phố thứ \(j\).

\OutputFile

In ra một số nguyên --- số lần sáp nhập tối thiểu để Zortax không thể bị chia rẽ nữa.

\Scoring

• Subtask 1 (20%): \(N \le 100\), \(K \le 7\)
• Subtask 2 (33%): \(N \le 3000\)
• Subtask 3 (20%): \(N \le 100\,000\), \(K \le 50\)
• Subtask 4 (27%): Không có ràng buộc bổ sung

Example

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

1

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

0

Bạn đang chơi một trò chơi điện tử nổi tiếng của Marvel có tên là Dr. Strange. Trong trò chơi này, bạn nhập vai một siêu anh hùng đang giải cứu thế giới bằng cách hấp thụ sức mạnh của các quái vật.

Bạn được cung cấp danh sách \(N\) quái vật. Quái vật thứ \(i\) xuất hiện tại thời điểm \(L_i\) và tồn tại cho đến thời điểm \(R_i\) (bao gồm cả \(L_i\) và \(R_i\)). Mỗi quái vật có một cấp độ sức mạnh \(P_i\). Nhiều quái vật có thể xuất hiện cùng một lúc.

Để chiến đấu, bạn thực hiện \(M\) lần hấp thụ sức mạnh liên tiếp theo thứ tự. Trước lần hấp thụ đầu tiên, bạn bắt đầu với một giá trị sức mạnh đã hấp thụ ban đầu là \(\text{Power}_0 = 1\) (hấp thụ từ chính bản thân bạn).

Đối với mỗi lần hấp thụ \(j = 1, 2, \ldots, m\), năng lượng khả dụng \(E_j\) của bạn tại thời điểm đó được tính theo công thức:

Trong đó, \(D_j\) là hệ số độ bền (durability), \(A_j\) là hệ số nhanh nhẹn (agility), \(F_j\) là mức độ mệt mỏi (fatigue) ở lần hấp thụ \(j\), và \(\text{Power}_{j-1}\) là tổng sức mạnh quái vật đã hấp thụ được trong lần di chuyển trước đó (\(j-1\)).

Vì bạn là Dr. Strange, bạn có khả năng du hành thời gian. Tại thời điểm \(t_j\) của lần hấp thụ thứ \(j\), với năng lượng \(E_j\) này, bạn sẽ hấp thụ sức mạnh của \(E_j\) quái vật yếu nhất (những quái vật có cấp độ sức mạnh \(P\) nhỏ nhất) đang hiện diện. Nếu tại thời điểm đó có ít hơn \(E_j\) quái vật, bạn sẽ hấp thụ tất cả chúng. Việc hấp thụ sức mạnh của chúng chỉ ảnh hưởng đến năng lượng của bạn mà không làm yếu hay loại bỏ bất kỳ quái vật nào.

Gọi \(\text{Power}_j\) là tổng sức mạnh hấp thụ được trong lần di chuyển thứ \(j\). Nhiệm vụ của bạn là xác định giá trị của \(\text{Power}_1, \text{Power}_2, \ldots, \text{Power}_m\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N, M\) -- số lượng quái vật và số lần hấp thụ (\(1 \le N, M \le 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(L_i, R_i, P_i\) -- thời điểm xuất hiện, thời điểm biến mất, và cấp độ sức mạnh của quái vật thứ \(i\) (\(1 \le L_i \le R_i \le 10^5\), \(1 \le P_i \le 10^7\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(t_j, D_j, A_j, F_j\) -- thời điểm thực hiện lần hấp thụ \(j\) và các hệ số tính toán năng lượng. Lưu ý rằng tất cả các giá trị \(t_j\) là một hoán vị của các số từ \(1\) đến \(M\) (\(1 \le t_j \le M\), \(0 \le D_j, A_j \le 10^5\), \(1 \le F_j \le 10^5\)).

Output

In ra \(M\) dòng. Mỗi dòng chứa một số nguyên duy nhất là tổng sức mạnh hấp thụ được trong lần di chuyển thứ \(j\).

Example

3 3
1 2 10
2 3 20
1 3 5
1 2 2 2
3 3 1 3
2 1 1 5

5
25
15

Scoring

• Subtask \(1\) (\(20\%\) số điểm) : \(N, M \leq 100\).
• Subtask \(2\) (\(20\%\) số điểm) : \(N, M \leq 2000\).
• Subtask \(3\) (\(20\%\) số điểm) : \(M = 1\).
• Subtask \(4\) (\(20\%\) số điểm) : \(t_j < t_{j + 1}\) với mọi \(i = 1..M-1\).
• Subtask \(5\) (\(20\%\) số điểm) : không có ràng buộc gì thêm.

Để chuẩn bị cho ngày lễ kỷ niệm của trường, các bạn trong lớp được giao nhiệm vụ trang trí hai bên tường lớp học bằng các dải màu. Mỗi bên tường sẽ được trang trí theo một quy luật riêng, lặp lại tuần hoàn vô hạn.

Cụ thể:

• Bên trái lớp học được trang trí theo một dãy màu \(a_1, a_2, \dots, a_n\), và dãy này sẽ lặp lại vô hạn: \(a_i = a_{i+n}\) với mọi \(i\).
• Bên phải lớp học được trang trí theo một dãy màu \(b_1, b_2, \dots, b_m\), và cũng lặp lại vô hạn: \(b_i = b_{i+m}\) với mọi \(i\).

Bạn Kino là người rất tinh mắt, muốn kiểm tra mức độ khác biệt giữa hai bên tường. Cụ thể, Kino chọn ra \(k\) vị trí đầu tiên (tính từ trái sang phải) và đo độ khác biệt màu sắc giữa hai bên tường ở mỗi vị trí. Độ khác biệt giữa hai màu \(a_i\) và \(b_i\) tại cùng vị trí được xác định bằng phép toán XOR bitwise: \(a_i \oplus b_i\).

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, k\) \((1 \leq n, m \leq 10^5,\ 1 \leq k \leq 10^{18})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((0 \leq a_i \leq 10^{18})\).
• Dòng thứ ba chứa \(m\) số nguyên \(b_1, b_2, \dots, b_m\) \((0 \leq b_i \leq 10^{18})\).

Output

In ra một số nguyên duy nhất --- tổng độ khác biệt ở \(k\) vị trí đầu tiên, chia dư cho \(10^9 + 7\).

Example

10 5 30
5 16 2 10 7 2 4 20 5 12
4 11 14 23 5

435

3 2 10
1 6 4
5 2

33

Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 18 & \(k \leq 2 \cdot 10^5\)

2 & 13 & \(n\) \(mod\) \(m = 0\)

3 & 30 & \(k \le 10^9\)

4 & 39 & Không có ràng buộc bổ sung

\hline
\endtabular

Trong giờ học Vật lý, một thành viên của CLB CHTCoder đang lơ đãng nhớ về crush thì bị thầy phát hiện.

Để không bị trừ điểm hoặc ghi vào sổ đầu bài, thầy đã giao cho hai bạn một thử thách:
Cho một bảng kích thước \(n \times n\), trong đó các số được điền theo thứ tự tăng dần từ trái sang phải và từ trên xuống dưới, bắt đầu từ \(1\) cho tới \(n \times n\).

Yêu cầu của thầy rất đơn giản: Tính tổng các phần tử nằm trên đường chéo chính của bảng.

Input

Đọc từ file NHOEM.INP:

• Số nguyên dương \(t\) (\(1 \le t \le 10^{6}\)) --- số câu hỏi.
• Mỗi dòng tiếp theo chứa một số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).

Output

Ghi ra file NHOEM.OUT:

• Gồm \(t\) dòng, mỗi dòng là tổng đường chéo chính tương ứng.

Example

2
3
6

15
111

Scoring

• Subtask 1 (70%): \(1 \le t, n \le 10^{3}\).
• Subtask 2 (30%): Không có ràng buộc thêm.