== include(page="template/taskheader" task_id="volei") ==

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).

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).

h2. Cerinta

h2. 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ă.

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ă.

h2. 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.

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 $x{~1~}$ $y{~1~}$ $x{~2~}$ $y{~2~}$, cu semnificaţia că elevii situaţi la poziţiile ({$x{~1~}$}, $y{~1~}$) şi ({$x{~2~}$}, $y{~2~}$) vor fi interschimbaţi.

h2. 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.

* $2$ ≤ $N$ ≤ $7$
* $1$ ≤ $D$ ≤ $30000$
* Coordonatele sunt numere întregi din intervalul [-$10000$, $10000$]
* 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).

* Distanţa dintre punctele ({x{~1~}}, {y{~1~}}) şi ({x{~2~}}, {y{~2~}}) este sqrt(({x{~1~}} - {x{~2~}})2 + ({y{~1~}} - {y{~2~}})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.

* 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.

h2. Exemplu

!problema/volei?fete.jpg!

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).

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$).

== include(page="template/taskfooter" task_id="volei") ==