Sim-4-2 | Drum Luminat

Cerință

A venit iarna și se întunecă mai devreme. După o zi de școală, Ana vrea să se întoarcă acasă. Putem reprezenta orașul în care trăiește Ana sub forma unei matrice cu $N$ linii și $M$ coloane. Celula de pe linia $i$ și coloana $j$ are luminozitatea $L[i][j]$. Școala Anei se află în celula de la coordonatele $(x_s, y_s)$, iar casa ei se află în celula de la coordonatele $(x_f, y_f)$.

Anei îi este frică de întuneric, și vrea să ia cel mai puternic luminat drum către casă. Cum ii se pare mult mai rezonabil să mearga prin două celule de luminozitate $5$ decat prin o celulă cu luminozitate $0$ si una cu $10$, ea definește luminozitatea unui drum ca media geometrică a luminozităților celulelor prin care trece.

Formal, fie un drum $(x_1, y_1), \ldots, (x_i, y_i), \ldots, (x_k, y_k)$ unde fiecare două pătrate sunt adiacente ($|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1$ pentru orice $1 < i \leq k$). Luminozitatea lui este definită ca: $(L[x_1][y_1] \cdot L[x_2][y_2] \cdot \ldots \cdot L[x_k][y_k])^{1 / k}$.

Un drum poate vizita de mai multe ori aceași celulă. Ajutați-o pe Ana să gasească drumul cu luminozitate maximă de la școală la casa ei.

Date de intrare

Pe prima linie se va afla un singur număr întreg $T$ --- numarul de scenarii diferite.

Fiecare scenariu va fi descris în modul următor:

• prima linie va conține două numere întregi $N$ și $M$ --- numărul de linii, respectiv coloane;
• pe a doua linie $x_s$, $y_s$, $x_f$, $y_f$ --- coordonatele școlii(start) respectiv ale casei Anei;
• fiecare din urmatoarele $N$ linii va conține $M$ numere întregi. Valoarea a $j$-a de pe al $i$-lea rănd, reprezentând luminozitatea celulei de la coordonatele $(i, j)$ --- $L[i][j]$.

Date de ieșire

Se vor afișa $T$ linii, pe fiecare linie câte un număr real pentru, reprezentând luminozitatea maximă a unui drum pentru fiecare scenariu.

Restricții și precizări

• $1 \leq T \leq 100\ 000$;
• $1 \leq N, M \leq 200\ 000$;
• Suma $N \cdot M$ pentru toate scenariile nu depășeste $200\ 000$;
• $0 \leq L[i][j] \leq 10^9$;
• Un răspuns este considerat corect dacă eroarea față de soluția corectă este mai mică decât $10^{-6}$;
• $1 \leq x_s, x_f \leq N$;
• $1 \leq y_s, y_f \leq M$;
• Se garantează că $(x_s, y_s) \neq (x_f, y_f)$.

Subtask-uri

Exemplu

stdin

2
3 3
1 1 3 3
3 2 0
2 0 2
0 2 3
3 3
2 1 3 3
1 1 1
3 2 2
3 3 3

stdout

0
3.000000000000