F. Шинэ жилийн цасан ширхэг

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

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

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

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

Gerald-н хувьд, Шинэ жилийн өмнөх өдөр Constantine нэгэн үзэсгэлэнтэй бүсгүйд ер бусын бэлэг бэлджээ. Энэхүү бэлэг нь шинэ жилийн шидэт цасан ширхэг бөгөөд ямарч хүслийг биелүүлдэг гэнэ.

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

Constantine-г сая сая цасан ширхгүүдийг сонгож байх зуураа амьсгаагаа түгжиж байсан. Үзэсгэлэнт бүсгүйг орж ирэхэд түүний цасан ширхэгийн зарим талст нь хайлж, алга болсон байв. Constantine $k$-аас ихгүй талст алга болсыг мэдэж байгаа. Яагаад гэвэл тэр цасан ширхгийг болгоомжтой хийсэн учраас. Одоо тэр үзэсгэлэнт бүсгүйд нанотехнологийн хүчийг үзүүлэхэд бэлэн болсон бөгөөд цасан ширхгийн тэгш хэмийн төвийг сэргээхээр болов.

Танд үлдсэн цасан ширхгүүдийн талстуудын координатуудыг наномертээр өгөгдөв. Таны даалгавар бол байж болох бүх тэгш хэмийн төвийн байршлийг тогтоох юм.

Оролт

Эхний мөрөнд хоёр бүхэл тоо болох $n$ and $k$ ($1 ≤ n ≤ 200 000$, $0 ≤ k ≤ 10$) - харгалзан үлдсэн цасан ширхгүүдийн тоо, хамгийн ихдээ хайлсан байх боломжтой талстуудын тоо. Дараагийн $n$ мөр үлдсэн цасан ширхгүүдийн координатууд дараах хэлбэрээр өгөгдөнө "x_i y_i". Бүхэл координатуудын утга абсолютаараа $5*10^{8}$-аас бага бөгөөд бүх координатууд ялгаатай байна.

Гаралт

Эхний мөрөнд $c$ тоо - байж болох тэгш хэмийн тоо. Дараагийн $c$ мөр тэгш хэмүүдийг мэдээллэх ёстой. Бүх тэгш хэмийн төвийн "$x$ $y$" координатууд байх бөгөөд таслалаас хойш 6 оронтой хэвлэ. Тэгш хэмийн цэгүүдийг ямарч дарааллаар хэвлэж болно. Хэвлэсэн бүх цэг өөр байх ёстой. Хэрэв хязгааргүй олон тэгш хэмийн төвтэй бол зөвхөн "-1" гэж хэвлэнэ үү.

Орчуулсан: Б.Алтангэрэл

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

Оролт
4 0
0 0
0 1
1 0
1 1
Гаралт
1
0.5 0.5
Оролт
4 2
0 0
0 1
1 0
1 1
Гаралт
5
0.0 0.5
0.5 0.0
0.5 0.5
0.5 1.0
1.0 0.5
Оролт
4 4
0 0
0 1
1 0
1 1
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...