Trạm bus gần nhất

Bối cảnh

Có \(N\) học sinh và \(M\) trạm xe bus trên mặt phẳng tọa độ Oxy. Tọa độ của học sinh thứ \(i\ (1\leq i\leq N)\) là \((a_i, b_i)\), và tọa độ của trạm xe bus thứ \(j\ (1\leq j\leq N)\) là \((c_j, d_j)\). Chắc chắn rằng đi xe bus sẽ nhanh hơn đi bộ nên các học sinh muốn tìm đến trạm bus gần nhất để có thể đi học sớm nhất có thể. Khoảng cách của học sinh và trạm bus được tính bằng công thức \(|a_i - c_j| + |b_i - d_j|\).

Yêu cầu

Nếu có nhiều trạm bus gần nhất cho một học sinh thì học sinh đó sẽ chọn trạm bus có chỉ số \(j\) nhỏ nhất.

Input

Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) \((1\leq N, M\leq 50)\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i, b_i\ (-10^8\leq a_i, b_i\leq 10^8)\).

\(M\) dòng cuối cùng, mỗi dòng chứa hai số nguyên \(c_j, d_j\ (-10^8\leq c_j, d_j\leq 10^8)\).

Output

In ra \(N\) dòng, dòng thứ \(i\ (1\leq i\leq N)\) là chỉ số \(j\) của trạm bus mà học sinh thứ \(i\) đi.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

2 2
2 0
0 0
-1 0
1 0

Output

2
1

Ví dụ 2

Input

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

Output

3
1
2

Ví dụ 3

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

Giải thích ví dụ

Trong ví dụ 1:

Khoảng cách của học sinh \(1\) với từng trạm bus là:

• Với trạm bus \(1:\ |2-(-1)|+|0-0|=3\)
• Với trạm bus \(2:\ |2-1|+|0-0|=1\)

Do đó trạm bus gần nhất mà học sinh \(1\) đi có chỉ số là \(2\).

Khoảng cách của học sinh \(2\) với từng trạm bus là:

• Với trạm bus \(1:\ |0-(-1)|+|0-0|=1\)
• Với trạm bus \(2:\ |0-1|+|0-0|=1\)

Có nhiều trạm bus gần nhất, nên học sinh sẽ đến trạm có chỉ số nhỏ nhất là \(1\).

Thông tin học tập

• Buổi: B10
• Concepts: coordinate arrays, nested loops, Manhattan distance, tie-breaking
• Giới hạn kiến thức: B01-B10
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 20