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 $2 \cdot N$ 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 $2 \cdot N$ linii va conţine un triplet de forma $x \ y \ \text{tip}$, unde $x \ y$ sunt coordonatele iniţiale ale unui elev (abscisa, ordonata), iar $\text{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 şi precizări

• $2 \leq N \leq 7$
• $1 \leq D \leq 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.

Exemplu

volei.in

3
4
-2 4 B
-1 3 F
-1 -2 B
1 5 F
3 3 F
6 6 B

volei.out

2
-2 4 -1 3
-1 3 3 3

Explicaţie

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