BOI 2004 举办地点的青年旅舍有一个由 $6 \times 6$ 个方格组成的停车场。停车场的行从上到下依次编号为 $1$ 到 $6$，列从左到右依次编号为 $1$ 到 $6$。停车场唯一的出口位于第三行的右侧。

在这个停车场里停放着 $N$ 辆车。你的车也在其中，但遗憾的是，由于被其他车辆阻挡，你的车无法轻易开出。你和你的朋友们可以向前或向后移动这些车，因为所有车的变速箱都处于空档（Neutral）。但是，你不能转弯或改变任何车辆（包括你自己的车和其他车）的方向。

你的任务是确定将你那辆大小为 $2 \times 1$ 方格的车开出停车场所需的最少步数。一步定义为将一辆车移动一个方格。除你的车外，其他任何车辆都不能移出停车场。

车只有两种尺寸：一种大小为 $2 \times 1$ 个方格，另一种大小为 $3 \times 1$ 个方格。车辆只能沿着其较长的一侧轴线方向移动。

在给定的样例中，$N = 8$，你的车编号为 $1$。

以下是使你的车驶出停车场的一个长度为 $18$ 的最少步数序列： $4 \leftarrow \leftarrow \leftarrow, 2 \rightarrow, 6 \uparrow, 3 \uparrow, 8 \leftarrow \leftarrow, 5 \downarrow \downarrow \downarrow, 7 \downarrow \downarrow, 1 \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow$。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 16$)，表示车辆的数量。

接下来的 $N$ 行，每行包含对编号为 $i$ 的车辆的描述。每行包含四个整数，依次指定：

• 长度 $l_i$
• 朝向 $o_i$
• 起始（左上角）坐标 $x_i$（列号）和 $y_i$（行号）

相邻的数字之间用单个空格分隔。$o_i = 1$ 表示该车水平停放。否则（$o_i = 0$），表示该车垂直停放。

满足以下限制条件：$l_i \in \{2, 3\}$，$o_i \in \{0, 1\}$，$1 \le x_i, y_i \le 6$。

你的车在紧接着包含数字 $N$ 的单行之后的首行（即输入的第二行，对应编号为 $1$ 的车）中进行描述。你的车必须通过唯一的出口驶出停车场。

输出格式

输出应仅包含一个整数，表示你的车驶出停车场所需的最少步数。

如果无法驶出停车场，则输出 -1。

样例

输入样例 1

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

输出样例 1

18