U blizini Mirkovog sela nalazi se šuma u kojoj slučajni prolaznici često pronalaze tartufe. Šumu možemo predstaviti kvadratom čija je duljina stranica 2·N metara. Središte kvadrata nalazi se u ishodištu koordinatnog sustava, a stranice kvadrata su paralelne koordinatnim osima.</p>

Kvadrat je podijeljen na 2·N × 2·N jednakih područja, a za svako područje je poznato koliko grama tartufa možemo pronaći ako prošećemo jednim metrom tog područja. 

Slika prikazuje test primjer

Mirko planira napraviti M šetnji. U jednoj šetnji, Mirko će odabrati neki pravac koji nije paralelan s koordinatnim osima, te prošetati po tom pravcu.

Za svaku šetnju, ispišite koliko ukupno grama tartufa Mirko može pronaći u toj šetnji. 

입력 형식

U prvom redu nalazi se cijeli broj N (1 ≤ N ≤ 500), polovica širine stranice šume.</p>

U svakom od sljedećih 2·N redova nalazi se po 2·N znakova ‘1’ - ‘9’ koji označavaju broj grama tartufa po prošetanom metru za svako od područja. Područja su navedena od sjevera prema jugu (tj. padajuće po y-koordinati), te od zapada prema istoku (tj. rastuće po x koordinati), kao na slici gore.

U sljedećem redu nalazi se cijeli broj M (1 ≤ M ≤ 2000), broj šetnji.

U svakom od sljedećih M redova nalaze se po četiri cijela broja x₁ , y₁ , x₂ i y₂ , koordinate dvije različite točke na pravcu kojim će Mirko prošetati.

Vrijedi: -10000 ≤ x₁ , y₁ , x₂ , y₂ ≤ 10000, x₁ ≠ x₂ , y₁ ≠ y₂ . 

출력 형식

Potrebno je ispisati M realnih brojeva na barem 5 decimala, svaki u zaseban redak. i-ti od tih brojeva govori koliko grama tartufa Mirko može pronaći u i-toj šetnji. 

예제 입력

2
1357
2468
1111
9999
4
0 0 1 1
-3 0 0 3
-2 0 2 -1
2 -4 4 2

예제 출력

32.52691
1.41421
4.12311
0.00000