В наши дни становится все труднее удачно припарковать свой автомобиль в городе. Представим себе отрезок улицы длиной в L метров, вдоль которого разрешена парковка. Водители должны ставить свои автомобили строго параллельно тротуару с правой стороны улицы (помните, что в стране авторов задач движение правостороннее!). Каждый водитель при парковке хочет оставить себе некоторый запас для маневрирования, поэтому водитель ищет такое место, что расстояние до сзади стоящей машины будет не меньше b метров, а до впереди стоящей — не меньше f метров (если сзади машины нет, то автомобиль можно ставить у самого края отрезка для парковки; то же самое верно для случая, когда спереди не припарковано машин). Введем ось координат вдоль тротуара. Пусть зона для парковки начинается в точке 0 и заканчивается в точке L. Водители едут в направлении увеличения координаты и ищут самое раннее место (с наименьшей возможной координатой), где они могут припарковать машину. В случае, если такого места не находится, водитель едет дальше в поисках счастья. Иногда некоторые машины покидают улицу и освобождают место для парковки. Считая, что на улице никогда не находятся две двигающиеся машины одновременно, напишите программу, которая по информации о водителях, приезжающих на улицу в целях парковки и уезжающих с нее, моделирует процесс и определяет для каждого автомобиля место, занятое им в зоне парковки.
Выходные данные
Для каждого запроса типа 1 в отдельной строке выведите число -1, если соответствующему автомобилю не нашлось места на парковке вдоль улицы. В противном случае выведите целое число, равное расстоянию от задней части автомобиля в его припаркованном положении до начала зоны парковки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
30 1 2
6
1 5
1 4
1 5
2 2
1 5
1 4
|
0
6
11
17
23
|
|
2
|
30 1 1
6
1 5
1 4
1 5
2 2
1 5
1 4
|
0
6
11
17
6
|
|
3
|
10 1 1
1
1 12
|
-1
|