E. Шинэ жилийн даалуу

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

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

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

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

Шинэ жилээ тэмдэглэж буй олон олон хүмүүс даалуу нурааж буй видео бичлэг постложээ. Энд тэдгээрийн жагсаалт нь байна:

https://www.youtube.com/results?search_query=New+Years+Dominos

Хоёр хэмжээст ертөнцөд амьдардаг Codeforces-н хэрэглэгч "ainta" мөн бичлэг постлох гэж байгаа аж.

Хоёр хэмжээст тэгш өнцөгт координатын хавтгай дээр $n$ ширхэг даалуу байрлажээ. $i$ дүгээр ($1 ≤ i ≤ n$) даалуу нь $y$ тэнхлэгтэй параллель $l_{i}$ урттай хэрчмээр илэрхийлэгднэ. Даалуу бүрийн суурь $x$ тэнхлэг дээр байрлана. $i$ дугаарын даалууны $x$ тэнхлэгийн координатыг $p_{i}$ гэж тэмдэглэе. Даалуунууд дарааллаараа буюу $p_{1} < p_{2} < ... < p_{n - 1} < p_{n}$ байхаар байрлана.

Хэрэглэгч "ainta" даалуу нурааж буй бичлэг хийхийг хүсчээ. Даалуунуудыг нураахын тулд тэрээр нэг даалууг баруун тийш түлхэнэ. Тэгээд даалуу $x$ тэнхлэгт бүхлээрээ хүртлээ тойрог замаар унана.

Хэрэв $s$ дугаарын даалуу унах үедээ $t$ дугаарын даалууд хүрвэл $t$ дугаарын даалуу мөн адилаар баруун тийш унаж эхлэнэ. $s$ ба $t$ дүгээр далууг илэрхийлэх хэрчмүүд огтлолцсон тохиолдолд $s$ дүгээр даалуу $t$ дүгээр даалуунд хүрсэн гэж үзнэ.

Дээрх зургийг харна уу. Хэрэв тэрээр хамгийн зүүн талын даалууг баруун тийш түлхвэл унах явцдаа $A$, $B$, $C$ даалуунд хүрнэ. Харин хамгийн зүүн талын даалуу $D$ даалуунд хүрэхгүй боловч эцэстээ $C$ даалуу түүнийг түлхэх юм.

Дээрх зураг нь унаж буй даалуунуудын жишээ юм. Улаан тойргоор даалуунууд нэгэндээ хүрэх цэгийг тэмдэглэв.

Хэрэглэгч "ainta"-д видео постлох $q$ төлөвлөгөө байгаа. $j$ дэх төлөвлөгөө нь $x_{j}$ дугаарын даалууг түлхэн хамгийн сүүлд $y_{j}$ дугаарын даалууг унагах юм. Гэвч зарим төлөвлөгөөнүүд санаснаар болохгүй тул зарим даалуугаа өндөрсгөхөөр шийджээ. Даалууны өндрийг $1$-ээр ихэсгэхэд нэг доллар зарцуулдаг.

Хэрэглэгч "ainta" төлөвлөгөө бүртээ түүнийг хэрэгжүүлэхийн тулд хамгийн багадаа хэдэн доллар зарцуулах шаардлагатайг мэдэхийг хүсчээ. Төлөвлөгөөнүүд хоорондоо хамааралгүй. Өөрөөр хэлбэл хэрэв ямар нэгэн төлөвлөгөөнд даалууны өндөр нэмэгдсэн бол бусад төлөвлөгөөнүүддээ нөлөөлөхгүй. $x_{j}$ болон $y_{j}$ дугаарын даалуунуудаас бусад унах даалуунууд чухал биш, хамгийн анх $x_{j}$ дугаарын даалуу түлхэгдэж унана.

Оролт

Эхний мөрөнд даалууны тоо болох $n$ ($2 ≤ n ≤ 2 × 10^{5}$) байна.

Дараагийн $n$ мөрөнд даалуу бүрийг тодорхойлно. $i$ ($1 ≤ i ≤ n$) дэх мөрөнд $i$ дэх даалууны $x$ координат ба өндрийг нь илэрхийлсэн $p_{i}$, $l_{i}$ ($1 ≤ p_{i}, l_{i} ≤ 10^{9}$) бүхэл тоонууд зайгаар тусгаарлагдан байна. $p_{1} < p_{2} < ... < p_{n - 1} < p_{n}$ байхаар өгөгдөнө.

Дараагийн мөрөнд төлөвлөгөөний тоо болох $q$ ($1 ≤ q ≤ 2 × 10^{5}$) өгөгдөнө.

Дараагийн $q$ мөрөнд төлөвлөгөө бүрийг тодорхойлно. $j$ ($1 ≤ j ≤ q$) дэх мөрөнд $x_{j}$, $y_{j}$ ($1 ≤ x_{j} < y_{j} ≤ n$) бүхэл тоонууд байна. $j$ дүгээр төлөвлөгөөнд $x_{j}$ дугаарын даалууг түлхэн $y_{j}$ дугаарын даалууг унатал видеог үргэлжлүүлэх юм.

Гаралт

Төлөвлөгөө бүрийг хэрэгжүүлэхэд хэрэгтэй хамгийн бага зардлыг хэвлэ. Зардал хэрэггүй бол "0" гэж хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
6
1 5
3 3
4 4
9 2
10 1
12 1
4
1 2
2 4
2 5
2 6
Гаралт
0
1
1
2

Тэмдэглэл

Жишээг авч үзье. Даалуунууд зураг дээр үзүүлсэн шиг байрлана.

$4$ дүгээр төлөвлөгөөг авч үзье. $2$ дугаар даалууг түлхэн $6$ дугаар даалууг унагахын тулд $3$ дугаар даалууны ($x$ координат нь $4$) өндөр $1$-ээр нэмэгдэх, $5$ дугаар даалууны ($x$ координат нь $9$) өндөр $1$-ээр нэмэгдэх шаардлагатай. (Өөр нэгэн хувилбар нь $5$ дугаар даалууны оронд $4$ дүгээр даалууны өндрийг $1$-ээр нэмэгдүүлж болно.) Энэ үед даалуунууд зурагт үзүүлсэн шиг унана. Хэрээс бүр даалуунууд нэгэндээ хүрэх цэгийг харуулж байна.

Сэтгэгдлүүдийг ачааллаж байна...