송로버섯

미르코의 마을 근처에는 지나가던 사람들이 송로버섯을 자주 발견하는 숲이 있다. 숲은 한 변의 길이가 $2N$미터인 정사각형이다. 정사각형의 중심은 좌표계의 원점에 있고, 변은 좌표축에 평행하다.

정사각형은 $2N \times 2N$개의 같은 크기의 구역으로 나뉘어 있다. 각 구역은 한 변이 1미터인 정사각형이다. 구역마다 그 구역 안에서 1미터를 걸을 때 찾을 수 있는 송로버섯의 양(그램)이 정해져 있다.

그림은 예제를 나타낸다.

미르코는 산책을 $M$번 할 계획이다. 한 번 산책할 때 미르코는 좌표축에 평행하지 않은 직선 하나를 골라 그 직선을 따라 걷는다.

산책마다 미르코가 찾을 수 있는 송로버섯의 총량(그램)을 출력하라. 이 양은 직선이 숲 안의 각 구역을 지나는 길이에 그 구역의 값을 곱해 모두 더한 값이다. 직선이 구역의 꼭짓점 한 점만 지나면 그 구역에서 걷는 길이는 0이다.

첫째 줄에 정수 $N$ ($1 \le N \le 500$)이 주어진다. $N$은 숲의 한 변 길이의 절반이다.

다음 $2N$개의 줄에는 각각 1부터 9까지의 문자가 $2N$개씩 주어진다. 각 문자는 그 구역에서 1미터를 걸을 때 찾는 송로버섯의 양(그램)이다. 구역은 북쪽에서 남쪽 순서(즉 $y$좌표가 감소하는 순서)로, 한 줄 안에서는 서쪽에서 동쪽 순서(즉 $x$좌표가 증가하는 순서)로 주어진다. 위 그림과 같다.

다음 줄에 산책 횟수를 나타내는 정수 $M$ ($1 \le M \le 2000$)이 주어진다.

다음 $M$개의 줄에는 각각 정수 네 개 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다. 이는 미르코가 걸을 직선 위의 서로 다른 두 점 $(x_1, y_1)$, $(x_2, y_2)$의 좌표이다.

$-10000 \le x_1, y_1, x_2, y_2 \le 10000$, $x_1 \ne x_2$, $y_1 \ne y_2$이다.

$M$개의 줄에 걸쳐 한 줄에 하나씩 실수를 출력한다. $i$번째 수는 $i$번째 산책에서 미르코가 찾을 수 있는 송로버섯의 총량(그램)이다.

각 값은 정확한 값을 소수점 아래 여섯째 자리에서 반올림해 소수점 아래 정확히 다섯 자리로 출력한다. 정확한 값이 두 후보의 한가운데이면 큰 쪽으로 올린다. 예를 들어 0은 0.00000으로 출력한다.