WALK - Dạo chơi quanh nhà

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

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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
  • Nguồn bài: VI Ural State University Collegiate Programming Contest (21.10.2001)