ストーリー

20XX 年、パ研は技術室奥を捨て、海賊となり大海原に漕ぎ出した...

問題文

1 から N までの番号が振られた N 人の海賊が、1 から 10^{12} までの番号が振られた 10^{12} 個のお宝を山分けします。それぞれの海賊には分配されるお宝へのこだわりがあり、海賊 i は番号が L_i 以上 R_i 以下であるようなお宝のみを欲しがってその他のお宝は受け取りません。ここで海賊たちの間には「番号が大きい海賊はそれよりも番号が小さい海賊のお零れをもらうべきだ」という暗黙のことわりがあるため、すべての i,j\ (1 \leq i \lt j \leq N) について L_j \leq L_i かつ R_i \leq R_j が満たされます。

海賊たちはこの数日、様々な山分けの仕方について考えを巡らせています。そこで、以下の Q 個のクエリを順に処理してください。

• 海賊 l,l+1,\ldots,r でお宝を山分けするとき、それぞれがもらうお宝の個数の最小値は最大でいくらになるか。

制約

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq 10^{12}\ (1 \leq i \leq N)
• すべての i,j\ (1 \leq i \lt j \leq N) について、L_j \leq L_i かつ R_i \leq R_j が満たされる
• 各クエリにおいて、1 \leq l \leq r \leq N が満たされる
• 入力は全て整数

Extra ケース

下記の制約を満たすデータセット（上記の制約を満たす 800 点分のテストケースを含む）に正解した場合、追加で 1 点が与えられる。ただし、このデータセットにおいては低速な言語による AC が可能であることは保証されない。

• 2 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 5 \times 10^5

入力例 1

2
2 4
1 5
2
1 2
2 2

出力例 1

2
5

1 つ目のクエリにおいては、例えば以下のような山分けの仕方が考えられます。

• 海賊 1 にお宝 2,3 を、海賊 2 にお宝 4,5 を割り当てる。

2 つ目のクエリにおいては、海賊 2 にお宝 1,2,3,4,5 の全てを割り当てればよいです。

入力例 2

10
545730128881 685343573126
495640031759 777974687460
441446188770 793309056685
376909511228 836745593749
371724504348 838698721858
232388555737 839645478663
171431376831 859733468976
64650919635 891249391583
54537347654 900209259449
7975806821 908972571709
10
9 9
2 3
1 6
3 9
2 10
1 2
3 4
5 6
2 9
7 8

出力例 2

845671911796
175931433958
93394843502
120810273113
100110751654
139613444246
229918041261
303628461463
105708988974
413299235974

原案: penguinman