Рассмотрим отрезок координатной прямой от \(1\) до \(n\). На этом отрезке стоят \(k\) смотровых башен.
У каждой башни есть два параметра — координата \(x_i\) и высота \(h_i\). Все координаты башен различны. С башни \(i\) можно увидеть точку \(j\), если \(|x_i - j| \le h_i\) (где \(|a|\) — это абсолютное значение \(a\)).
За одну монету можно увеличить высоту любой башни на \(1\). Увеличивать высоту каждой башни можно произвольное число раз (в том числе и ноль раз).
Надо обработать \(q\) независимых запросов. В \(i\)-м запросе задаются две различных точки \(l\) и \(r\). Надо посчитать минимально необходимое количество монет, чтобы можно было увидеть обе эти точки (с одной башни или с разных башен).
Выходные данные
На каждый запрос выведите одно целое число — минимально необходимое количество монет, чтобы можно было увидеть обе точки (с одной башни или с разных башен).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
20 3
2 15 10
6 2 0
3
1 20
10 11
3 4
|
3 1 0
|
|
2
|
10 2
2 9
1 2
3
4 5
5 6
1 10
|
2 2 0
|