Bài tập

Cho một cây gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\), trong đó đỉnh \(1\) là gốc của cây. Tất cả các đỉnh trên đường đi từ đỉnh \(1\) đến đỉnh \(u\) được gọi là tổ tiên của đỉnh \(u\). Mỗi đỉnh đều có hai loại trọng số: đỉnh thứ \(i\) có trọng số của đỉnh là \(a_i\) và trọng số tổ tiên là \(b_i\).

Tổ tiên chung gần nhất của một tập đỉnh là đỉnh chung đầu tiên của các đỉnh khi đi về đỉnh gốc \(1\) (nếu tập hợp gồm \(1\) đỉnh thì tổ tiên chung gần nhất là chính đỉnh đó).

Xét một tập hợp gồm \(k\) \((0 < k \le N)\) đỉnh phân biệt bất kì \(\{u_1, u_2, \dots, u_k\}\). Gọi \(p\) là tổ tiên chung gần nhất của \(k\) đỉnh. Khi đó giá trị của tập đỉnh này được tính bằng công thức:

Vậy một cây \(N\) đỉnh sẽ có \(2^N - 1\) tập đỉnh phân biệt.

Yêu cầu. Hãy tính tổng giá trị của tất cả các tập đỉnh có thể tạo ra. Vì kết quả có thể rất lớn nên in ra phần dư của kết quả khi chia cho \(10^9 + 7\).

\InputFile

• Dòng đầu tiên chứa số nguyên dương \(N\) \((N \le 10^6)\) là số đỉnh của cây.
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) \((a_i \le 10^9;\ 1 \le i \le N)\) mô tả trọng số đỉnh của các đỉnh từ đỉnh \(1\) đến đỉnh \(N\).
• Dòng thứ ba chứa \(N\) số nguyên dương \(b_1, b_2, \dots, b_N\) \((b_i \le 10^9;\ 1 \le i \le N)\) mô tả trọng số khi nó là tổ tiên của các đỉnh từ đỉnh \(1\) đến đỉnh \(N\).
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) \((u, v \le N)\) mô tả một cạnh của cây.

\OutputFile

• Gồm một số nguyên duy nhất là kết quả của bài toán sau khi lấy phần dư khi chia cho \(10^9 + 7\).

\Examples
\beginexample
\exmp
3
1 1 2
2 1 2
1 2
1 3

21

\endexample

\Note
Với cây trong ví dụ (gốc \(1\), hai con là \(2\) và \(3\)):

• Tập \(\{1\}\) có giá trị: \(2\);
• Tập \(\{2\}\) có giá trị: \(1\);
• Tập \(\{3\}\) có giá trị: \(4\);
• Tập \(\{1, 2\}\) có giá trị: \(2\);
• Tập \(\{1, 3\}\) có giá trị: \(4\);
• Tập \(\{2, 3\}\) có giá trị: \(4\);
• Tập \(\{1, 2, 3\}\) có giá trị: \(4\).

Tổng là \(21\).

\Scoring

• (\(20\%\)) \(N \le 15\) và cây có dạng đường thẳng: đỉnh \(1\) nối với đỉnh \(2\), đỉnh \(2\) nối với đỉnh \(3\), …, đỉnh \(N-1\) nối với đỉnh \(N\);
• (\(20\%\)) \(N \le 15\);
• (\(20\%\)) Cây có dạng đường thẳng: đỉnh \(1\) nối với đỉnh \(2\), đỉnh \(2\) nối với đỉnh \(3\), …, đỉnh \(N-1\) nối với đỉnh \(N\);
• (\(20\%\)) Mọi trọng số đỉnh của các đỉnh đều là \(1\);
• (\(20\%\)) Không có ràng buộc thêm.

\endproblem

Bạn được cho một mảng \(w\) gồm \(N\) số nguyên không âm.
Có \(M\) truy vấn, truy vấn thứ \(j\) cho bởi ba số \((l_j, r_j, k_j)\).

Với mỗi truy vấn, hãy kiểm tra xem có thể sắp xếp đoạn

thành dãy không giảm hay không, nếu chỉ được phép hoán đổi hai phần tử kề nhau trong đoạn khi tổng của chúng không vượt quá \(k_j\).

