Giải bài trực tuyến

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) * L .
1 <= N <= 10000 .
1 <= L <= 1000 .

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 xi , yi 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ơ (xi,yi) và 2 tương ứng là chọn vectơ (-xi,-yi) . Dữ liêụ đảm bảo có phương án.

Example

Input:
4 5
5 0
0 5
0 0
-3 4

Output:
1 2 1 1