B. Нью-Йоркийн зочид буудлууд

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

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

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

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

Нью-Йорк хотыг $1$-ээс $N$ хүртэл дугаарлагдсан $N$ ширхэг босоо гудамж, $1$-ээс $M$ хүртэл дугаарлагдсан $M$ ширхэг хөндлөн гудамжаас бүрдсэн тэгш өнцөгт тор хэлбэртэй гэж бодъё. $C$ тооны найз зарим гудамжны уулзвар дээр байрлах $C$ тооны зочид буудлуудад байгаа. Тэд зарим гудамжны уулзвар дээр байрлах $H$ ресторануудын аль нэгэнд нэгнийхээ төрсөн өдрийг тэмдэглэх хэрэгтэй байлаа.

Тэгээд найзууд хамгийн холоос ирэх хүнийхээ хувьд ч гэсэн аль болох бага зам туулаасай гэж бодож байв. Баярт нь зориулж найзуудад хамгийн тохиромжтой ресторан сонгоход нь туслана уу.

Хөрш уулзваруудын хоорондох зайг нэг километр гэж үзнэ.

Оролт

Эхний мөрөнд хоёр бүхэл $N$, $M$ ($1 ≤ N, M ≤ 10^{9}$) тоонууд байна. Эдгээр нь хотын хэмжээнүүд юм. Дараагийн мөрөнд нэг бүхэл $C$ ($1 ≤ C ≤ 10^{5}$) тоо агуулагдана. Энэ нь найзуудын байрласан зочид буудлуудын тоо юм. Дараагийн $C$ мөрүүдэд зочид буудлуудын тодорхойлолт байх ба мөр бүрт координатууд болох $x$, $y$ ($1 ≤ x ≤ N$, $1 ≤ y ≤ M$) бүхэл тоонууд байна. Дараагийн мөрөнд ресторануудын тоо болох $H$ бүхэл тоо агуулагдана. Үүний дараагийн $H$ мөр бүрт ресторануудын тодорхойлолтуудыг дээрхтэй адилхан хэлбэрээр оруулна.

Нэг уулзвар дээр хэд хэдэн ресторанууд болон зочид буудлууд байрлаж болно.

Гаралт

Эхний мөрөнд тохиромжтой зайг хэвлэнэ. Дараагийн мөрөнд энэ тохиромжтой зайд байгаа рестораны дугаарыг хэвлэнэ. Хэрвээ хэд хэдэн боломжууд байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.

Орчуулсан: Даариймаа

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

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