410213: GYM103984 I ТВ

I. ТВограничение по времени на тест3 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

После тяжёлого рабочего дня Алексей решил расслабиться за просмотром телевизора. Всего есть $$$n$$$ телеканалов, на $$$i$$$-м телеканале показывают интересную для Алексея передачу в отрезок времени $$$[l_i, r_i]$$$.

Так как жизнь Алексея расписана по минутам, то он смотрит телевизор по определенному алгоритму. Пусть в текущий момент Алексей смотрит телеканал $$$x$$$ в момент времени $$$t$$$. Тогда:

• если на этом телеканале в момент времени $$$t$$$ идёт интересная передача, то Алексей досматривает ее до конца и переходит к следующему телеканалу под номером $$$x + 1$$$;
• если же в момент времени $$$t$$$ на телеканале $$$x$$$ нет интересной передачи, то Алексей моментально переходит к следующему телеканалу $$$x + 1$$$;
• если же канала $$$x+1$$$ не существует (при $$$x=n$$$), то Алексей заканчивает просмотр телевизора.

Алексей пока не определился, в какой момент и с какого телеканала начать просмотр. У него есть $$$m$$$ вариантов, $$$i$$$-й вариант предполагает начало просмотра телевизора с телеканала $$$x_i$$$ в момент времени $$$t_i$$$. Для каждого из вариантов определите время, которое Алексей проведет за просмотром интересных передач.

Входные данные

В первой строке содержится целое число $$$n$$$ ($$$1 \le n \le 300\,000$$$) — количество телеканалов.

Следующие $$$n$$$ строк содержат описания телеканалов: $$$i$$$-я строка содержит два числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i < r_i \le 10^9$$$) — отрезок времени, на протяжении которого на $$$i$$$-м телеканале идёт интересная передача.

В следующей строке задано целое число $$$m$$$ ($$$1 \le m \le 300\,000$$$) — количество вариантов просмотра.

Следующие $$$m$$$ строк содержат описания вариантов просмотра, в $$$i$$$-й строке содержатся два целых числа $$$x_i$$$ и $$$t_i$$$ ($$$1 \le x_i \le n; 1 \le t_i \le 10^9$$$) — номер телеканала и момент времени, соответственно.

Выходные данные

Для $$$i$$$-го варианта просмотра выведите одно целое число — суммарное время, которое Алексей будет смотреть интересные передачи, если начнет просмотр с телеканала $$$x_i$$$ в момент времени $$$t_i$$$.

ПримерВходные данные

3
1 3
2 4
7 10
4
1 2
2 5
1 7
3 10

Выходные данные

2
0
3
0

Примечание

Рассмотрим тест из условия.

Если Алексей начнёт просмотр с первого телеканала в момент времени $$$2$$$, то он будет смотреть на нём интересную передачу в течение одной минуты до момента времени $$$3$$$, затем переключится на второй канал, на котором будет смотреть интересную передачу в течение одной минуты до момента времени $$$4$$$. В момент времени $$$4$$$ Алексей переключится на третий канал, по которому в этот момент не идёт интересная передача, поэтому в этот момент он закончит просмотр телевизора.

Во втором варианте просмотра, в момент времени $$$5$$$ интересная передача не идёт ни по одному из каналов, поэтому Алексей сразу завершит просмотр.

В третьем варианте просмотра Алексей начнёт просмотр с первого канала в момент времени $$$7$$$, так что он переключится сразу на второй, а потом и сразу на третий канал, после чего будет смотреть на нём интересную передачу в течение трёх минут до момента времени $$$10$$$, после чего завершит просмотр телевизора.