Vùng đất Utopia xinh đẹp từng bị chiến tranh tàn phá. Khi chiến sự lắng xuống, đất nước được chia thành bốn vùng bởi một đường kinh tuyến chạy theo hướng bắc–nam và một đường vĩ tuyến chạy theo hướng đông–tây. Giao điểm của chúng được gọi là điểm \((0,0)\). Cả bốn vùng đều nhận tên Utopia, nhưng dần dần được gọi là Utopia 1 ở phía đông bắc, Utopia 2 ở phía tây bắc, Utopia 3 ở phía tây nam và Utopia 4 ở phía đông nam.

Vị trí của một điểm được xác định bằng khoảng cách có dấu về phía đông và về phía bắc so với \((0,0)\): chiều dương của trục hoành hướng đông, chiều dương của trục tung hướng bắc. Các khoảng cách này có thể âm.

Các vùng được đánh số như sau: vùng 1 có \(x>0,y>0\); vùng 2 có \(x<0,y>0\); vùng 3 có \(x<0,y<0\); vùng 4 có \(x>0,y<0\). Các điểm trên hai trục tọa độ không thuộc vùng nào.

Một trở ngại lớn là người dân không được phép vượt qua biên giới giữa các vùng. May mắn thay, một số thí sinh IOI tài giỏi của Utopia đã phát minh ra một phương thức dịch chuyển tức thời an toàn. Máy dịch chuyển cần các mã số, mỗi mã chỉ được dùng một lần.

Thử thách dành cho nhóm thí sinh ấy và cho bạn là điều khiển máy từ vị trí ban đầu \((0,0)\) lần lượt đến \(N\) vùng theo một danh sách cho trước. Bạn có thể đáp xuống bất kỳ điểm nào bên trong vùng được yêu cầu. Hai hay nhiều vùng liên tiếp trong danh sách có thể giống nhau. Sau khi rời vị trí ban đầu, bạn không bao giờ được đáp xuống đường biên.

Bạn có \(2N\) mã số nguyên dương, đôi một khác nhau. Trong mỗi lần dịch chuyển, chọn hai mã chưa dùng, gắn cho mỗi mã một dấu + hoặc -, rồi dùng chúng làm độ dịch chuyển theo trục hoành và trục tung. Nếu vị trí hiện tại là \((x,y)\) và cặp số có dấu là \((u,v)\), vị trí mới sẽ là \((x+u,y+v)\). Chẳng hạn, cặp \((+u,-v)\) đưa bạn đến \((x+u,y-v)\). Bạn có thể sử dụng các mã theo bất kỳ thứ tự nào, nhưng mỗi mã phải được dùng đúng một lần trong toàn bộ hành trình.

Hãy tìm một hành trình thỏa mãn danh sách vùng đã cho.

Dữ liệu vào

• Dòng đầu chứa \(N\), với \(1\le N\le 10000\).
• Dòng thứ hai chứa \(2N\) mã số nguyên dương đôi một khác nhau, mỗi mã không vượt quá \(100000\).
• Dòng cuối chứa \(N\) số nguyên từ \(1\) đến \(4\), là các vùng cần đến theo thứ tự.

Dữ liệu ra

Nếu có lời giải, in \(N\) dòng theo thứ tự dịch chuyển. Mỗi dòng chứa hai mã đã gắn dấu, lần lượt cho trục hoành và trục tung. Phải in dấu + hoặc - trước mỗi mã, không có khoảng trắng giữa dấu và số; hai số có dấu được ngăn cách bằng một dấu cách. Có thể in bất kỳ lời giải hợp lệ nào.

Nếu không có lời giải, chỉ in số \(0\).

Chấm điểm

Có 25 bộ kiểm tra, mỗi bộ tương ứng 4 điểm trong thang điểm gốc 100. Một bộ kiểm tra chỉ được điểm khi hành trình đúng và chương trình chạy trong giới hạn thời gian; ngược lại được 0 điểm.

Ví dụ

4
7 5 6 1 3 2 4 8
4 1 2 1

+7 -1
-5 +2
-4 +3
+8 +6

4
2 5 4 1 7 8 6 3
4 2 2 1

+3 -2
-4 +5
-6 +1
+8 +7

Nguồn

Đề gốc IOI 2002. Tài liệu kỳ thi.