D. Машины зогсоол

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Одоо үед хот дотор машиндаа зогсоол олж байрлуулна гэдэг улам л хэцүү болж байгаа билээ. Машины зогсоол байрлах $L$ метр урттай гудамжны нэгэн хэсгийг авч үзье. Жолооч нар нь өөрсдийн машиныг гудамжны баруун талд нь явган хүний замтай параллель байхаар байрлуулах юм(уг бодлогын зохиолчийн улсад машинууд нь баруун гарын дүрмээр явдаг!). Машинаа байрлуулж байхдаа жолооч болгон нь өөрийн машин нь чөлөөтэй хөдөлж байхаар өөртөө нэмэлт хоосон зай үлдээхийг хүсэх бөгөөд ийм учраас жолооч болгон нь өөрийн машин болон хойно байрлах машины хоорондох зай $b$ метрээс багагүй, өөрийн машин болон урд байрлах машины хоорондох зай $f$ метрээс багагүй байх машины зогсоолыг хайх ажээ (хэрэв ямар ч машин жолоочийн машины хойно байхгүй байвал тэрээр өөрийн машинаа машины зогсоолын захад байрлуулж болох бөгөөд хэрэв жолоочийн машины урд талд нь ямар ч машин байхгүй байвал мөн л адил зогсоолын захад машинаа байрлуулж болно). Бид явган хүний замын дагуу координатын тэнхлэгийг тодорхойлъё. Машин зогсоол нь 0 гэсэн цэгээс эхлэх бөгөөд $L$ гэсэн цэг дээр дуусах юм. Жолооч нар нь координатын өсөх чиглэлд машинаа жолоодох бөгөөд машинаа байрлуулж болох хамгийн эхэнд таарах зогсоолыг(өөрөөр хэлбэл боломжит хамгийн бага координаттай ) хайна. Хэрэв ийм байх ямар ч зогсоол байхгүй байвал жолооч өөртөө төгс тохирох зогсоолыг хайсаар цааш явах юм. Өөрөөр хэлбэл уг зогсоолд машинаа тавихгүй гэсэн үг. Зарим тохиолдолд хэсэг машин гудамжийг орхин явах бөгөөд машин тавьж болох хоосон зайнууд үүсэх ажээ. Хугацааны ямар нэгэн мөчид уг гудамжинд хөдөлж буй 2 машин байж болохгүй юм. Та гудамжинд орж ирэн машинаа зогсоолд тавьж буй жолооч нарын болон уг гудамжийг орхин явж буй жолооч нарын мэдээллийг ашиглан машин тус бүрд хоосон зогсоол олж өгөх үйл явцыг загварчлах программ зохионо уу.

Оролт

Оролтын эхний мөрөнд 3-н бүхэл тоо $L$, $b$ болон $f$ ($10 ≤ L ≤ 100000, 1 ≤ b, f ≤ 100$) өгөгдөнө. 2-дахь мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 100$) өгөгдөх ба энэ нь программ-д ирж буй хүсэлтийн тоог илэрхийлнэ. Хүсэлт болгон нь дан мөрөнд дүрслэгдэх бөгөөд 2 тоогоор өгөгдөх юм. Эхний тоо нь уг хүсэлтийн төрлийг илэрхийлнэ. Хэрэв тухайн хүсэлтийн төрөл нь $1$-тэй тэнцүү бол 2-дахь тоо нь гудамжинд орж ирэн машин зогсоол хайж буй машины уртыг(метрээр өгөгдөнө) илэрхийлэх юм. Харин тухайн хүсэлтийн төрөл нь $2$-той тэнцүү бол 2-дахь тоо нь $1$-р төрлийн нэгэн хүсэлтийн дугаарыг илэрхийлэх бөгөөд энэ нь уг дугаарын хүсэлт дээр машин зогсоолд ирж байсан машин нь машин зогсоолын газрыг орхин явж байгаа болохыг илэрхийлэх юм.

Мөн $2$-р төрлийн хүсэлт ирэх үед тухайн машин нь машин зогсоолд баттай зогсож байна. Машины уртууд нь $1$-ээс $1000$ хүртэлх бүхэл тоонууд байна.

Гаралт

$1$-р төрлийн асуулт болгоны хувьд хэрэв харгалзах машиныг уг гудамжинд байрлуулах боломжгүй байвал дан мөрөнд $-1$ гэж хэвлэнэ үү. Бусад тохиолдолд зогсоолд тавьсан машины хойд хэсгээс машин зогсоолын газрын эхлэл хэсэг хүртэлх зайтай тэнцүү байх ганц тоог дан мөрөнд хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
30 1 2
6
1 5
1 4
1 5
2 2
1 5
1 4
Гаралт
0
6
11
17
23
Оролт
30 1 1
6
1 5
1 4
1 5
2 2
1 5
1 4
Гаралт
0
6
11
17
6
Оролт
10 1 1
1
1 12
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...