Thế vận hội sắp được tổ chức tại vương quốc JOI. Để chào đón các vận động viên từ khắp nơi trên thế giới, những tòa nhà dọc đường từ sân bay đến nơi lưu trú sẽ được trang trí. Có \(2N\) tòa nhà, được đánh số từ \(1\) đến \(2N\) theo thứ tự từ phía sân bay.

Tổng thống K phụ trách dự án trang trí. Ông kêu gọi người dân đề xuất các phương án và cuối cùng chọn ra hai phương án \(A\) và \(B\). Theo phương án \(A\), mức độ lộng lẫy của tòa nhà thứ \(i\) (\(1 \le i \le 2N\)) là \(A_i\); theo phương án \(B\), mức độ lộng lẫy của tòa nhà đó là \(B_i\).

Cả hai phương án đều rất tốt nên ông khó lựa chọn. Ông quyết định chọn một trong hai phương án cho từng tòa nhà. Để bảo đảm công bằng, đúng \(N\) tòa nhà phải dùng phương án \(A\) và \(N\) tòa nhà còn lại phải dùng phương án \(B\). Ngoài ra, để các vận động viên càng thêm hào hứng trên đường đến nơi lưu trú, mức độ lộng lẫy phải không giảm: gọi \(C_i\) là mức độ lộng lẫy của tòa nhà thứ \(i\), cần có \(C_i \le C_{i+1}\) với mọi \(1 \le i \le 2N-1\).

Hãy viết chương trình nhận số tòa nhà và mức độ lộng lẫy của từng tòa nhà trong mỗi phương án, xác định có thể chọn các phương án thỏa mãn yêu cầu hay không, và in ra một cách chọn nếu có.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N
A_1 A_2 ... A_{2N}
B_1 B_2 ... B_{2N}

Dữ liệu ra

Nếu không có cách chọn thỏa mãn yêu cầu, in ra -1.

Ngược lại, in ra xâu \(S\) có độ dài \(2N\) mô tả cách chọn. Ký tự thứ \(i\) (\(1 \le i \le 2N\)) của \(S\) là A nếu tòa nhà thứ \(i\) dùng phương án \(A\), và là B nếu dùng phương án \(B\). Nếu có nhiều cách chọn hợp lệ, có thể in ra một cách bất kỳ.

Ràng buộc

• \(1 \le N \le 500000\).
• \(1 \le A_i \le 10^9\) với mọi \(1 \le i \le 2N\).
• \(1 \le B_i \le 10^9\) với mọi \(1 \le i \le 2N\).

Phân nhóm

Các ràng buộc chung ở trên áp dụng cho mọi nhóm. Các ràng buộc bổ sung và số điểm của từng nhóm như sau:

1. \(11\) điểm: \(N \le 2000\).
2. \(89\) điểm: Không có ràng buộc bổ sung.

Ví dụ

3
2 5 4 9 15 11
6 7 6 8 12 14

AABABB

2
1 4 10 20
3 5 8 13

BBAA

2
3 4 5 6
10 9 8 7

-1

6
25 18 40 37 29 95 41 53 39 69 61 90
14 18 22 28 18 30 32 32 63 58 71 78

BABBABAABABA

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, kỳ trại huấn luyện mùa xuân JOI 2019/2020, ngày thi thứ nhất (20/03/2020). Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.