Sau mỗi truy vấn, mảng trở lại trạng thái ban đầu.

\InputFile

• Dòng đầu tiên chứa hai số nguyên \(N, M\) (\(1 \le N, M \le 10^6\)).
• Dòng thứ hai chứa \(N\) số nguyên \(w_i\) (\(0 \le w_i \le 10^9\)).
• Mỗi dòng trong \(M\) dòng tiếp theo chứa ba số \(l_j, r_j, k_j\) (\(1 \le l_j \le r_j \le N\), \(0 \le k_j \le 2\cdot 10^9\)).

\OutputFile
Với mỗi truy vấn, in ra 1 nếu có thể sắp xếp đoạn, và 0 nếu không thể.

\Scoring

• Subtask 1 (8 điểm): \(1 \le N, M \le 500\).
• Subtask 2 (9 điểm): \(1 \le N, M \le 5000\).
• Subtask 3 (13 điểm): \(1 \le N, M \le 10^6\), \(0 \le k_j < w_i\) với mọi \(i\).
• Subtask 4 (23 điểm): \(l_i=1, r_i=n\) với mọi \(i\).
• Subtask 5 (24 điểm): \(1 \le N, M \le 2\cdot 10^5\).
• Subtask 6 (23 điểm): Không có ràng buộc bổ sung.

Example

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

1
0

Giang hiện đang là kiến trúc sư trưởng cho tập đoàn viễn thông đa quốc gia G-Network. Hệ thống mạng lưới của tập đoàn bao gồm \(n\) trạm trung chuyển được đánh số từ \(1\) đến \(n\). Để tối ưu hóa chi phí vận hành, các trạm này được kết nối với nhau bởi \(n-1\) tuyến cáp quang hai chiều, sao cho giữa hai trạm bất kỳ luôn tồn tại một đường đi duy nhất. Mỗi tuyến cáp kết nối giữa trạm \(u\) và trạm \(v\) có độ dài vật lý là \(w\).

Trong chiến lược mở rộng thị trường, tập đoàn sẽ kích hoạt các trạm phát sóng tại các vị trí chiến lược. Giả sử tại một thời điểm, có một tập hợp \(S\) các trạm được chọn làm trạm phát sóng đặc biệt. Để quản lý dữ liệu từ các trạm này, tập đoàn cần thiết lập một Trung tâm điều hành G.

Vị trí đặt trung tâm G có thể là bất kỳ trạm nào trong số \(n\) trạm của mạng lưới. Để giảm thiểu độ trễ tín hiệu, Giang định nghĩa giá trị G là tổng khoảng cách ngắn nhất từ trung tâm G đến tất cả các trạm phát sóng đặc biệt trong tập \(S\). Trạm được chọn làm trung tâm G phải là trạm có tổng khoảng cách này là nhỏ nhất. (Lưu ý: Có thể có nhiều trạm thỏa mãn điều kiện làm trung tâm G, nhưng giá trị G là duy nhất).

Giang đưa ra \(q\) kế hoạch mở rộng khác nhau. Trong mỗi kế hoạch, anh cung cấp một danh sách gồm \(m\) trạm dự kiến sẽ được kích hoạt theo thứ tự \(a_1, a_2, \dots, a_m\). Đối với mỗi kế hoạch, Giang yêu cầu bạn thực hiện các báo cáo phân tích sau:
Với mỗi số nguyên \(x\) từ \(1\) đến \(m\), hãy tính giá trị G tại thời điểm tập trạm phát sóng đặc biệt mới chỉ gồm \(x\) trạm đầu tiên trong danh sách kích hoạt: \(S = \{a_1, a_2, \dots, a_x\}\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \leq n, q \leq 2 \times 10^{5}\)) --- số lượng trạm và số lượng kế hoạch.
• Trong \(n - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v\) và \(w\) (\(1 \leq u, v \leq n, 1 \leq w \leq 10^{6}\)) mô tả một tuyến cáp quang nối trạm \(u\) và \(v\) với độ dài \(w\).

• \(q\) dòng tiếp theo, mỗi dòng mô tả một kế hoạch:

• Số đầu tiên là \(m\) (\(1 \leq m \leq n\)) --- số lượng trạm dự kiến kích hoạt.

