There are N students and M checkpoints on the xy-plane.
The coordinates of the i-th student (1 \leq i \leq N) is (a_i,b_i), and the coordinates of the checkpoint numbered j (1 \leq j \leq M) is (c_j,d_j).
When the teacher gives a signal, each student has to go to the nearest checkpoint measured in Manhattan distance.
The Manhattan distance between two points (x_1,y_1) and (x_2,y_2) is |x_1-x_2|+|y_1-y_2|.
Here, |x| denotes the absolute value of x.
If there are multiple nearest checkpoints for a student, he/she will select the checkpoint with the smallest index.
Which checkpoint will each student go to?

Constraints

* 1 \leq N,M \leq 50
* -10^8 \leq a_i,b_i,c_j,d_j \leq 10^8
* All input values are integers.

Input

The input is given from Standard Input in the following format:


N M
a_1 b_1
:
a_N b_N
c_1 d_1
:
c_M d_M


Output

Print N lines.
The i-th line (1 \leq i \leq N) should contain the index of the checkpoint for the i-th student to go.

Examples

Input

2 2
2 0
0 0
-1 0
1 0


Output

2
1


Input

3 4
10 10
-10 -10
3 3
1 2
2 3
3 5
3 5


Output

3
1
2


Input

5 5
-100000000 -100000000
-100000000 100000000
100000000 -100000000
100000000 100000000
0 0
0 0
100000000 100000000
100000000 -100000000
-100000000 100000000
-100000000 -100000000


Output

5
4
3
2
1

import java.util.Scanner;

public class Main {
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int m = sc.nextInt();

		int s[] = new int [n * 2];
		int c[] = new int [m * 2];

		for (int i = 0; i < n; ++i)
		{
			s[i * 2] = sc.nextInt();
			s[i * 2 + 1] = sc.nextInt();

			//System.out.print(s[i * 2] + " ");
			//System.out.println(s[i * 2 + 1]);
		}

		//System.out.println();

		for (int i = 0; i < m; ++i)
		{
			c[i * 2] = sc.nextInt();
			c[i * 2 + 1] = sc.nextInt();

			//System.out.print(c[i * 2] + " ");
			//System.out.println(c[i * 2 + 1]);
		}

		//System.out.println();

		sc.close();

		for (int i = 0; i < n; ++i)
		{
			int dist = Integer.MAX_VALUE, index = -1;

			//System.out.println(index + " " + dist);

			for (int j = 0; j < m; ++j)
			{
				int tmp = Math.abs(s[i * 2] - c[j * 2]) + Math.abs(s[i * 2 + 1] - c[j * 2 + 1]);

				if (tmp < dist)
				{
					dist = tmp;
					index = j + 1;

					//System.out.println("D:" + tmp + " " + dist + " " + index);
				}
			}

			System.out.println(index);
		}
	}
}
