Alice Loves Segment

(難易度目安 : 点)

自然数が与えられます.

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

としたとき

が成り立っています.

区間が好きな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

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

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

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

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

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

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

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

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