Республиканская олимпиада по информатике 2008 год

Есеп H. Жұлдызды аспан

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайт

Денис Назаров, Уфа

Қыстың жарқын кешінде информатикадан Республикалық олимпиаданың қазылар алқасы Иван Васильевич асықпай үйіне бара жатты. Кей уақыттарда оның назары, өзінің сұлулығымен таң қалдырған бұлтсыз аспанға түсіп тұрды. Үйіне келгенде ол, жұлдыздар координаталар жазықтығында тек бүтін санды координаталарға ие нүктелерде орналасатындай, жұлдызды аспанның картасын құруды шешті. Ені мен ұзындығының координаталар жазықтығында бірлігі ретінде 1 жарық жылды алуды шешті. Иван Васильевич жұлдыздарды келесі ереже бойынша бөлді: жұлдыз қандай да бір жұлдыз шоғырына тиісі болады, егер бұл жұлдыз шоғырында кем дегенде осы жұлдызға дейінгі координаталар жазықтығында ара қашықтығы K жарық жылдан аспайтындай тағы бір жұлдыз табылса. Бір жұлдыз, екі жұлдыз шоғырына тиісті бола алмайды және кез-келген жұлдыз шоғырында кем дегенде бір жұлдыз бар. Бұдан кейін Иван Васильевич жұлдыздар шоғырының центрін келесі ережемен табуды шешті: егер жұлдызды картадан алып тастағанда, жұлдыздар шоғыры тағы да бірнеше жұлдыздар шоғырына бөлінетін болса, ол жұлдыздар шоғырының центрі болып есептеледі. Бір жұлдыздар шоғырында бірнеше центр болуы мүмкін. Екі немесе одан да аз жұлдыздардан құралған жұлдыздар шоғырында, анықтама бойынша центірі болмайды. Иван Васильевичке барлық жұлдыздар шоғырларының центрлерін табуға көмектесіңіз.

Формат входного файла

Кіріс файлда барлық жұлдыздардың координаталары жазылған (xi,yi). Жұлдыздар координаталарының жұптары әр түрлі. Жұлдыздардың жалпы саны 3000-нан аз, бірақ 1-ден көп. Жұлдыздардың координаталарының абсолют шамасы 214 -нен аз болатын бүтін сандар. Соңғы жолда $10^9$-нен кіші теріс емес $K$ бүтін саны жазылған.

Формат выходного файла

Сіздің программаңыз шығыс файлға екі бүтін сан шығаруы тиіс. Бірі – жұлдыздар шоғырының жалпы саны, екіншісі – олардың жұлдыздар картасындағы центрлерінің жалпы саны.

Пример:

Вход

4
0 0
1 1
0 1
1 0

Ответ

3 4 1 1