Alice Loves Segment

2 secs 1024 MB
hide

問題文


(難易度目安 : 点)

自然数が与えられます.

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

としたとき

が成り立っています.

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


を満たすつの自然数が与えられる.

このとき以下の条件を満足する自然数の個数を答えよ.

としたときかつ


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

制約


・入力は全て整数

とした時

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

入力


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

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

このとき,番目のクエリは以下で与えられます.

l_1 l_2 r_1 r_2

出力


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

行目には,番目のクエリの答えを出力してください.

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

サンプル


入力1
4 3
1 2
1 3
2 4
2 3
1 2 3 4
1 1 2 2
1 1 2 4
出力1
3
1
2

つめのクエリにて区間の左端が,右端がに含まれる閉区間は番目が該当します.

つめのクエリにて区間の左端が,右端がに含まれる閉区間は番目が該当します.

つめのクエリにて区間の左端が,右端がに含まれる閉区間は番目が該当します.

入力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
出力2
1
0
1
1
4
3
1
0
0

Submit


Go (1.14)