Gà hay trứng, cái gì có trước? Sống một trăm năm thành triệu phú hay sống nghèo khổ bảy ngày? Làm thế nào để trở thành đại kiện tướng cờ vua? Làm thế nào để nâng rèm? Làm thế nào để vượt qua kỳ thi cuối kỳ? Làm thế nào để huấn luyện một con rồng? Đây là những câu hỏi thú vị mà chúng tôi chỉ có thể suy ngẫm sau cuộc thi, nhưng bây giờ chúng tôi đưa ra một vấn đề khoa học máy tính kém thú vị hơn.

Bạn được cấp hai tập hợp số ~A~ và ~B~ có kích thước ~N~. Trong một bước, bạn có thể chọn một phần tử tùy ý từ bộ ~A~ và thay đổi một chữ số (bit) tùy ý trong biểu diễn nhị phân của nó. Số kết quả không được là phần tử của tập ~A~ ngay trước khi thay đổi.

Ví dụ, số ~5~ trong nhị phân là ~0101_2~. Trong một bước, nó có thể thành ~13 = 1101_2, 1 = 0001_2, 7 = 0111_2~ hoặc ~4 = 0100_2~ nếu chúng ta đổi bit thứ ~4~, ~3~, ~2~ hay ~1~.

Xác định chuỗi các bước để tập hợp ~A~ bằng tập hợp ~B~. Các tập hợp bằng nhau nếu chúng có cùng kích thước và không có phần tử nào trong tập hợp ~A~ không thuộc tập hợp ~B~.

Lưu ý: Số lần thực hiện không nhất thiết phải tối thiểu nhưng phải đáp ứng các ràng buộc của nhiệm vụ.

Input

• Dòng đầu tiên chứa số nguyên ~N~ (~1 \leq N \leq 2^{15}~) là kích thước của các tập ~A~ và ~B~.
• Dòng thứ hai chứa ~N~ số nguyên đôi một phân biệt ~a_i~ (~0 \leq a_i < 2^{15}~) là các phần tử của tập ~A~.
• Dòng thứ hai chứa ~N~ số nguyên đôi một phân biệt ~b_i~ (~0 \leq b_i < 2^{15}~) là các phần tử của tập ~B~.

Output

• Dòng đầu tiên, đưa ra số bước.
• Những dòng tiếp theo, đưa ra các số nguyên ~x~ và ~y~ (~0 \leq x, y < 2^{15}~) - ta đổi số ~x~ trong tập ~A~ thành số ~y~. Số ~x~ và ~y~ phải khác nhau đúng một bit, và phải đảm bảo ~x \in A~ và ~y \notin A~ ở thời điểm thực hiện.

Scoring

Số bước bạn được phép thực hiện không vượt quá ~2^{19}~. Có thể chứng minh rằng luôn tồn tại lời giải với giới hạn đã cho.

1. ~a_i, b_i \leq 2^{14}~ (10 điểm)

2. ~N \leq 7~ (15 điểm)

3. ~N \leq 2^7~ (30 điểm)

4. Không có ràng buộc gì thêm (15 điểm)

Sample Input 1

3
0 1 2
1 2 3

Sample Output 1

2
1 3
0 1

Sample Input 2

3
4 8 31
0 4 8

Sample Output 2

5
31 30
30 28
28 24
24 16
16 0

Sample Input 3

5
0 1 2 4 5
7 6 5 3 2

Sample Output 3

9
1 3
3 7
0 1
1 0
2 6
0 2
7 3
5 7
4 5