Với mỗi submission AC trong thời gian chính thức của contest LQDOJ Cup 2024 - Round #1, các bạn đã đóng góp 12.500 VNĐ vào quỹ ủng hộ đồng bào khắc phục sự cố cơn bão Yagi. Số tiền này sẽ được tổng hợp và chuyển tới Mặt trận Tổ quốc Việt Nam sau khi việc kiểm tra được hoàn tất.

Khánh là một nhà một nhà khoa học tài ba, chuyên nghiên cứu về đồ thị, đặc biệt là cây.

Hôm nay Khánh đang tìm hiểu về một đồ thị vô hướng gồm \(n\) đỉnh được đánh số từ \(1\) đến \(n\), các đỉnh được nối với nhau bằng \(n - 1\) cạnh có trọng số ban đầu là \(0\) sao cho từ một đỉnh có thể đi đến tất cả các đỉnh còn lại.

Bây giờ Khánh có \(q\) truy vấn cập nhật trọng số các cạnh trên đồ thị, các truy vấn được đánh số lần lượt từ \(1\) đến \(q\). Mỗi truy vấn có dạng \(u\) \(v\) \(k\), tức là tăng trọng số các cạnh trên đường đi ngắn nhất từ \(u\) đến \(v\) lên \(k\) đơn vị. Ngoài ra ban đầu anh còn nắm giữ một số nguyên dương \(m\).

Khánh sẽ thực hiện \(t\) kịch bản, ở mỗi kịch bản anh sẽ chỉ thực hiện các truy vấn có chỉ số từ \(l\) đến \(r\), sau khi hoàn thành các truy vấn nêu trên anh muốn chọn \(m\) con đường liên thông với nhau sao cho tổng trọng số của \(m\) con đường ấy là lớn nhất.

Lưu ý rằng các kịch bản là độc lập với nhau, tức là mỗi kịch bản không ảnh hưởng đến các kịch bản khác. Trong mỗi kịch bản, ban đầu, trọng số của tất cả các cạnh bằng \(0\).

Yêu cầu: Với mỗi kịch bản, các bạn hãy tính tổng trọng số lớn nhất của \(m\) con đường liên thông.

Input

• Dòng đầu tiên chứa các số nguyên \(n, q, t\) và \(m\) \((2 \leq n \leq 10^{5}, 1 \leq q \leq 5 \times 10^{5}, 1 \leq t \leq 200, 1 \le m \leq min(n-1, 8)\)).
• Trong \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n)\) mô tả một cạnh của đồ thị.
• Trong \(q\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(u\), \(v\) và \(k\) \((1 \leq u, v \leq n, 1 \leq k \leq 100)\) mô tả truy vấn truy vấn thứ \(i\).
• Trong \(t\) dòng cuối cùng, dòng thứ \(i\) chứa hai số nguyên \(l\) và \(r\) \((1 \leq l \leq r \leq q)\) mô tả một kịch bản.

Output

• In ra \(t\) dòng là đáp án cho \(t\) kịch bản.

Scoring

• Subtask \(1\) (\(26\%\) số điểm): \(n \leq 15\).
• Subtask \(2\) (\(22\%\) số điểm): với mọi truy vấn, \(u\) và \(v\) là \(2\) đỉnh có cạnh nối trực tiếp.
• Subtask \(3\) (\(20\%\) số điểm): \(m \leq 3\)
• Subtask \(4\) (\(17\%\) số điểm): \(q \leq 10^{4}\)
• Subtask \(5\) (\(15\%\) số điểm): không có rằng buộc gì thêm.

Example

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

4
26
25
15