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

* $1 ≤ N ≤ 10.000$
* $1 ≤ A, B ≤ N$

* $1 ≤ P ≤ 1.000.000$

* $1 ≤ P ≤ 1.000.000.000$

* $1 ≤ T ≤ 100.000$
* Rezultatele se vor afisa cu o precizie de $10^-6^$