D. Цэргүүд

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

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

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

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

Берландад дахин түнэр харанхуй нүүрлэлээ. Хорон муу санааны эзэн Ван де Март вант улсыг бүхэлд нь байлдан эзлэх гэж байна. Берландын хаан Валеригийн дуудсан дайны зөвлөл $n$ цэрэгтэй ирсэн. Урт хугацааны зөвлөгөөний дараа вант улсад удирдлагын яг $n$ цэг байгаа (хэрвээ эдгээр цэгүүдийн нэг нь дайсанд эзлэгдвэл дайныг алдана) гэдэг нь тодорхой болсон ба цэрэг бүр нэг цэгийг эзлэнэ.

Берланд $m$ хамгаалалтын хаалттай $m + 1$ бүсд хуваагдсан ба нэг бүсээс нөгөө бүсд нэвтрэх ганц арга нь хаалтан дээгүүр авирах юм. Хаалт бүр хавтгай дээрх тойрог байна, ямар ч хоёр хаалт ижил цэггүй ба ямар ч удирдлагын цэг хаалт дээр байхгүй. Танд $k$ ширхэг $a_{i}$, $b_{i}$ хос тоонууд өгөгдсөн. Хос бүрийн хувьд та: цэрэг $a_{i}$ индекстэй удирдлагын цэгээс $b_{i}$ (Ван де Март эхлээд $b_{i}$ удирдлагын цэгрүү дайрсан үед) удирдлагын цэгт хүрэхийн тулд хэдэн хаалт давахыг олох ёстой. Цэрэг бүр морь унасан (хаалтан дээгүүр морь давах маш хэцүү) бол та хос бүрийн хувьд давах хаалтын хамгийн бага хэмжээг олно.

Оролт

Оролтын эхний мөрөнд гурван бүхэл тоон утга $n$, $m$, $k$ ($1 ≤ n, m ≤ 1000$, $0 ≤ k ≤ 100000$) байна. Дараагийн $n$ мөр бүрт хоёр бүхэл тоон утга $Kx_{i}$, $Ky_{i}$ ($ - 10^{9} ≤ Kx_{i}, Ky_{i} ≤ 10^{9}$) байх ба $i$-р удирдлагын цэгийн координатууд байна. Удирдлагын цэгүүд давхцаж болно.

Дараагийн $m$ мөр бүрт $i$-р хаалтыг гурван бүхэл тоон утга $r_{i}$, $Cx_{i}$, $Cy_{i}$ ($1 ≤ r_{i} ≤ 10^{9}$, $ - 10^{9} ≤ Cx_{i}, Cy_{i} ≤ 10^{9}$)-р тодорхойлно. Эдгээр нь радиус болон харгалзах хаалтыг байрлуулсан тойргийн төв байна.

Тэгээд $k$ ширхэг хос бүхэл тоо $a_{i}$, $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$) нь тус бүр нэг мөрөнд байх ба таны хариулах ёстой хүсэлтүүд юм. $a_{i}$ ба $b_{i}$ нь давхцаж болно.

Гаралт

Яг $k$ мөр хэвлэх ба нэг мөрөнд харгалзах хүсэлтийн хариу болох нэг бүхэл тоо байна.

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

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

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