Cho ~N~ vectơ có độ dài không quá ~L~. Xét đến vectơ ~i~ ~(x~, ~y)~ ta có thể chọn vectơ ~i~ ~(x~, ~y)~ hoặc vectơ ~-i~ ~(-x, -y)~. Yêu cầu hãy xác định ~1~ cách chọn các vectơ sao cho vectơ tổng của ~N~ vectơ thì có độ dài không quá ~\sqrt{2} \times L~.

Input

• Dòng ~1~: ~2~ số nguyên ~N~, ~L~.
• ~N~ dòng tiếp theo mỗi dòng gồm ~2~ số nguyên ~x_i~, ~y_i~ mô tả vectơ ~i~.

Output

• Gồm ~1~ dòng ghi ra ~N~ số nguyên, số thứ ~i~ là ~1~ tương ứng là chọn vectơ ~(x_i, y_i)~ và ~2~ tương ứng là chọn vectơ ~(-x_i, -y_i)~. Dữ liêụ đảm bảo có phương án.

Giới hạn

• ~1 \le N \le 10000~.
• ~1 \le L \le 1000~.

Sample Input

4 5
5 0
0 5
0 0
-3 4

Sample Output

1 2 1 1