• Tiếp theo là \(m\) số nguyên phân biệt \(a_1, a_2, \dots, a_m\) (\(1 \le a_i \le n\)) theo đúng thứ tự kích hoạt.

• Tổng giá trị \(m\) trong tất cả các truy vấn không vượt quá \(6 \times 10^{5}\).

Output

• Với mỗi kế hoạch (truy vấn), in ra \(m\) số nguyên trên một dòng, số thứ \(x\) là giá trị G tương ứng với tập \(x\) trạm phát sóng đầu tiên.

Example

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

0 4 4 5 7 
0 3 5 7 

Scoring

• Subtask 1 (17%): \(n \leq 5000\) và tổng \(m \leq 5000\).
• Subtask 2 (19%): Các trạm được nối với nhau thành một đường thẳng (\(1-2-3-\dots-n\)).
• Subtask 3 (20%): Mỗi kế hoạch luôn có đúng \(m = 3\) trạm.
• Subtask 4 (21%): Tất cả các tuyến cáp đều có cùng độ dài \(w = 1\).
• Subtask 5 (23%): Không có ràng buộc gì thêm.

Bước vào cánh cửa đại học, có lẽ thứ ám ảnh nhất đối với Quân hiện tại là môn Giải tích. Cuộc sống Giải tích không hề dễ dàng, cuộc sống như đóng cửa tất cả các con đường của Quân. Tuy nhiên, môn Đại số tuyến tính lại mở ra cho Quân những ý tưởng mới. Mặc dù không có kiến thức về TÍNH GIỚI HẠN LIM LOGARIT ĐẠO HÀM NGUYÊN HÀM VI PHÂN TÍCH PHÂN TÍCH PHÂN BẤT ĐỊNH TÍCH PHÂN SUY RỘNG ĐẠO HÀM CẤP CAO ĐẠO HÀM NHIỀU BIẾN NGUYÊN HÀM VÔ CÙNG LỚN VÔ CÙNG BÉ CHUỖI SỐ L... nhưng Quân lại có khả năng tốt ở môn Đại số tuyến tính. Vì thế Quân đã đăng ký đi thi sơ loại Olympic Toán học Sinh viên của trường Đại học Công nghệ Thông tin tổ chức để thử sức ("mặc dù lý do chính là do thầy dạy Giải tích bảo nếu Quân đi thi thì sẽ được cộng "1" điểm quá trình). Bài toán hôm nay ra khá khó, có một bài liên quan tới các đoạn thẳng, nhưng Quân không giải được, Quân phải mở máy lên code để dễ hình dung hơn thay vì trình bày ra giấy, bài toán như sau:

• Xét \(n\) đoạn thẳng trên trục số, đoạn thẳng thứ \(i\) là đoạn \([l_{i}, r_{i}]\). Hai đoạn thẳng gọi là "giao nhau" khi và chỉ khi tồn tại một số thực \(x\) sao cho \(l_{i} \leq x \leq r_{i}\) và \(l_{j} \leq x \leq r_{j}\). Đếm số cách tô màu các đoạn thẳng sao cho các đoạn thẳng giao nhau có màu khác nhau. Vì kết quả có thể rất lớn, in ra kết quả chia lấy dư cho \(998244353\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n \leq 5 \times 10^5\), \(1 \leq k \leq 10^9\)) --- số lượng đoạn thẳng và số lượng màu.

• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l_i\) và \(r_i\) (\(1 \leq l_i \leq r_i \leq 10^9\)) --- điểm đầu và điểm cuối của đoạn thẳng thứ \(i\).

Output

Với mỗi bộ test, in ra một dòng chứa một số nguyên --- kết quả là số cách để tô màu các đoạn. Vì kết quả có thể rất lớn, hãy in ra kết quả modulo \(998244353\).

Example

4 3
4 7
3 4
5 8
1 3

24

2 1000
100 200
300 400

1000000

Scoring

• \(20\%\) số test có \(n \leq 10\).

• \(10\%\) số test có \(k = 1, n \leq 1000\).

• \(10\%\) số test có \(k = 1, n \leq 5.10^5\).

• \(30\%\) số test có \(n \leq 5000, r_{i} \leq 5000\).

• \(30\%\) số test còn lại không có ràng buộc gì thêm.