在 Mirko 的村庄附近有一片森林，路人经常在那里发现松露。我们可以将这片森林表示为一个边长为 $2 \cdot N$ 米的正方形。该正方形的中心位于坐标系原点，且其边与坐标轴平行。

该正方形被划分为 $2 \cdot N \times 2 \cdot N$ 个相等的小区域，对于每个区域，已知在该区域内每走一米可以找到多少克松露。

图片展示了测试样例

Mirko 计划进行 $M$ 次散步。在每次散步中，Mirko 会选择一条不与坐标轴平行的直线，并沿着该直线行走。

对于每次散步，请计算 Mirko 在该次散步中总共能找到多少克松露。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 500$)，表示森林边长的一半。

接下来的 $2 \cdot N$ 行，每行包含 $2 \cdot N$ 个字符（'1' - '9'），表示每个区域每走一米能找到的松露克数。区域按从北向南（即 $y$ 坐标递减）和从西向东（即 $x$ 坐标递增）的顺序给出，如上图所示。

接下来一行包含一个整数 $M$ ($1 \le M \le 2000$)，表示散步次数。

接下来的 $M$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$，表示 Mirko 将要行走的直线上两个不同点的坐标。

满足：$-10000 \le x_1, y_1, x_2, y_2 \le 10000$，$x_1 \neq x_2$，$y_1 \neq y_2$。

输出格式

输出 $M$ 个实数，每个实数占一行，保留至少 5 位小数。第 $i$ 个数表示 Mirko 在第 $i$ 次散步中能找到的松露克数。

样例

输入 1

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

输出 1

32.52691 
1.41421 
4.12311 
0.00000