题目描述

DQY 最近学了树，矩阵和联通块，他打算把这些结合起来帮助 Sooty 出一道题，他先给出一个 $n,m$ 的矩阵，给一棵树，大小为 $k$，这颗树在矩阵上，树的形式是这样给出的：

v a b，表示从 $(a,b)$ 向 $(a,b+1)$ 连一条边。

h a b，表示从 $(a,b)$ 向 $(a+1,b)$ 连一条边。

保证最后一定是颗树。然后有 $q$ 个询问，每次询问在某一个子矩阵 $(x1,y1),(x2,y2)$ 内的树被分成了几个联通块。

输入格式

输入第一行两个数 $n,m$。

第二行两个数 $k,q$。

接下来 $k-1$ 行是对树的描述。

接下来 $q$ 行是询问。

输出格式

​在某一个子矩阵 $(x1,y1),(x2,y2)$ 内的树被分成了几个联通块。

样例

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

样例解释

数据分组