让我们构造一个由方格和方格间的墙组成的迷宫。从一个被墙包围的单个方格开始，然后对迷宫进行多次扩展。

扩展过程如下：将四个迷宫副本拼接在一起，形成一个 $2 \times 2$ 的副本方阵。现在，想象站在新迷宫的最中心，即四个方格交汇的一点。考虑从中心向外延伸的四堵长墙，它们分隔了相邻的副本。在这四堵墙中的三堵上，我们各开辟一个宽度为一个方格的通道。第四堵墙保持完整。

让我们记录一次具体的扩展。为从中心出发的墙分配四个数字：$r$ 代表向右的墙，$u$ 代表向上的墙，$l$ 代表向左的墙，$d$ 代表向下的墙。其中一个数字为零，其余三个数字决定了我们具体在何处开辟通道：即从中心开始计数的墙的单位线段编号。例如，1 表示紧邻中心的通道，2 表示从中心开始的第二个单位线段，依此类推。

下图展示了示例中迷宫的构造过程及结果。

我们得到的迷宫中，任意两个方格之间恰好存在一条简单路径；回想一下，如果一条路径访问每个方格最多一次，则称其为简单路径。回答 $q$ 个如下形式的问题：给定方格 $A$ 和 $B$ 的坐标，求它们之间简单路径的长度。路径长度为到达相邻方格的步数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 30$)。接下来的 $n$ 行定义了迷宫的构建方式。每一行描述一次扩展，包含四个整数：$r, u, l, d$。其中一个是零，其余三个严格为正。

下一行包含一个整数 $q$ ($1 \le q \le 1000$)。随后是 $q$ 行询问。每个询问包含四个整数：$row_A, col_A, row_B, col_B$。这些是迷宫中两个方格的坐标（从 $1$ 到 $2^n$）。其中，行从上到下编号，列从左到右编号。

输出格式

对于每个询问，输出一个整数：给定方格之间简单路径的长度。

样例

输入 1

3
0 1 1 1
1 0 1 1
0 3 1 2
4
4 5 4 5
5 4 8 1
5 8 1 8
5 5 4 5

输出 1

0
6
22
15