F. Мэлхийнүүд ба Шумуулууд

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

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

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

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

$Ox$ координатын тэнхлэг дээр сууж буй $n$ мэлхий байна. Мэлхий бүрийн хувьд $i$-р мэлхийн байрлал ба хэлний анхны урт болох хоёр утга$x_{i}, t_{i}$ мэдэгдэж байгаа (мэдээж бүх $x_{i}$ байрлалууд ялгаатай). $m$ шумуулууд нэг нэгээрээ координатын тэнхлэг дээр газардаж байна. Шумуул бүрийн хувьд $j$-р шумуулын буух байрлалын координат $p_{j}$ ба $i$-р шумуулын хэмжээ $b_{j}$ мэдэгдэж байна. Мэлхийнүүд болон шумуулууд координатын тэнхлэг дээр цэг хэлбэрээр дүрслэгдэнэ.

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

Хэрвээ тухайн нэг мөчид нэг шумуулыг хэд хэдэн мэлхий идэх боломжтой байвал хамгийн зүүн талынх нь иднэ (хамгийн бага $x_{i}$-тай нь). Шумуулыг идсэний дараа мэлхийн хэлний урт идсэн шумуулны хэмжээгээр нэмэгдэнэ. Үүний дараа мэлхий өөр бусад шумуулуудыг идэх боломжтой болох юм (энэ тохиолдолд мэлхий тэднийг идэх ёстой).

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

Шумуул бүр өмнө нь газардсан шумуулуудаас мэлхийнүүд идэж чадах бүх шумуулаа идсэний дараа координатын тэнхлэгрүү газардана. Шумуулууд координатын тэнхлэгт газардах дарааллаараа өгөгдөнө.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n, m$ ($1 ≤ n, m ≤ 2*10^{5}$) байх ба мэлхийнүүд болон шумуулуудын тоо байна.

Дараагийн $n$ мөр бүрт хоёр бүхэл тоон утга $x_{i}, t_{i}$ ($0 ≤ x_{i}, t_{i} ≤ 10^{9}$) байх ба $i$-р шумуулын байрлал болон хэлний анхны урт байна. Бүх $x_{i}$ ялгаатай байх нь тодорхой.

Дараагийн $m$ мөр бүрт хоёр бүхэл тоон утга $p_{j}, b_{j}$ ($0 ≤ p_{j}, b_{j} ≤ 10^{9}$) байх ба $j$-р шумуулын байрлал болон хэмжээ байна.

Гаралт

$n$ мөр хэвлэнэ. $i$-р мөрөнд хоёр бүхэл тоон утга $c_{i}, l_{i}$ байх ёстой ба $i$-р мэлхийн идсэн шумуулын тоо ба $i$-р мэлхийн хэлний урт байна.

Орчуулсан: Г.Мэндбаяр

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

Оролт
4 6
10 2
15 0
6 1
0 1
110 10
1 1
6 0
15 10
14 100
12 2
Гаралт
3 114
1 10
1 1
1 2
Оролт
1 2
10 2
20 2
12 1
Гаралт
1 3
Сэтгэгдлүүдийг ачааллаж байна...