### 问题描述 在一个国家里，有 $N$ 个城市，它们被表示为平面上的点，其中一些城市是特殊的。通常，两个城市之间的旅行时间等于它们之间的曼哈顿距离。此外，如果两个城市都是特殊的，你可以在它们之间进行 $T$ 个时间单位的传送。 现在，卓卓需要回答 $Q$ 个形式的查询： - 给定两个城市 $A$ 和 $B$，从 $A$ 到 $B$ 的最快旅行时间。 请注意：没有两个点具有相同的坐标。 ### 输入格式 第一行包含两个整数 $N$ 和 $T$。 接下来的 $N$ 行中，每行包含三个整数 $s$ $x$ $y$，其中 $s$ 表示城市是否特殊，为 $1$ 表示特殊，为 $0$ 表示不特殊，而 $(x, y)$ 表示城市的坐标。 接下来一行包含一个整数 $Q$。 接下来的 $Q$ 行中，每行包含两个整数 $A$ 和 $B$。 ### 输出格式 输出 $Q$ 行，每行包含一个整数，代表一个查询的答案。 ### 样例输入 ``` 6 3 0 1 2 0 5 1 1 3 3 1 1 5 0 3 5 1 7 5 5 1 2 1 5 1 6 3 4 4 2 ``` ### 样例输出 ``` 5 5 6 3 7 ``` ### 评测数据规模 $2 \leq N \leq 1000$，$1 \leq T \leq 2000$，$1 \leq Q \leq 1000$，$0 \leq x, y \leq 1000$，$1 \leq A, B \leq N$。