問題文

(難易度目安 : $500$点)

自然数$N,Q$が与えられます.

さらに$N$個の閉区間により構成される数列$A$が与えられ、$A$の$i$番目の要素について

$・A[i] = [x_i,y_i]$としたとき$1 \le x_i \le y_i \le N　(1 \le i \le N)$

が成り立っています.

区間が好きなAliceさんは、以下の形式のクエリに$Q$個回答しました.

$◎1\le l_1 \le l_2 < r_1 \le r_2 \le N$を満たす$4$つの自然数$(l_1,l_2,r_1,r_2)$が与えられる.

このとき以下の条件を満足する自然数$j(1 \le j \le N)$の個数を答えよ.

$▷A[j] = [x_j,y_j]$としたとき$l_1 \le x_j \le l_2$かつ $r_1 \le y_j \le r_2$

Aliceさん同様各クエリに回答してください.

制約

・入力は全て整数

$・2\le N \le 200000$

$・1\le Q \le 200000$

$・A[i] = [x_i,y_i]$とした時$1 \le x_i \le y_i \le N　(1 \le i \le N)$

◉全クエリにおいて以下が成り立つ.

$・1\le l_1 \le l_2 < r_1 \le r_2 \le N$

入力

入力は以下の形式で与えられます.

N Q
x_1 y_1
x_2 y_2
..
x_N y_N
Query_1
Query_2
..
Query_Q

このとき,$j(1 \le j \le Q)$番目のクエリは以下で与えられます.

l_1 l_2 r_1 r_2

出力

合計$Q$行出力してください.

$j( 1\le j \le Q)$行目には,$j$番目のクエリの答えを出力してください.

最後に改行してください.

サンプル

4 3
1 2
1 3
2 4
2 3
1 2 3 4
1 1 2 2
1 1 2 4

3
1
2

・$1$つめのクエリにて区間の左端が$[1,2]$,右端が$[3,4]$に含まれる閉区間は$A$の$(2,3,4)$番目が該当します.

・$2$つめのクエリにて区間の左端が$[1,1]$,右端が$[2,2]$に含まれる閉区間は$A$の$(1)$番目が該当します.

・$3$つめのクエリにて区間の左端が$[1,1]$,右端が$[2,4]$に含まれる閉区間は$A$の$(1,2)$番目が該当します.

5 9
3 4
5 5
2 4
2 5
1 4
2 4 5 5
3 4 5 5
1 4 5 5
3 3 4 5
1 3 4 5
1 2 3 5
1 1 4 5
4 4 5 5
3 4 5 5

1
0
1
1
4
3
1
0
0