Drum Luminat

Time limit: 0.2s Memory limit: 256MB Input: Output:

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 NN linii și MM coloane. Celula de pe linia ii și coloana jj are luminozitatea L[i][j]L[i][j]. Școala Anei se află în celula de la coordonatele (xs,ys)(x_s, y_s), iar casa ei se află în celula de la coordonatele (xf,yf)(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 55 decat prin o celulă cu luminozitate 00 si una cu 1010, ea definește luminozitatea unui drum ca media geometrică a luminozităților celulelor prin care trece.

Formal, fie un drum (x1,y1),,(xi,yi),,(xk,yk)(x_1, y_1), \ldots, (x_i, y_i), \ldots, (x_k, y_k) unde fiecare două pătrate sunt adiacente (xixi1+yiyi1=1|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1 pentru orice 1<ik1 < i \leq k). Luminozitatea lui este definită ca: (L[x1][y1]L[x2][y2]L[xk][yk])1/k(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 TT --- numarul de scenarii diferite.

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

  • prima linie va conține două numere întregi NN și MM --- numărul de linii, respectiv coloane;
  • pe a doua linie xsx_s, ysy_s, xfx_f, yfy_f --- coordonatele școlii(start) respectiv ale casei Anei;
  • fiecare din urmatoarele NN linii va conține MM numere întregi. Valoarea a jj-a de pe al ii-lea rănd, reprezentând luminozitatea celulei de la coordonatele (i,j)(i, j) --- L[i][j]L[i][j].

Date de ieșire

Se vor afișa TT 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

  • 1T100 0001 \leq T \leq 100\ 000;
  • 1N,M200 0001 \leq N, M \leq 200\ 000;
  • Suma NMN \cdot M pentru toate scenariile nu depășeste 200 000200\ 000;
  • 0L[i][j]1090 \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 10610^{-6};
  • 1xs,xfN1 \leq x_s, x_f \leq N;
  • 1ys,yfM1 \leq y_s, y_f \leq M;
  • Se garantează că (xs,ys)(xf,yf)(x_s, y_s) \neq (x_f, y_f).

Subtask-uri

# Punctaj Restricții
0 0 Exemplul
1 10 NM10N \cdot M \leq 10
2 20 N=1N = 1
3 30 1L[i][j]1 \leq L[i][j]
4 40 Fără restricții suplimentare

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

Log in or sign up to be able to send submissions!