CF1070M.Algoland and Berland

Once upon a time Algoland and Berland were a single country, but those times are long gone. Now they are two different countries, but their cities are scattered on a common territory.

All cities are represented as points on the Cartesian plane. Algoland consists of $a$ cities numbered from $1$ to $a$. The coordinates of the $i$-th Algoland city are a pair of integer numbers $(xa_i, ya_i)$. Similarly, Berland consists of $b$ cities numbered from $1$ to $b$. The coordinates of the $j$-th Berland city are a pair of integer numbers $(xb_j, yb_j)$. No three of the $a+b$ mentioned cities lie on a single straight line.

As the first step to unite the countries, Berland decided to build several bidirectional freeways. Each freeway is going to be a line segment that starts in a Berland city and ends in an Algoland city. Freeways can't intersect with each other at any point except freeway's start or end. Moreover, the freeways have to connect all $a+b$ cities. Here, connectivity means that one can get from any of the specified $a+b$ cities to any other of the $a+b$ cities using freeways. Note that all freeways are bidirectional, which means that one can drive on each of them in both directions.

Mayor of each of the $b$ Berland cities allocated a budget to build the freeways that start from this city. Thus, you are given the numbers $r_1, r_2, \dots, r_b$, where $r_j$ is the number of freeways that are going to start in the $j$-th Berland city. The total allocated budget is very tight and only covers building the minimal necessary set of freeways. In other words, $r_1+r_2+\dots+r_b=a+b-1$.

Help Berland to build the freeways so that:

• each freeway is a line segment connecting a Berland city and an Algoland city,
• no freeways intersect with each other except for the freeway's start or end,
• freeways connect all $a+b$ cities (all freeways are bidirectional),
• there are $r_j$ freeways that start from the $j$-th Berland city.

很久以前，Algoland 和 Berland 曾是一个国家，但那段时光早已成为过去。如今它们已成为两个不同的国家，然而它们的城市却散布在同一片领土上。

所有城市均被表示为笛卡尔平面上的点。Algoland 由 $a$ 座城市组成，编号从 $1$ 到 $a$。第 $i$ 座 Algoland 城市的坐标为一对整数 $(xa_i, ya_i)$。类似地，Berland 由 $b$ 座城市组成，编号从 $1$ 到 $b$。第 $j$ 座 Berland 城市的坐标为一对整数 $(xb_j, yb_j)$。在全部 $a+b$ 座上述城市中，任意三点均不共线。

作为两国统一的第一步，Berland 决定修建若干条双向高速公路。每条高速公路均为一条线段，其起点为一座 Berland 城市，终点为一座 Algoland 城市。高速公路之间除端点（即起点或终点）外，不得在任何位置相交。此外，这些高速公路必须连接全部 $a+b$ 座城市。此处“连通”指：对于给定的 $a+b$ 座城市中的任意两座，均可仅通过高速公路（双向通行）相互抵达。

每个 Berland 城市的市长均划拨了预算，用于修建从该城市出发的高速公路。因此，你将获得一组数 $r_1, r_2, \dots, r_b$，其中 $r_j$ 表示将从第 $j$ 座 Berland 城市出发修建的高速公路数量。总预算极为紧张，仅够修建满足要求的最少数量的高速公路。换言之，$r_1+r_2+\dots+r_b=a+b-1$。

请帮助 Berland 修建高速公路，使得：

• 每条高速公路均为连接一座 Berland 城市与一座 Algoland 城市的线段；
• 高速公路之间除端点（即起点或终点）外不相交；
• 高速公路连通全部 $a+b$ 座城市（所有高速公路均为双向）；
• 从第 $j$ 座 Berland 城市出发的高速公路数量恰好为 $r_j$。

Input contains one or several test cases. The first input line contains a single integer number $t$ ($1 \le t \le 3000$) — number of test cases. Then, $t$ test cases follow. Solve test cases separately, test cases are completely independent and do not affect each other.

Each test case starts with a line containing space-separated integers $a$ and $b$ ($1 \le a, b \le 3000$) — numbers of Algoland cities and number of Berland cities correspondingly.

The next line contains $b$ space-separated integers $r_1, r_2, \dots, r_b$ ($1 \le r_b \le a$) where $r_j$ is the number of freeways, that should start in the $j$-th Berland city. It is guaranteed that $r_1+r_2+\dots+r_b=a+b-1$.

The next $a$ lines contain coordinates of the Algoland cities — pairs of space-separated integers $xa_i, ya_i$ ($-10000 \le xa_i, ya_i \le 10000$). The next $b$ lines contain coordinates of the Berland cities — pairs of space-separated integers $xb_i, yb_i$ ($-10000 \le xb_i, yb_i \le 10000$). All cities are located at distinct points, no three of the $a+b$ cities lie on a single straight line.

Sum of values $a$ across all test cases doesn't exceed $3000$. Sum of values $b$ across all test cases doesn't exceed $3000$.

输入包含一个或多个测试用例。第一行输入为一个整数 $t$（$1 \le t \le 3000$），表示测试用例的数量。随后是 $t$ 个测试用例。请独立求解每个测试用例，各测试用例之间完全独立，互不影响。

每个测试用例以一行开始，该行包含两个用空格分隔的整数 $a$ 和 $b$（$1 \le a, b \le 3000$），分别表示 Algoland 城市的数量和 Berland 城市的数量。

下一行包含 $b$ 个用空格分隔的整数 $r_1, r_2, \dots, r_b$（$1 \le r_j \le a$），其中 $r_j$ 表示第 $j$ 个 Berland 城市应作为起点的高速公路数量。保证 $r_1+r_2+\dots+r_b=a+b-1$。

接下来的 $a$ 行给出 Algoland 城市的坐标——每行为一对用空格分隔的整数 $xa_i, ya_i$（$-10000 \le xa_i, ya_i \le 10000$）。再接下来的 $b$ 行给出 Berland 城市的坐标——每行为一对用空格分隔的整数 $xb_i, yb_i$（$-10000 \le xb_i, yb_i \le 10000$）。所有城市均位于互不重合的点上，且全部 $a+b$ 个城市中任意三点不共线。

所有测试用例中 $a$ 的总和不超过 $3000$；所有测试用例中 $b$ 的总和不超过 $3000$。

For each of the $t$ test cases, first print "YES" if there is an answer or "NO" otherwise.

If there is an answer, print the freeway building plan in the next $a+b-1$ lines. Each line of the plan should contain two space-separated integers $j$ and $i$ which means that a freeway from the $j$-th Berland city to the $i$-th Algoland city should be built. If there are multiple solutions, print any.

对于每个测试用例，首先输出“YES”（若存在解），否则输出“NO”。

若存在解，则在接下来的 $a+b-1$ 行中输出高速公路建设方案。方案中每行应包含两个以空格分隔的整数 $j$ 和 $i$，表示需修建一条从第 $j$ 个 Berland 城市到第 $i$ 个 Algoland 城市的高速公路。若存在多种解，输出任意一种即可。