题目描述

设计师 Niko 正在建造一座由方格和墙组成的分形迷宫。最开始，迷宫只有一个方格，四周都被墙围住。之后，他会进行若干次扩展。

一次扩展的过程如下：先取当前迷宫的四份拷贝，将它们拼成一个 $2\times 2$ 的大迷宫。站在新迷宫的正中心，也就是四份拷贝交界的点，可以看到四道从中心出发、分隔相邻拷贝的长墙。在其中三道墙上，各打开一个宽度为一个方格的通道；剩下一道墙保持完整。

一次具体扩展由四个整数 $r,u,l,d$ 描述，分别对应从中心向右、向上、向左、向下的四道墙。其中恰好有一个数为 $0$，表示对应方向的墙不打开通道。其余三个正整数表示通道的位置：从中心开始数，第几个单位墙段被打开。例如，$1$ 表示紧挨中心的单位墙段，$2$ 表示从中心数第二个单位墙段，依此类推。

展示从单个方格开始，依次按三次扩展参数 r=0,u=1,l=1,d=1、r=1,u=0,l=1,d=1、r=0,u=3,l=1,d=2 构造迷宫，并标出 $r,u,l,d$ 四个方向及最终迷宫。

最终得到的迷宫中，任意两个方格之间都恰好存在一条简单路径。这里简单路径指每个方格至多访问一次的路径。

现在有 $q$ 个询问。每个询问给出两个方格 $A,B$ 的坐标，请求出它们之间简单路径的长度。路径长度定义为移动到相邻方格的步数。

输入格式

第一行包含一个整数 $n$，表示扩展次数。

接下来 $n$ 行，每行包含四个整数 $r,u,l,d$，描述一次扩展。每行中恰好有一个数为 $0$，其余三个数均为正整数。

接下来一行包含一个整数 $q$。

接下来 $q$ 行，每行包含四个整数 $row_A,col_A,row_B,col_B$，表示两个方格在最终迷宫中的坐标。坐标范围为 $1$ 到 $2^n$，行从上到下编号，列从左到右编号。

输出格式

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

数据范围

• $1\le n\le 30$；
• $1\le q\le 1000$；
• $1\le row_A,col_A,row_B,col_B\le 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

输出

0
6
22
15