Yêu cầu:

Tín là một nhà thám hiểm không gian. Sắp đến cậu ấy sẽ tham gia một cuộc thi nhằm tìm kiếm những người cho chuyến du hành không gian 2022 của ASAN. Vì biết đây là một cơ hội ngàn năm có một, Tín không ngừng học hỏi để cải thiện bản thân. Tuy nhiên cậu ấy lại đang phải đối mặt với một vấn đề khó chưa tìm ra lời giải, bạn là người bạn thân của anh ấy và cố gắng giúp Tín giải quyết vấn đề đấy. Mô tả vấn đề như sau:
Tín được cho một dãy số nguyên ~a_1, a_2, ..., a_N~ . Ta định nghĩa độ đẹp của một dãy là số dãy con liên tiếp nhiều nhất có thể trong cách chọn từ dãy đấy các dãy con liên tiếp không giao nhau sao cho tổng của mỗi dãy con đều bằng 0. Cho Q cặp số ~(L_i, R_i)~, Tín được yêu cầu với mỗi cặp số tìm độ đẹp của dãy con liên tiếp ~a_{L_i}, a_{L_{i+1}}, ..., a_{R_i}~ tương ứng.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên N (~1 ≤ N ≤ 4 × 10^5~). • Dòng thứ hai chứa N số nguyên ~a_1, a_2, ..., a_N (|a_i| ≤ 10^9)~. • Dòng thứ ba chứa số nguyên Q (~1 ≤ Q ≤ 4 × 10^5~). • Q dòng tiếp theo mỗi dòng chứa hai số nguyên ~L_i~ và ~R_i~ (~1 ≤ L_i ≤ R_i ≤ N~).

Kết quả:

Ghi ra trên Q dòng, dòng thứ i là độ đẹp của dãy con liên tiếp ~a_{L_i}, a_{L_{i+1}}, ..., a_{R_i}~ tương ứng.

Ví dụ:

Input:

10
1 2 -3 0 1 -4 3 2 -1 1
3
1 10
1 5
2 9

Output:

4
2
2

Giải thích:

Trong dãy con liên tiếp ~a_1, a_2, ..., a_{10}~ ta chọn 4 dãy con liên tiếp không giao nhau gồm các chỉ số {1, 2, 3}, {4}, {5, 6, 7}, {9, 10}.
Trong dãy con liên tiếp ~a_1, a_2, ..., a_5~ ta chọn 2 dãy con liên tiếp không giao nhau gồm các chỉ số {1, 2, 3}, {4}.

Giới hạn:

• Subtask 1 (30%): ~1 ≤ N, Q ≤ 5000~. • Subtask 2 (40%): ~1 ≤ N, Q ≤ 10^5~. • Subtask 3 (30%): Không có giới hạn gì thêm.

Yêu cầu:

Sau kì nghỉ 30/4, 1/5 dài, Huy nhận ra mình có niềm yêu thích mãnh liệt đối với mảnh vườn của nhà anh ấy. Hiện tại Huy đang tức tốc trang trí cho khu vườn của anh ấy bằng 2N viên đá trước khi phải rời xa khu vườn một thời gian. 2N viên đá trong đó có một nửa có màu xanh được đánh số từ 1 đến N, và một nửa còn lại có màu đỏ được đánh số từ 1 đến N, các con số được ghi trực tiếp lên viên đá để dễ dàng phân biệt. Để trang trí khu vườn, Huy sẽ đặt các viên đá trên một đường thẳng và khoảng cách giữa hai viên đá liên tiếp là 1.
Tuy nhiên có một điều mà Huy rất quan tâm là làm sao để khu vườn của mình trở nên "đẹp". Anh ấy mô tả một khu vườn "đẹp" nếu không tồn tại hai viên đá nào có cùng số ghi trên nó mà khoảng cách giữa hai viên đá đấy là bội của M. Thời gian còn lại rất gấp rút, bạn hãy giúp Huy đếm xem thử có bao nhiêu cách sắp xếp 2N viên đá trang trí khu vườn để khu vườn trở nên "đẹp". Hai cách trang trí được xem là khác nhau nếu tồn tại một viên đá thứ i ~(1 ≤ i ≤ 2*N)~ mà trên cách sắp xếp này được đánh số hoặc có màu khác với cách sắp xếp kia.

Dữ liệu:

• Gồm một dòng duy nhất ghi hai số nguyên N, M ~(1 ≤ M ≤ N ≤ 2000)~.

Kết quả:

Ghi ra số nguyên duy nhất là số cách trang trí khu vườn "đẹp". Vì kết quả có thể rất lớn nên chỉ cần đưa ra kết quả sau khi modulo ~10^9 + 7~

Ví dụ:

Input:

5 2

Output:

460800

Input:

1 1

Output:

0

Giới hạn:

• Subtask 1 (10%): ~1 ≤ N, M ≤ 5~.
• Subtask 2 (15%): ~1 ≤ N, M ≤ 100~.
• Subtask 3 (20%): ~1 ≤ N, M ≤ 300~.
• Subtask 4 (30%): ~1 ≤ N, M ≤ 900~.
• Subtask 5 (25%): Không có giới hạn gì thêm.

Yêu cầu:

Trong một lần đi dạo bé mèo Purple đã phát hiện ra một cây (đồ thị vô hướng liên thông không có chu trình) với N đỉnh đánh số từ 1 đến N. Trên cạnh thứ i (~1 ≤ i < N~) nối giữa hai đỉnh ~u_i, v_i~ chứa ~c_i~ trái táo trên đấy.
Vì sức leo trèo có hạn, mèo Purple sẽ chọn đúng K đỉnh sau đó bé mèo sẽ đi từ gốc của cây đến từng đỉnh đã chọn và lấy đi số táo nằm trên các cạnh đi qua, đương nhiên sau mỗi lần lấy hết táo trên một cạnh thì số táo nằm trên cạnh đấy sẽ trở về 0 trái. Purple muốn tối đa hóa số lượng táo có thể lấy được nhưng hiện tại bé mèo vẫn chưa biết được gốc của cây nằm ở đỉnh nào. Bạn hãy giúp bé mèo Purple xác định số lượng táo tối đa có thể lấy được nếu gốc của cây nằm ở đỉnh i ~(\forall i \in [1,N])~.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên N, K ~(1 ≤ K ≤ N ≤ 10^5)~.
• N-1 dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, c_i (1 ≤ u_i, c_i ≤ N, 0 ≤ c_i ≤ 10^9)~.

  Kết quả:

Ghi ra trên N dòng, dòng thứ i là số táo tối đa có thể lấy được nếu chọn gốc của cây là đỉnh i.

Ví dụ:

Input:

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

Output:

28
28
28
32
30
32
28
32
32
29
30

Giới hạn:

• Subtask 1 (10%): ~1 ≤ N ≤ 18~.
• Subtask 2 (15%): ~1 ≤ N ≤ 200, 1 ≤ K ≤ 20~.
• Subtask 3 (20%): ~1 ≤ N ≤ 1000, 1 ≤ K ≤ 100~.
• Subtask 4 (20%): ~1 ≤ N ≤ 2000~.
• Subtask 5 (15%): ~K = 1~.
• Subtask 6 (20%): Không có giới hạn gì thêm.