https://codeforces.com/contest/1635/problem/F

x 遞增，考慮維護 w。

1.考慮單點匹配，由 w? 大的匹配 w? 小的。

顯然，若 i < j < k ，且 w_j<=w_k, 那么最優(yōu)的匹配一定不是 (i,k)。

因為(i,k)的值大于 (i,j)。 所以 (j,k)是一個可能選項。

故維護每個點 i，只需要考慮記錄i左右邊第一個(如果存在的話)滿足? w_j<=w_i? 的 j，分別記作 L_i? 和? R_i

2.區(qū)間上最優(yōu)解。

自然會有疑問：對于一個單點 i，i左右邊第一個滿足 權(quán)重小于 w_i? 的點為 L_i? 與 R_i，

? 但是 i? 本身卻可以和區(qū)間內(nèi)其他節(jié)點構(gòu)成本區(qū)間的最優(yōu)解呢？

對于詢問區(qū)間? [Lq,Rq]，如果有帶權(quán)距離最小的點對 (a,b) ∣ w_a<=w_b ，滿足 a < L_b < b.

由于 w_Lb<=w_b, 根據(jù)1的討論，(a, L_b)的值小于(a,b)的值， (a,b)一定不是最優(yōu)解。矛盾。

對于詢問區(qū)間? [Lq,Rq]，如果有帶權(quán)距離最小的點對 (a,b) ∣ w_a>w_b ，滿足 a < R_a < b.

由于 w_Ra<=w_a, 類似根據(jù)1的討論， (R_a, b)的值小于(a,b)的值，(a,b)一定不是最優(yōu)解。矛盾。

綜上，我們得到結(jié)論：區(qū)間內(nèi)的帶權(quán)距離最小的點對一定屬于那 最多2n 個點對之中。

即答案匹配只能是區(qū)間中所有? (L_i,i)和? (i,R_i) 中最小值。

input

5 5

-2 2

0 10

1 1

9 7

12 2

1 3

2 3

1 5

3 5

2 4