La ora de sport elevii doresc să joace volei. Sunt exact N fete şi N băieţi şi se doreşte formarea a două echipe, o echipă formată numai din fete, iar cealaltă numai din băieţi. Iniţial, elevii au o poziţie fixată pe teren. Ei pot fi reprezentaţi ca 2N puncte de coordonate întregi în plan. Pentru a putea începe jocul, profesorul de sport trebuie să traseze un fileu (o dreaptă) între echipa băieţilor şi echipa fetelor, astfel încât cele două echipe să se afle de o parte şi de alta a fileului. Cum trasarea unui fileu între cele două echipe poate să nu fie posibilă conform aşezării iniţiale, trebuie să fie efectuate unele schimbări. Astfel, profesorul poate alege la un moment dat o singură fată şi un singur băiat, situaţi la distanţa maxim D şi să le interschimbe poziţiile (fata va trece în locul băiatului, iar băiatul în locul fetei).
Cerinţă
Să se determine numărul minim de mutări pe care trebuie să le efectueze profesorul de sport pentru a fi posibilă amplasarea unui fileu, precum şi mutările efectuate.
Date de intrare
Fişierul de intrare volei.in conţine pe prima linie N, numărul de fete, egal cu numărul de băieţi. A doua linie va conţine numărul natural nenul D, cu semnificaţia din enunţ. Fiecare dintre următoarele 2N linii va conţine un triplet de forma x y tip, unde x y sunt coordonatele iniţiale ale unui elev (abscisa, ordonata), iar tip este caracterul B dacă elevul corespunzător este băiat sau F dacă este fată.
Date de ieşire
Fişierul de ieşire volei.out va conţine pe prima linie un număr natural nrmin reprezentând numărul minim de mutări care trebuie să fie efectuate. Pe următoarele nrmin linii se vor afişa mutările efectuate, câte o mutare pe o linie, în ordinea efectuării lor. O mutare este descrisă sub forma x1 y1 x2 y2, cu semnificaţia că elevii situaţi la poziţiile (x1,y1) şi (x2,y2) vor fi interschimbaţi.
Restricţii
2 ≤ N ≤ 7
1 ≤ D ≤ 30 000
Coordonatele sunt numere întregi din intervalul [-10 000, 10 000].
Nu vor exista 3 poziţii coliniare.
Nu vor exista două persoane în aceeaşi poziţie.
Distanţa dintre punctele (x1,y1) şi (x2,y2) este sqrt((x1-x2)2+(y1-y2)2).
Dacă sunt mai multe soluţii posibile, afişaţi oricare dintre acestea.
Se va acorda 40% din punctajul pe test dacă numărul de mutări este corect, respectiv 100% din punctaj dacă atât numărul mutărilor, cât şi mutarile efectuate sunt corecte.
Pentru 50% dintre teste D mai mare decât maximul distanţelor între oricare două puncte.
Exemple
volei.in
volei.out
Explicaţii
3
4
-2 4 B
-1 3 F
-1 -2 B
1 5 F
3 3 F
6 6 B
2
-2 4 -1 3
-1 3 3 3
Se interschimbă băiatul de la poziţia (-2,4) cu fata de la poziţia (-1,3). Apoi se interschimbă băiatul de la poziţia (-1,3) cu fata de la poziţia (3,3).
