> 在确定好主会场的位置后，小 T 和小 S 开始着手布置庆典会场。他们在通往主会场的必经之路上，设置了一块宽阔的展览区，用于展现十年 THUPC 的精彩画面。 > > 小 T 将展览区规划成了一个巨大的网格，最外围以及内部的部分格子被设为展览墙。为了方便大家沿动线参观，他将所有的展览墙精心设计为了四连通的结构。 > > 为了让参观过程更具趣味性，小 S 决定在这里举办一场寻宝活动。

小 T 将展览区规划成一个大小为 $$$n \times n$$$ 的二维网格。网格的最外围由一圈展览墙包围，即横坐标或纵坐标等于 $$$0$$$ 或 $$$n + 1$$$ 的所有格子均为展览墙格子。此外，展览区内部还散布着 $$$m$$$ 个展览墙格子，其中第 $$$i \ (1 \le i \le m)$$$ 个的坐标为 $$$(x_i, y_i)$$$。**保证所有的展览墙格子之间是四连通的。**

经过实地布景测试，小 T 总结出了在网格间移动的耗时规律。具体而言，在格子间有以下两种移动方式：

- 沿上下左右方向移动一格，即从 $$$(x, y)$$$ 移动到 $$$(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)$$$ 中的某一个相邻格子，需要消耗 $$$2$$$ 个单位时间。 - 沿对角线方向移动一格，即从 $$$(x, y)$$$ 移动到 $$$(x - 1, y - 1), (x - 1, y + 1), (x + 1, y - 1), (x + 1, y + 1)$$$ 中的某一个对角格子，需要消耗 $$$3$$$ 个单位时间。

当然，移动的目标位置不能是展览墙格子。**注意：沿对角线方向移动时，可以直接从两个对角展览墙格子之间的缝隙穿过。例如，即使 $$$(x, y + 1)$$$ 与 $$$(x + 1, y)$$$ 均为展览墙格子，依然可以消耗 $$$3$$$ 个单位时间，直接从 $$$(x, y)$$$ 沿对角线移动到 $$$(x + 1, y + 1)$$$。**

小 S 在展览区中总计布置了 $$$q$$$ 个宝藏。对于第 $$$i \ (1 \le i \le q)$$$ 个宝藏，她会公布它的位置 $$$(tx_i, ty_i)$$$，而公布时你所处的位置为 $$$(sx_i, sy_i)$$$。为了以最快速度夺得各个宝藏，你需要计算出，从你所处的位置移动到宝藏所在位置的最短耗时。