CF1869B.2D Traveling

Piggy lives on an infinite plane with the Cartesian coordinate system on it.

There are $n$ cities on the plane, numbered from $1$ to $n$, and the first $k$ cities are defined as major cities. The coordinates of the $i$-th city are $(x_i,y_i)$.

Piggy, as a well-experienced traveller, wants to have a relaxing trip after Zhongkao examination. Currently, he is in city $a$, and he wants to travel to city $b$ by air. You can fly between any two cities, and you can visit several cities in any order while travelling, but the final destination must be city $b$.

Because of active trade between major cities, it's possible to travel by plane between them for free. Formally, the price of an air ticket $f(i,j)$ between two cities $i$ and $j$ is defined as follows:

f(i,j)= \\begin{cases} 0, & \\text{if cities }i \\text{ and }j \\text{ are both major cities} \\\\ |x\_i-x\_j|+|y\_i-y\_j|, & \\text{otherwise} \\end{cases}

Piggy doesn't want to save time, but he wants to save money. So you need to tell him the minimum value of the total cost of all air tickets if he can take any number of flights.

小猪生活在一个带有笛卡尔坐标系的无限平面上。

平面上有 $n$ 座城市，编号从 $1$ 到 $n$，其中前 $k$ 座城市被定义为“主要城市”。第 $i$ 座城市的坐标为 $(x_i, y_i)$。

作为一位经验丰富的旅行者，小猪希望在中考结束后来一场轻松的旅行。目前他位于城市 $a$，并希望乘飞机前往城市 $b$。你可以在任意两座城市之间直飞，旅行途中可以按任意顺序访问若干中间城市，但最终目的地必须是城市 $b$。

由于主要城市之间贸易活跃，它们之间的航班可免费乘坐。形式化地，城市 $i$ 与城市 $j$ 之间的机票价格 $f(i,j)$ 定义如下：

$$f(i,j)= \begin{cases} 0, & \text{若城市 }i \text{ 和 }j \text{ 均为主要城市} \\ |x_i-x_j|+|y_i-y_j|, & \text{否则} \end{cases}$$

小猪并不追求节省时间，而只希望节省金钱。因此你需要告诉他：在允许任意次数飞行的前提下，所有机票费用之和的最小值是多少？

The first line of input contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains four integers $n$, $k$, $a$ and $b$ ($2\le n\le 2\cdot 10^5$, $0\le k\le n$, $1\le a,b\le n$, $a\ne b$) — the number of cities, the number of major cities and the numbers of the starting and the ending cities.

Then $n$ lines follow, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^9\le x_i,y_i\le 10^9$) — the coordinates of the $i$-th city. The first $k$ lines describe major cities. It is guaranteed that all coordinates are pairwise distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

输入的第一行包含一个整数 $t$（$1\le t\le 10^4$）—— 表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含四个整数 $n$、$k$、$a$ 和 $b$（$2\le n\le 2\cdot 10^5$，$0\le k\le n$，$1\le a,b\le n$，$a\ne b$）—— 分别表示城市的数量、主要城市的数量，以及起点城市和终点城市的编号。

接下来是 $n$ 行，其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$-10^9\le x_i,y_i\le 10^9$）—— 表示第 $i$ 个城市的坐标。前 $k$ 行描述的是主要城市。保证所有坐标的两两互不相同。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$。

For each test case, print a single integer — the minimum value of the total price of all air tickets.

对于每个测试用例，输出一个整数——所有机票总价的最小值。

In the first test case:

The major cities are marked red.

The optimal way to choose the flights is: $3\rightarrow 1 \rightarrow 2 \rightarrow 5$, which will cost $3+0+1=4$. Note that the flight $1\rightarrow 2$ costs $0$, because both city $1$ and $2$ are major cities.

In the second test case, since there are only $2$ cities, the only way is to take a flight from city $1$ to $2$.

In the third test case, since city $2$ and $4$ are both major cities, Piggy can directly take a flight from city $2$ to $4$, which costs $0$.

In the fourth test case, Piggy can choose to take the following flights: $3\rightarrow 2\rightarrow 1$, and the cost is $11+11=22$.

在第一个测试用例中：

主要城市以红色标出。

选择航班的最优方案为：$3\rightarrow 1 \rightarrow 2 \rightarrow 5$，总花费为 $3+0+1=4$。注意，航班 $1\rightarrow 2$ 的花费为 $0$，因为城市 $1$ 和城市 $2$ 均为主要城市。

在第二个测试用例中，由于仅有 $2$ 座城市，唯一的方式是从城市 $1$ 飞往城市 $2$。

在第三个测试用例中，由于城市 $2$ 和城市 $4$ 均为主要城市，Piggy 可直接从城市 $2$ 飞往城市 $4$，花费为 $0$。

在第四个测试用例中，Piggy 可选择以下航班路线：$3\rightarrow 2\rightarrow 1$，总花费为 $11+11=22$。