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, ..., 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+...+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. 

Input

Input contains one or several test cases. The first input line contains a single integer number t (1 ≤ t ≤ 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 ≤ a, b ≤ 3000) — numbers of Algoland cities and number of Berland cities correspondingly.

The next line contains b space-separated integers r_1, r_2, ..., r_b (1 ≤ r_b ≤ 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+...+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 ≤ xa_i, ya_i ≤ 10000). The next b lines contain coordinates of the Berland cities — pairs of space-separated integers xb_i, yb_i (-10000 ≤ xb_i, yb_i ≤ 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.

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.

Example

Input

2
2 3
1 1 2
0 0
1 1
1 2
3 2
4 0
1 1
1
0 0
0 1


Output

YES
2 2
1 2
3 2
3 1
YES
1 1
#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int n = 0, f = 1;
  char c;
  for (c = getchar(); c != '-' && (c < '0' || c > '9'); c = getchar())
    ;
  if (c == '-') c = getchar(), f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - 48;
  return n * f;
}
struct ar {
  int x, y, id, d;
} now;
bool operator<(ar a, ar b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
int i, a, b, d[3005];
vector<ar> p, an;
bool cmp(ar a, ar b) { return a.x * b.y > a.y * b.x; }
void solve(vector<ar> p) {
  int i, j, k, D, n = p.size() - 1;
  if (!n) return;
  for (i = 1; i <= n; i++)
    if (p[i] < p[0]) swap(p[i], p[0]);
  for (i = 1; i <= n; i++) p[i].x -= p[0].x, p[i].y -= p[0].y;
  sort(p.begin() + 1, p.end(), cmp);
  for (i = 1; i <= n; i++) p[i].x += p[0].x, p[i].y += p[0].y;
  if (p[0].d < 0) {
    for (i = 1; i <= n; i++) {
      j = i, D = 0;
      for (;; i++) {
        D += p[i].d;
        if (D >= 0) break;
      }
      p[i].d--, an.push_back((ar){p[i].id, p[0].id});
      p[i].d -= D;
      solve(vector<ar>(p.begin() + j, p.begin() + i + 1));
      p[j = i].d = D - 1;
      for (; D;) D += p[++i].d;
      solve(vector<ar>(p.begin() + j, p.begin() + i + 1));
    }
    return;
  }
  for (i = 1; p[0].d >= 0;) {
    for (j = i, D = 1; D; i++) D += p[i].d;
    p[0].d--, an.push_back((ar){p[0].id, p[i - 1].id});
    solve(vector<ar>(p.begin() + j, p.begin() + i));
  }
  solve(vector<ar>(p.begin() + i - 1, p.end()));
}
void work() {
  a = read(), b = read();
  for (i = 1; i <= b; i++) d[i] = read();
  p.clear(), an.clear();
  for (i = 1; i <= a + b; i++) {
    now.x = read(), now.y = read();
    if (i <= a)
      now.id = i, now.d = -1;
    else
      now.d = d[now.id = i - a] - 1;
    p.push_back(now);
  }
  solve(p);
  puts("YES");
  for (i = 0; i <= a + b - 2; i++) printf("%d %d\n", an[i].x, an[i].y);
}
int main() {
  for (int t = read(); t--;) work();
}
