E. Инна ба хүүхдүүд

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

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

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

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

Инна, Дима, Сережа 3 нэг өрөөнд сууж байна. Өрөө нэлээд хүйтэн байсан учраас Сережа "хүүхдүүд" гэдэг тоглоом тоглохоор санал болгож ээ.

Хүүхдүүд тоглоомын хөлөг нь төгсгөлгүй тэгш өнцөгт хэлбэртэй $n$ цэнхэр, $m$ улаан хүүхэдтэй хөлөг юм. Бүх хүүхдүүд хугацаанаас хамаарч өсдөг хэрчим байх юм. Хугацааны $t$ агшинд ($x,y$) координат дахь цэнхэр хүүхэд ($x-t$, $y+t$), ($x+t$, $y-t$) цэгт төгсгөлтэй хэрчим байх юм. Харин улаан хүүхэд ($x+t$, $y+t$), ($x-t$, $y-t$) координатд төгсгөлтэй шулуун болох юм. Хугацааны $t=0$ агшинд бүх хүүхдүүд цэг байна.

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

Танд бүх хүүхдүүдийн анхны координат өгөгдсөн бол бодлогын нөхцөлийг хангах хугацааны агшинг олоорой.

Оролт

Оролтын эхний мөрт $n$, $m$ ($1 ≤ n, m ≤ 2000$) тоо өгөгдөнө.

Дараагийн $n$ мөрөнд цэнхэр хүүхдүүдийн координат өгөгдөнө. $i$-р мөрөнд $i$-р хүүхдийн координат $x_i$, $y_i$ байна. Дараагийн $m$ мөрөнд улаан хүүхдүүдийн анхны координат адил хэлбэрээр өгөгдөнө.

Аль ч хүүхдийн координат $10^6$-с абсолют утгаараа хэтрэхгүй. Бүх хүүхэд ялгаатай координатаас эхэлнэ.

Гаралт

Бодлогын хариу болох ганц тоог хэвлэнэ.

Хэрвээ хэзээ ч тэгш өнцөгт үүсэхгүй бол "Poor Sereja!" гэж хашилтгүйгээр хэвлэ.

Орчуулсан: zoloogg

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

Оролт
2 2
2 2
5 5
3 7
5 1
Гаралт
3
Оролт
3 2
2 2
3 2
6 2
4 2
5 2
Гаралт
1
Сэтгэгдлүүдийг ачааллаж байна...