Phủ sóng

Trên một vùng không gian phẳng cực lớn được mô tả như một bảng số có kích thước \((10^9 + 1) \times (10^9 + 1)\), các hàng được đánh số từ \(0\) đến \(10^9\), các cột cũng tương tự. Ô nằm ở cột \(x\) và hàng \(y\) thì được gọi là ô \((x, y)\) với \(0 \le x, y \le 10^9\).

Ban đầu có \(N\) máy phát tín hiệu được đặt tại các ô \((x_i, y_i)\). Mỗi máy phát có hai thuộc tính:

• \(D_i\): bán kính phủ sóng của máy phát.
• \(S_i\): cường độ tín hiệu phát ra.

Máy phát tại \((x_i, y_i)\) sẽ phát sóng đến toàn bộ các ô \((x, y)\) thỏa mãn:

Nếu một ô nằm trong phạm vi phủ sóng của nhiều máy phát, cường độ tại ô đó là tổng các \(S_i\) của những máy phát phủ sóng được nó.

Có \(Q\) truy vấn, mỗi truy vấn yêu cầu bạn tính tổng cường độ tín hiệu tại một ô \((u, v)\).

\InputFile

• Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \le N \le 2 \cdot 10^5\)) --- số lượng máy phát.
• \(N\) dòng tiếp theo, mỗi dòng gồm 4 số nguyên \(x_i\), \(y_i\), \(D_i\), \(S_i\) (\(0 \le x_i, y_i \le 10^9\), \(0 \le D_i \le 10^9\), \(1 \le S_i \le 10^9\)) --- thông tin của máy phát thứ \(i\).
• Dòng tiếp theo chứa một số nguyên \(Q\) (\(1 \le Q \le 2 \cdot 10^5\)) --- số lượng truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên \(u\), \(v\) --- tọa độ của ô cần truy vấn (\(0 \le u, v \le 10^9\)).

\OutputFile

In ra \(Q\) dòng, dòng thứ \(i\) là tổng cường độ tín hiệu tại ô được hỏi trong truy vấn thứ \(i\).

\Scoring

• Subtask 1 (15% số điểm): \(N \le 100\), \(0 \le x_i, y_i, u, v \le 100\), \(D_i \le 100\).
• Subtask 2 (15% số điểm): \(N \le 1000\), \(0 \le x_i, y_i, u, v \le 1000\), \(D_i \le 1000\).
• Subtask 3 (18% số điểm): \(N \le 1000\), \(Q \le 1000\).
• Subtask 4 (52% số điểm): Không có ràng buộc gì thêm.

Example

3
1 1 1 5
2 2 1 7
3 3 2 10
2
1 1
2 2

5
17

2
0 0 1 3
10 10 1 7
3
0 0
1 1
10 10

3
0
7