Cho số nguyên dương ~c~ có biểu diễn nhị phân là ~1~ xâu có độ dài ~N-1~ chỉ gồm ký tự ~0~ và ~1~. Bạn cần tìm ~2~ số ~a~ và ~b~ thoả mãn điều kiện sau :

• ~a-b = c~ và ~a~ ~\&~ ~b = 0~ (với ~\&~ thể hiện toán tử AND).
• Số bit ~1~ trong biểu diễn nhị phân của ~a~ và ~b~ là bằng nhau.
• ~a, b < 2^N~.

Input

• Dòng đầu tiên gồm một số ~N~ thể hiện độ dài của xâu nhị phân ~(2 \le N \le 2 \times 10^5)~.
• Dòng tiếp theo gồm ~N-1~ ký tự ~0~ hoặc ~1~ lần lượt từ trái sang phải là bit thứ ~N-2, \dots, 1, 0~ trong biểu diễn nhị phân của ~c~ .

Output

In ra ~2~ xâu nhị phân độ dài ~N~ trên ~2~ dòng :

• Dòng đầu là biểu diễn nhị phân của số ~a~.
• Dòng thứ hai là biểu diễn nhị phân của số ~b~.

Nếu có nhiều cặp số ~(a, b)~ hợp lệ thì hãy chọn một cặp bất kỳ để in ra.

Subtask

• ~30\%~ số test có ~n \leq 15~.
• ~70\%~ số test còn lại không có điều kiện gì thêm.

Sample Input

11
0000000001

Sample Output

00000000010
00000000001

Note

Khi chuyển từ hệ nhị phân sang hệ thập phân ta có :

• ~a = 00000000010_2 = 2~
• ~b = 00000000001_2 = 1~
• ~c = 0000000001_2 = 1~