Алыс болашақта адамзат отарлау үшін үлкен, жылы әрі жасыл желекті ғаламшар тауып, жаңа отарды қамтамасыз ету мақсатында көптеген электр станцияларын салып жатыр. Таңғажайып технология құрылысшыларға Ғаламның орасан зор энергиясын игеруге мүмкіндік береді. Алайда олар ескермеген бір кішкентай жайт бар: екі электр станциясын бір-біріне тым жақын салу тізбекті реакцияның туындау қаупін едәуір арттырады, ал ол өз кезегінде жойқын жарылысқа әкеп соғады. Әрине, бұған жол бермеу керек.

Бақытымызға орай, станцияларда қолдануға болатын жарық және қараңғы энергия деп аталатын, бір-бірімен әрекеттеспейтін екі түрлі энергия бар. Егер электр станцияларының бір бөлігі жарық энергиямен, ал бір бөлігі қараңғы энергиямен жұмыс істесе, бірдей станциялар арасындағы қашықтық бұрынғыдан үлкенірек болуы мүмкін, бұл бүкіл бастаманың қауіптілігін азайтады.

Тапсырма

$n$ станцияның орналасқан жерлері берілген (ғаламшар жеткілікті түрде үлкен болғандықтан, оларды жазықтықтағы нүктелер ретінде қарастыра аламыз). Бір типті екі станцияның арасындағы евклидтік қашықтық мүмкіндігінше ең үлкен болатындай етіп, әр станцияға жарық немесе қараңғы энергияны тағайындаңыз. Нақты сандарды шығармау үшін жауап ретінде осы ең үлкен қашықтықтың квадратын, сондай-ақ станциялардың «жарық» және «қараңғы» болып бөлінуін шығарыңыз.

Кіріс деректері

Кіріс деректерінің бірінші жолында бір бүтін сан $N$ ($3 \le N \le 100\,000$) — электр станцияларының саны берілген. Келесі $N$ жолдың $i$-шісінде екі бүтін сан $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) — $i$-ші станцияның координаттары берілген. Барлық нүктелер өзара әртүрлі.

Шығыс деректері

Шығыс деректерінің бірінші жолында қол жеткізуге болатын ең үлкен қашықтықтың квадратын білдіретін бір бүтін санды шығарыңыз. Екінші жолда жарық энергиямен жұмыс істейтін станциялар саны, ал үшінші жолда осы станциялардың бос орын арқылы бөлінген нөмірлерінің тізімі болуы тиіс. Төртінші және бесінші жолдар дәл осындай форматта қараңғы энергия станцияларын сипаттауы керек. Егер бірнеше дұрыс шешім болса, олардың кез келгенін шығарыңыз.

Ішкі есептер

Examples

Input 1

4
0 3
0 0
3 0
3 3

Output 1

18
2
1 3
2
2 4