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 được xếp thành một hàng theo thứ tự từ trái sang phải. Hai địa điểm liền kề cách nhau 1 đơn vị khoảng cách. 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ách địa điểm bắn loại pháo hoa đó một khoảng 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\le i\le 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\le j \le 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ố \(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\).

Example

12 3 7
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

0
20
0
10
10
0
20

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n,m,q \leq 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(n,m,q \leq 5 \cdot 10^3\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.