Поезд пассаЖирный
Андрей разрабатывает системы для продажи билетов на поезда. Он собирается протестировать её на маршруте скоростного поезда «Intercity Express», которые соединяет два крупных города и имеет n - 2 промежуточные остановки, т.е. всего существует n остановок, пронумерованных натуральными числами от 1 до n.
«Intercity Express» — очень современный и комофортабельный паровоз, в нем есть целых s мест, заботливо пронумерованных от 1 до s. В тестовом режиме система имеет доступ к базе данных, в которой содержится описание проданных билетов в направлении от станции 1 к станции n, и система должна уметь отвечать на запрос, возможно ли купить билет от станции a до станции b и, если это возможно, сообщить номер минимального свободного места, которое свободно на протяжении всего пути от a до b. Обратите внимание, в тестовом режиме система умеет лишь отвечать на запросы, при этом продажа билетов после запроса не осуществляется, и общая ситуация не меняется.
Помогите Андрею: напишите программу, которая будет отвечать на подобные запросы.
В первой строке входных данных содержатся три числа n, s и m — количество станций, количество мест в поезде и количество уже проданных билетов, соответственно (2 ≤ n ≤ 109, 1 ≤ s ≤ 100 000, 0 ≤ m ≤ 100 000).
Следующие m строк описывают билеты, каждый билет описывается тремя числами ci, ai, и bi — номер места, которое будет занято этим пассажиром, станция отправления и станция прибытия (1 ≤ ci ≤ s, 1 ≤ ai < bi ≤ n).
В следующей строке содержится число q — количество запросов (1 ≤ q ≤ 100 000). В процессе работы вы должны поддерживать число p. Изначально p = 0. Следующие 2q чисел описывают запросы. Каждый запрос задается двумя числами: xi и yi (xi < yi). Для получения номеров городов a и b, для которых необходимо ответить на вопрос задачи, необходимо использовать следующие сложнейшие формулы: a = xi + p, b = yi + p. Ответом на запрос является целое число 0, если свободных мест нет на отрезке пути от a до b, или минимальный номер такого места в противном случае. Прсле ответа на запрос, присвойте числу p ответ на запрос.
Для каждого запроса выведите единственное число — ответ на него.
Решение, работающиее при \(s, m, q \le 1000\), будет набирать не менее 60 баллов. Тесты оцениваются независимо.
5 3 5 1 2 5 2 1 2 2 4 5 3 2 3 3 3 4 10 1 2 1 2 1 2 2 3 -2 0 2 4 1 3 1 4 2 5 1 5
1 2 2 3 0 2 0 0 0 0