#1381. 梯形阵

梯形阵

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