Khoảng khắc năm cũ bước sang năm mới luôn mang trong mình một ý nghĩa to lớn đối với tất cả mọi người. Vào lúc 0h ngày 1/1 năm nay, thành phố Đà Nẵng như thường lệ sẽ tổ chức bắn pháo hoa đón giao thừa. Có tổng cộng \(n\) địa điểm bắn pháo hoa và các địa điểm này được nối với nhau bằng \(n - 1\) con đường hai chiều sao cho giữa hai địa điểm bất kỳ có đúng một đường đi từ địa điểm này sang địa điểm kia. Độ dài mỗi đường đi là số lượng cạnh trên đường đi đó. Ban tổ chức đánh giá độ đẹp và độ ảnh hưởng của các loại pháo hoa như sau:

• Một loại pháo hoa được gọi là có giới hạn ảnh hưởng \(s\) thì nó chỉ ảnh hưởng đến những người dân đứng tại các địa điểm có độ dài quãng đường đến địa điểm bắn loại pháo hoa đó nhỏ hơn hoặc bằng \(s\).
• Một loại pháo hoa được gọi là có giá trị độ đẹp \(c\) thì người dân đứng tại các địa điểm trong giới hạn ảnh hưởng của loại pháo hoa này được hưởng trọn vẹn độ đẹp \(c\).

Có tổng cộng \(m\) loại pháo hoa được bắn. Loại pháo hoa thứ \(i\) (\(1 \leq i \leq m\)) có độ đẹp mắt \(c_{i}\), độ ảnh hưởng \(s_{i}\), và sẽ được bắn liên tục ở địa điểm \(u_{i}\) kể từ giây thứ \(t_{i}\) tính từ thời khắc giao thừa.

Yêu cầu: Bạn cần trả lời \(q\) câu hỏi, câu hỏi thứ \(j\) (\(1 \leq j \leq q\)) yêu cầu tính tổng độ đẹp mắt của các pháo hoa trong giới hạn ảnh hưởng đến người dân đứng ở địa điểm thứ \(v_{j}\) ngay sau giây thứ \(d_{j}\) tính từ giao thừa.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(n, m, q\) (\(1 \leq n, m, q \leq 10^{5}\)) lần lượt là số địa điểm bắn pháo hoa, số loại pháo hoa và số câu hỏi.
• Dòng thứ \(i\) trong số \(n - 1\) dòng tiếp theo chứa hai số nguyên dương \(a_{i}\) và \(b_{i}\) (\(1 \leq a_{i}, b_{i} \leq n\)) thể hiện rằng có con đường hai chiều giữa địa điểm \(a_{i}\) và \(b_{i}\).
• Dòng thứ \(i\) trong số \(m\) dòng tiếp theo chứa ba số nguyên \(t_{i}, u_{i}, c_{i}, s_{i}\) (\(0 \leq t_{i}, c_{i} \leq 10^{7}, 1 \leq u_{i} \leq n, 0 \leq s_{i} < n\)) lần lượt là thời điểm loại pháo hoa thứ \(i\) bắt đầu bắn, địa điểm được bắn, độ đẹp mắt và giới hạn ảnh hưởng của loại pháo hoa đó.
• Dòng thứ \(j\) trong số \(q\) dòng tiếp theo chứa hai số nguyên \(d_{j}\) và \(v_{j}\) (\(0 \leq d_{j} \leq 10^{7}, 1 \leq v_{j} \leq n\)) là nội dung câu hỏi thứ \(j\).

Output

• Ghi ra \(q\) dòng, dòng thứ \(i\) ghi một số nguyên duy nhất là câu trả lời cho câu hỏi thứ \(i\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n, m, q \leq 500\).
• Subtask \(2\) (\(15\%\) số điểm): \(n, m, q \leq 5 \times 10^{3}\).
• Subtask \(3\) (\(15\%\) số điểm): \(a_{i} = i, b_{i} = i + 1, \forall 1 \leq i < n\).
• Subtask \(4\) (\(20\%\) số điểm): \(s_{i} = 1, \forall 1 \leq i \leq m\).
• Subtask \(5\) (\(20\%\) số điểm): \(s_{i} = 2, \forall 1 \leq i \leq m\).
• Subtask \(6\) (\(15\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

20 
20 
0 
10 
30 
0 
30