曾几何时,阿尔戈兰和贝尔兰是一个国家,但那些时代早已一去不复返了。现在它们是两个不同的国家,但它们的城市分散在共同的领土上。
所有城市都表示为笛卡尔平面上的点。 Algoland 由 $$$a$$$ 城市组成,编号从 $$$1$$$ 到 $$$a$$$。第 $$$i$$$ 个 Algoland 城市的坐标是一对整数 $$$(xa_i, ya_i)$$$。同样,Berland 由 $$$b$$$ 城市组成,编号从 $$$1$$$ 到 $$$b$$$。第 $$$j$$$ 个 Berland 城市的坐标是一对整数 $$$(xb_j, yb_j)$$$。 $$$a+b$$$ 提到的三个城市都不位于一条直线上。
作为团结各国的第一步,伯兰决定修建几条双向高速公路。每条高速公路都是一条线段,起始于 Berland 城市,结束于 Algoland 城市。除高速公路的起点或终点外,高速公路不能在任何点相互相交。此外,高速公路必须连接所有 $$$a+b$$$ 城市。在这里,连通性意味着人们可以使用高速公路从任何指定的 $$$a+b$$$ 城市前往任何其他 $$$a+b$$$ 城市。请注意,所有高速公路都是双向的,这意味着人们可以在每条高速公路上双向行驶。
每个 $$$b$$$ Berland 城市的市长都会分配预算来建设从该城市开始的高速公路。因此,您将得到数字 $$$r_1, r_2, \dots, r_b$$$,其中 $$$r_j$$$ 是第 $$$j$$$ 伯兰城市中将要开始的高速公路数量。分配的总预算非常紧张,仅涵盖建设最低限度的必要高速公路。换句话说,$$$r_1+r_2+\dots+r_b=a+b-1$$$。
帮助 Berland 修建高速公路,以便:
- 每条高速公路都是连接 Berland 城市和 Algoland 城市的线段,
- 除高速公路的起点或终点外,没有高速公路彼此相交,
- 高速公路连接所有 $$$a+b$$$ 城市(所有高速公路都是双向的),
- 有 $$$r_j$$$ 高速公路从第 $$$j$$$ 个 Berland 城市开始。
输入
输入包含一个或多个测试用例。第一个输入行包含一个整数 $$$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_b \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$$$。
输出
对于每个 $$$t$$$ 测试用例,如果有答案,首先打印“YES”,否则打印“NO”。
如果有答案,请在接下来的 $$$a+b-1$$$ 行中打印高速公路建筑平面图。计划的每一行应包含两个以空格分隔的整数 $$$j$$$ 和 $$$i$$$,这意味着应修建一条从第 $$$j$$$ 个 Berland 城市到第 $$$i$$$ 个 Algoland 城市的高速公路。如果有多个解决方案,请打印其中一个。
示例
输入 #1
2 2 3 1 1 2 0 0 1 1 1 2 3 2 4 0 1 1 1 0 0 0 1
输出 #1
YES 2 2 1 2 3 2 3 1 YES 1 1