Under construction

Still being built. Things may change

Wiing Wiing

Interview

Time limit2sMemory limit1024 MB

Summary
Sort N points around Hyeok by the angle of a counterclockwise rotating ray from him, with nearer people first when two share a direction.
Level

Medium5 of 10

Topics
Sorting, Geometry
Solved
No attempts yet

Problem

비잉비잉 돌아가는\n>\n> 세상도 나를 비웃듯이 계속 꿈틀대죠\n\nHyeok is surrounded by NN people in the middle of a department store. The ii-th person is at the plane coordinates (Xi,Yi)(X_i, Y_i), and no one stands at the same position as Hyeok. Hyeok stops everyone's time, turns in place counterclockwise, and records in order the positions of the people in front of him at each moment. When several people are in front of him, he records them starting with the one closest to him.

Input

The first line contains NN, the number of people excluding Hyeok. (1≤N≤300 0001 \le N \le 300\,000)

Each of the next NN lines contains the position XiX_i and YiY_i of a person, separated by a space, excluding Hyeok. (−109≤Xi,Yi≤109-10^9 \le X_i, Y_i \le 10^9)

The next line contains Hyeok's position XHX_H and YHY_H, separated by a space. Hyeok is at (XH,YH)(X_H, Y_H). (−109≤XH,YH≤109-10^9 \le X_H, Y_H \le 10^9)

Output

Print the positions Hyeok recorded, in order, one per line from the first line to the NN-th line. Each line contains XiX_i and YiY_i separated by a space.

If there are several possible answers, print any of them.

Examples1

  1. Example 1

    Input
    8
    5 -3
    10 1
    -1 2
    1 7
    2 1
    2 5
    5 4
    6 -1
    3 2
    
    Expected output
    -1 2
    2 1
    5 -3
    6 -1
    10 1
    5 4
    2 5
    1 7