Alice có một khu đất trống được chia làm \(m \times n\) mảnh đất hình vuông. Các hàng mảnh đất hình vuông được đánh số từ \(1\) đến \(m\) từ trên xuống dưới, các cột mảnh đất hình vuông được đánh số từ \(1\) đến \(n\) từ trái sang phải. Mảnh đất hình vuông nằm giao giữa hàng \(i\) \((1 \leq i \leq m)\) và cột \(j\) \((1 \leq j \leq m)\) gọi là ô \((i, j)\).

Alice dự định sẽ đi lần lượt từng ô theo đường xoắn ốc cùng chiều kim đồng hồ bắt đầu từ ô \((1, 1)\) để trồng cây trên các mảnh đất hình vuông.

Ví dụ, với khu đất \(4 \times 5\) thì thứ tự các ô Alice đi như hình dưới.

Qua khảo sát, Alice biết rằng có \(k\) ô \((x_{1}, y_{1}), (x_{2}, y_{2}), \ldots, (x_{k}, y_{k})\) không thể trồng cây. Khi đó, nếu Alice đi vào các ô này Alice sẽ bỏ qua và không trồng cây ở đó. Là một người yêu thích toán học, Alice mong muốn mỗi ô sẽ được trồng một số cây đều là số nguyên tố.

Cụ thể, khi đi theo đường xoắn ốc như dự định, nếu vào ô là ô \((u, v)\) trồng được cây và ô này là ô thứ \(t\) trồng được cây (tính từ lúc bắt đầu xuất phát) thì ô \((u, v)\) sẽ được trồng số lượng cây là số nguyên tố lớn thứ \(t\).

Ví dụ, nếu khu đất \(4 \times 5\) có \(7\) ô không thể trồng được cây là \((1, 2), (2, 3), (3, 4), (4, 5), (2, 1), (3, 2), (4, 3)\) thì số cây được trồng tại các ô như hình dưới.

Sau khi trồng cây xong, Alice muốn tính số lượng cây nằm trong hình chữ nhật có ô trái trên là ô \((u_{1}, v_{1})\) và ô phải dưới là ô \((u_{2}, v_{2})\). Hãy giúp Alice trả lời câu hỏi như vậy.

Input

• Dòng đầu chứa bốn số nguyên \(m, n, k, q\) \((m, n \leq 500, k \leq m \times n, q \leq 10^{6})\);
• Dòng thứ \(i\) trong \(k\) dòng sau chứa hai số nguyên \(x_{i}, y_{i}\) \((1 \leq x_{i} \leq m, 1 \leq y_{i} \leq n)\);
• Tiếp theo là \(q\) dòng, mỗi dòng chứa bốn số \(u_{1}, v_{1}, u_{2}, v_{2}\) mô tả một câu hỏi.

Output

• Gồm \(q\) dòng, mỗi dòng là câu trả lời cho câu hỏi tương ứng ở dữ liệu vào.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m = 1, n \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(m \leq 100, n \leq 100\).
• Subtask \(3\) (\(20\%\) số điểm): \(q \leq 10\).
• Subtask \(4\) (\(20\%\) số điểm): không có rằng buộc gì thêm.

Example

4 5 7 2
1 2
2 3
3 4
4 5
2 1
3 2
4 3
1 1 2 2
3 2 4 3

33
60