Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

There are N students and M checkpoints on the xy-plane. The coordinates of the i-th…

  1. User

    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

  2. DeepSeek Assistant

    We need to solve a problem: Given N student coordinates (a_i,b_i), M checkpoint coordinates (c_j,d_j). For each student, find the checkpoint with minimal Manhattan distance. If multiple have same distance, choose the one with smallest index.

    Constraints N,M <= 50, so O(N*M) is trivial.

    We need to read input and output.

    But we need to implement solution.

    Edge cases: distances can be large (up to 2e8), but within 64-bit.

    Implementation: for each student, loop over checkpoints, compute Manhattan distance, keep track of min distance and min index. If distance < min_dist, update; if distance == min_dist and index < min_index, update.

    Output the index of the chosen checkpoint (1-indexed).

    That's it.

    We should provide Python code.

    But note: the problem expects output as lines with checkpoint indices. So implement in Python.

    Given that it's a typical AtCoder problem ABC111 B? Actually it's from AtCoder Beginner Contest 057 B? Check: "Checkpoints" problem from ABC 057 B? Let's check: ABC 057 B - Checkpoints? Actually ABC 057 B is "Checkpoints" where N and M up to 50, similar description. Yes.

    So solution is straightforward.

    We need to ensure reading input correctly.

    We'll write:

    def main(): import sys input = sys.stdin.readline N, M = map(int, input().split()) students = [tuple(map(int, input().split())) for _ in range(N)] checkpoints = [tuple(map(int, input().split())) for _ in range(M)] for a,b in students: min_dist = None min_idx = None for j, (c,d) in enumerate(checkpoints, start=1): dist = abs(a-c) + abs(b-d) if min_dist is None or dist < min_dist or (dist == min_dist and j < min_idx): min_dist = dist min_idx = j print(min_idx)

    if name == 'main': main()

    That's all.

    But as ChatGPT, we need to produce a final answer: The solution explanation and code.

    Given the instructions: The assistant should provide the solution.

    Thus final response: Explanation and code.

    I'll output the code.

    But ensure to follow typical format.

    I'll produce:

    import sys
    
    def main():
        input = sys.stdin.readline
        N, M = map(int, input().split())
        students = [tuple(map(int, input().split())) for _ in range(N)]
        checkpoints = [tuple(map(int, input().split())) for _ in range(M)]
    
        for ax, ay in students:
            best = 0
            best_dist = 10**18
            for idx, (cx, cy) in enumerate(checkpoints, start=1):
                dist = abs(ax - cx) + abs(ay - cy)
                if dist < best_dist or (dist == best_dist and idx < best):
                    best_dist = dist
                    best = idx
            print(best)
    
    if __name__ == '__main__':
        main()
    

    That works.

    I'll now answer. ```python

    import sys

    def main(): input = sys.stdin.readline N, M = map(int, input().split())

    students = [tuple(map(int, input().split())) for _ in range(N)]
    checkpoints = [tuple(map(int, input().split())) for _ in range(M)]
    
    for ax, ay in students:
        best_idx = 0          # will hold the answer (1‑based)
        best_dist = 10**18    # a very large number
    
        for idx, (cx, cy) in enumerate(checkpoints, start=1):
            dist = abs(ax - cx) + abs(ay - cy)
            # update if strictly better, or equal distance but smaller index
            if dist < best_dist or (dist == best_dist and idx < best_idx):
                best_dist = dist
                best_idx = idx
    
        print(best_idx)
    

    if name == "main": main()