Các nhà khoa học đang nghiên cứu về tổ kiến, họ mô phỏng tổ kiến trên một lưới ô vuông \(n \cdot m\) bao gồm \(k\) ô \((x_i, y_i)\). Các ô này có cấu trúc theo dạng cây, hai ô kề cạnh có thể di chuyển qua nhau, hai ô bất kì có thể di chuyển qua lại lẫn nhau thông qua một đường đi duy nhất không lặp lại các ô. Bây giờ các nhà khoa học quan tâm đến việc nếu xét một hình chữ nhật \((x_1, y_1, x_2, y_2)\) và xem xét các ô thuộc tổ kiến nằm trong hình chữ nhật này thì sẽ có bao nhiêu thành phần liên thông. Các nhà khoa học sẽ xem xét nhiều kịch bản là các hình chữ nhật khác nhau.

Yêu cầu: Cho dữ liệu về tổ kiến và \(q\) truy vấn, mỗi truy vấn là một hình chữ nhật, hãy đếm số thành phần liên thông trong hình chữ nhật đó.

Input

• Dòng đầu chứa hai số nguyên \(n, m\) (\(1 \le n, m \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa số nguyên \(k, q\) (\(2 \le k \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5\)).
• \(k-1\) dòng tiếp theo, mỗi dòng chứa \(f_i, x_i, y_i\) mô tả ô \((x_i, y_i)\) thuộc tổ kiến kết nối với ô \((x_i+1, y_i)\) nếu \(f_i =\) h, hoặc kết nối với ô \((x_i, y_i+1)\) nếu \(f_i =\) v (\(1 \le x_i \le n, 1 \le y_i \le m\)). Dữ liệu đảm bảo các ô này tạo thành một cây.
• \(q\) dòng tiếp theo mỗi dòng chứa bốn số \(x_1, y_1, x_2, y_2\) (\(1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le m\)). Các ô \((x, y)\) được coi là nằm trong hình chữ nhật thỏa mãn \(x_1 \le x \le x_2, y_1 \le y \le y_2\).

Output

• Ghi ra \(q\) dòng là kết quả của mỗi truy vấn.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, m, k, q \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, m, k, q \le 3000\).
• Subtask \(3\) (\(30\%\) số điểm): \(n, m \le 3000, k, q \le 10^5\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 3
8 4
v 1 1
h 1 1
h 2 1
v 2 1
v 2 2
h 1 3
h 3 1
1 1 4 3
3 2 4 3
3 1 3 1
1 2 3 3

1
0
1
2