Description

小Q最近喜欢上了一款游戏，名为《舰队connection》，在游戏中，小Q指挥强大的舰队南征北战，从而成为了一名

dalao。在战斗中，布阵往往是决定胜败的关键，其中梯形阵捉摸不定的攻守能力深受小Q喜爱。

【题意描述】

小Q的舰队有n艘船在海上航行，每艘船都拥有自己的坐标(xi,yi)。我们规定x表示行，y表示列，x从上到下增加，

y从左到右增加，左上角为(1,1)，右下角为(Xmax, Ymax)。梯形阵由舰队中的至少4艘船构成，阵中的所有船只都

在一条直线上，且刚好与坐标轴夹角为45度。阵型中所有船只组成的线段上不能有其他的船只，但延长线上可以有

其他船只。例如，在以下阵列中(.表示海，*表示船)

.*.**.

.**.

....

**..*.

...*

....*.

存在6种梯形阵，其中3种如下(被X标注的为阵中的船只)：

..**...X*..*.*X.

X...X.*.X.

.X....X.......

**...X..*.X...

..X.**...X...*

....X...........

另外的3种均在同一条直线上，但它们被视为不同的梯形阵，如下：

.X...*...X.**.

.X*..X**..X**.

..X....X...*.X..

..X...X.**..X.

...**...X..*.X

..............*.

需要注意的是，以下三种不被认为是梯形阵，因为它们所在线段上包含了其他船只。

（X表示选出的船只，#表示不合法的其他船只）

.X...X...X.**.

.#**..X**.*.X**.

..X....#...*.X..

..X...X.**..#.

...X*...X..*.X

..............*.

小Q会不断给出两种询问(type, L, R, k)

询问1：在L<=xi<=R的所有船中，至少由1/k的船组成的梯形阵有多少种

询问2：在L<=yi<=R的所有船中，至少由1/k的船组成的梯形阵有多少种

例如，在上图的舰队中：

.*.**.

.**.

....

**..*.

...*

....*.

对于询问(1,1,5,3)来说，1~5行共计15艘船，至少由其中1/3的船即5艘船组成的梯形阵只有1种。

对于询问(1,1,5,4)来说，至少由1/4的船，即15/4艘船组成的梯形阵，由于船必须是整数艘

也即至少4艘船组成，有5种。

对于询问(2,2,5,6)来说，2~5列共计12艘船，至少由1/6的船组成，即至少由2艘船组成

但是梯形阵至少要由4艘船组成，所以只有1种。

Format

Input

第一行三个数，n, Xmax, Ymax，空格分隔，表示船数和最大坐标。

接下来n行，每行两个数Xi, Yi，空格分隔，表示每艘船的位置。

接下来1行，一个数q，表示任务2的询问个数。

接下来q行，每行4个数type, L, R, k，空格分隔，描述一个询问。

n<=200000，1<=Xmax<=500000，1<=Ymax<=500000，1<=q<=100000，1<=k<=n

所有询问k之和不超过200000

Output

共计q行，每行一个数，表示每个询问的答案。

Samples

16 6 6
1 2
1 4
1 5
2 1
2 3
2 4
2 5
3 2
3 4
4 1
4 2
4 5
5 1
5 4
5 6
6 5
3
1 1 5 3
1 1 5 4
2 2 5 6

1
5
1