Задача №114711. ТВ
После тяжёлого рабочего дня Алексей решил расслабиться за просмотром телевизора. Всего есть \(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\).
Рассмотрим тест из условия.
Если Алексей начнёт просмотр с первого телеканала в момент времени \(2\), то он будет смотреть на нём интересную передачу в течение одной минуты до момента времени \(3\), затем переключится на второй канал, на котором будет смотреть интересную передачу в течение одной минуты до момента времени \(4\). В момент времени \(4\) Алексей переключится на третий канал, по которому в этот момент не идёт интересная передача, поэтому в этот момент он закончит просмотр телевизора.
Во втором варианте просмотра, в момент времени \(5\) интересная передача не идёт ни по одному из каналов, поэтому Алексей сразу завершит просмотр.
В третьем варианте просмотра Алексей начнёт просмотр с первого канала в момент времени \(7\), так что он переключится сразу на второй, а потом и сразу на третий канал, после чего будет смотреть на нём интересную передачу в течение трёх минут до момента времени \(10\), после чего завершит просмотр телевизора.
3 1 3 2 4 7 10 4 1 2 2 5 1 7 3 10
2 0 3 0