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

Poveste şi cerinţă...

Domnul B. este un artist modern. Ultima sa mare creatie este, intr-o forma extrem de stilizata, permutarea identica de lungime $N$ (adica permutarea $1, 2, 3 ... N$).
 
Domnul C. este malitios. Ultimul sau mare plan este de a distruge ultima mare creatie a Domnului B., facand interschimbari aleatoare ale unor numere din permutare. Mai exact, la un pas, Domnul C. isi va alege cu probabilitate egala doua pozitii, $i$ si $j$ si va interschimba continuturile celor doua pozitii din permutare.
Domnul C. are in cap $T$ intrebari, iar in functie de raspunsurile voastre isi va alege cea mai malitioasa strategie pentru a distruge creatia Domnului B. O intrebare are forma urmatoare: $P A B$, cu semnificatia "Care este probabilitatea ca dupa $P$ pasi, numarul $A$ sa ajunga pe pozitia $B$?"
 
Ajutati-l pe Domnul C., raspunzand corect la fiecare dintre cele $T$ intrebari.

h2. Date de intrare

Fişierul de intrare $swaps.in$ ...

Fişierul de intrare $swaps.in$ va contine pe prima linie numerele naturale $N$ si $T$. Urmatoarele $T$ linii vor contine triplete de forma $P A B$, cu semnificatia din enunt.

h2. Date de ieşire

În fişierul de ieşire $swaps.out$ ...

În fişierul de ieşire $swaps.out$ se vor afla raspunsurile la cele $T$ intrebari, pe linii diferite.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 10.000$
* $1 ≤ A, B ≤ N$
* $1 ≤ P ≤ 1.000.000$
* Rezultatele se vor afisa cu o precizie de $10^-6^$

h2. Exemplu