Hợp nhất đoạn

Cho \(n\) đoạn trên trục số, mỗi đoạn được biểu thị bởi cặp số nguyên dương \([l, r]\) trong đó \(l \le r\). Các đoạn này đôi một không có điểm chung hoặc chỉ có điểm chung ở đầu mút. Bạn được cho \(q\) truy vấn, mỗi truy vấn gồm hai số nguyên \((x, y)\) trong đó \(1 \le x \le y \le n\). Với mỗi truy vấn, bạn phải tìm số nguyên không âm \(k\) nhỏ nhất sao cho tồn tại cách nới rộng mỗi đoạn từ đoạn thứ \(x\) đến đoạn thứ \(y\) ra không quá \(k\) đơn vị để với mọi \(x \le i < y\) đoạn thứ \(i\) có giao điểm với đoạn thứ \(i+1\). Lưu ý với mỗi đoạn bạn chỉ được nới rộng sang trái và sang phải một số nguyên đơn vị mà thôi.

Ví dụ, khi \(n = 3\) và có 3 đoạn là \((1, 2), (4, 7), (12, 17)\):

• Nếu truy vấn \(x = 1\) và \(y = 2\) thì \(k\) nhỏ nhất bằng 1, khi đó ta có thể nới đoạn \((1,2)\) sang phải 1 đơn vị để được đoạn \((1,3)\) và nới đoạn \((4,7)\) sang trái 1 đơn vị để được đoạn \((3,7)\), lúc ấy hai đoạn \((1,3)\) và \((3,7)\) giao nhau.

• Nếu truy vấn \(x = 2\) và \(y = 3\) thì \(k\) nhỏ nhất bằng 3, khi đó ta có thể nới đoạn \((4,7)\) sang phải 3 đơn vị để được đoạn \((4,10)\) và nới đoạn \((12,17)\) sang trái 2 đơn vị để được đoạn \((10,17)\), lúc ấy hai đoạn \((4,10)\) và \((10,17)\) giao nhau.

• Nếu truy vấn \(x = 1\) và \(y = 3\) thì \(k\) nhỏ nhất bằng 3, khi đó ta có thể nới đoạn \((1,2)\) sang phải 1 đơn vị để được đoạn \((1,3)\), nới đoạn \((4,7)\) sang trái 1 đơn vị và sang phải 2 đơn vị để được đoạn \((3,9)\), đồng thời nới đoạn \((12,17)\) sang trái 3 đơn vị để được đoạn \((9,17)\), lúc ấy ba đoạn \((1,3)\), \((3,9)\), \((9,17)\) lần lượt giao nhau.

Input

• Dòng đầu là hai số nguyên \(n\) và \(q\) \((1 \le n \le 5000, 1 \le q \le 10^6)\).
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo mô tả đoạn thứ \(i\) gồm hai đầu mút \(l_i, r_i\) \((1 \le l_i < r_i \le 10^9)\). Lưu ý \(r_i \le l_{i+1}\) với mọi \(1 \le i < n\).
• Mỗi dòng trong số \(q\) dòng tiếp theo mô tả một truy vấn gồm hai số nguyên \(x, y\) \((1 \le x \le y \le n)\).

Output

• In ra \(q\) dòng, mỗi dòng gồm một số nguyên là số \(k\) nhỏ nhất tìm được cho truy vấn tương ứng.

Example

10 7
4 5
17 18
21 23
25 26
29 31
45 51
61 65
76 77
79 81
85 88
3 6
3 5
6 9
1 1
1 10
7 8
1 3

7
2
7
0
9
6
6

Scoring

\begintabular|c|c|l|
\hline
Subtask & Số điểm & Ràng buộc

\hline
1 & 15 & \(1 \le n, q \le 2000\), \(l_{i+1} \le r_i + 20\) với mọi \(i\)

\hline
2 & 25 & \(1 \le n, q \le 2000\)

\hline
3 & 60 & Không có ràng buộc gì thêm

\hline
\endtabular