Tổ kiến

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\times m$ bao gồm $k$ ô $(x_i,y_i)$. Các ô này có cấu trúc theo dạng cây: giữa một số cặp ô kề cạnh có kết nối, và hai ô có kết nối có thể di chuyển qua lại lẫn nhau; hai ô bất kì của tổ kiến 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 ô. Hai ô kề cạnh nhưng không có kết nối thì không đi trực tiếp sang nhau đượ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 (chỉ đi qua các ô của tổ kiến nằm trong hình chữ nhật, theo các kết nối). 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 đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n,m$ ($1\le n,m\le 2·{10}^5$).
• Dòng thứ hai chứa hai số nguyên $k,q$ ($2\le k\le 2·{10}^5$, $1\le q\le 2·{10}^5$).
• $k-1$ dòng tiếp theo, mỗi dòng chứa $f_i,x_i,y_i$ mô tả một kết nối: ô $(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$, ô được kết nối cũng nằm trong lưới). Các ô thuộc tổ kiến là các ô xuất hiện trong các kết nối; dữ liệu đảm bảo có đúng $k$ ô như vậy và các ô này cùng $k-1$ kết nối 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 nếu thỏa mãn $x_1\le x\le x_2$, $y_1\le y\le y_2$.

Dữ liệu ra

In ra $q$ dòng, dòng thứ $j$ là kết quả của truy vấn thứ $j$.

Ràng buộc

• $1\le n,m\le 2·{10}^5$.
• $2\le k\le 2·{10}^5$, $1\le q\le 2·{10}^5$.
• $f_i$ là kí tự $h$ hoặc $v$, $1\le x_i\le n$, $1\le y_i\le m$.
• $1\le x_1\le x_2\le n$, $1\le y_1\le y_2\le m$.

Subtasks

• $20\%$ số test có $n,m,k,q\le 100$.
• $20\%$ số test có $n,m,k,q\le 3000$.
• $30\%$ số test có $n,m\le 3000$, $k,q\le {10}^5$.
• $30\%$ số test còn lại không có ràng buộc gì thêm.

Ví dụ