Dạo chơi quanh nhà ( WALK )

Giới hạn
  • Thời gian: 0.117s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 10000 bytes

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


  • Người up: hard7771988
  • Điểm: 0.66
  • Ngôn ngữ cho phép:
  • Nguồn bài: VI Ural State University Collegiate Programming Contest (21.10.2001)