Căsuța

Gigel vrea să își construiască o căsuță în București. El vrea să aleagă o amplasare și o formă bună pentru fundația casei.

Pentru simplitate, considerăm Bucureștiul ca fiind un pătrat cu latura de $N$ metri, situat într-un sistem de coordonate cartezian, având colțul stânga-jos în punctul ($0$,$0$), și colțul dreapta-sus în punctul ($N$,$N$).

Gigel, excentric de fel, vrea ca forma fundației căsuței să fie una aparte, anume, trebuie să respecte următoarele condiții:

• Forma este un triunghi dreptunghic, având catetele paralele cu axele sistemului și colțul drept poziționat în dreapta-jos.
• Vârfurile formei au coordonatele întregi.
• Lungimea catetei orizontale este un multiplu al lungimii catetei verticale.

În București, unele zone sunt mai valoroase decât celelalte. Mai simplu, Gigel cunoaște pentru fiecare metru pătrat din București dacă acesta este valoros sau nu, prin intermediul unei matrice binare $V$, de dimensiuni $N \times N$. Elementul $V_{i,j}$ are valoarea 1 sau 0 după cum aria acoperită de pătratul cu colțul stânga-jos $(j-1,\ i-1)$ și colțul dreapta-sus $(j, i)$ este sau nu valoroasă. Numerotarea liniilor, respectiv a coloanelor începe de la $1$.

Definim valoarea unei forme ca fiind suma ariilor intersecțiilor dintre formă și fiecare pătrat valoros din București.

Cerință

Se dau $T$ variante de fundație care respectă condițiile impuse de Gigel. Pentru fiecare, afișați valoarea formei acesteia.

Date de intrare

Pe prima linie a fișierului casuta.in se află două numere, $N$ și $T$, cu semnificația din enunț. Urmează $N$ linii a câte $N$ cifre de $1$ sau de $0$, fără spații între ele, valorile matricei $V$, indexate de la 1. Pe următoarele $T$ linii se află câte patru întregi, $X_1,Y_1,X_2,Y_2$, reprezentând coordonatele vârfurilor ipotenuzei unei variante de fundație.

Date de ieșire

În fișierul casuta.out se va afișa câte un număr real pe fiecare dintre cele $T$ linii, anume valoarea acelei forme. Numerele trebuie afișate cu $5$ zecimale exacte.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$
• $1 \leq T \leq 1 \ 000 \ 000$
• $0 \le X_1 < X_2 \leq N, 0 \leq Y_1 < Y_2 \leq N$, pentru toate formele din intrare.
• Fie $\mathcal{L}$ lungimea celei mai mari catete verticale, și fie $\mathcal{A}$ suma ariilor tuturor formelor din intrare.

Exemplul 1

casuta.in

5 3
10000
01010
00000
00000
00100
0 0 2 2
1 0 5 2
2 4 5 5

casuta.out

1.00000
0.25000
0.16666

Explicație

Exemplul corespunde diagramei de mai jos. Cu mov am notat pătratele de arie valoroasă.