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.
Output
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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 3
1 1 2
0 0
1 1
1 2
3 2
4 0
1 1
1
0 0
0 1
|
YES
2 2
1 2
3 2
3 1
YES
1 1
|