Trong đêm Giao Thừa khi trăng tròn tỏa sáng và mọi người tin rằng vận mệnh có thể được thay đổi, quốc vương Thiên Ban đã mời đến một pháp sư Quýt để mở ra một nghi lễ cổ xưa mang tên Phép Đổi Vận.

Nghi lễ này sử dụng hai dãy số linh thiêng là ~a~ và ~b~, mỗi dãy gồm ~n~ phần tử, được đánh số từ ~1~ đến ~n~. Mỗi con số trong dãy tượng trưng cho một luồng vận khí khác nhau trong năm mới. Để hoàn thành nghi lễ, pháp sư Quýt cần tạo ra một dãy mới ~c~, trong đó mỗi phần tử ~c_i~ thể hiện sức mạnh vận mệnh tại vị trí ~i~.

Cụ thể, giá trị ~c_i~ được xác định như sau: ~c_i = \sum a_j \times b_k~ với tất cả các cặp chỉ số ~(j, k)~ thỏa mãn: ~j | k = i~ (tức là ~j~ và ~k~ là or bit của chúng lại bằng ~i~).

Do dịp tết cận kề nên ai cũng nôn nóng đi chơi nên bạn hãy trợ giúp pháp sư tính toán toàn bộ dãy ~c~ để hoàn tất nghi lễ Đổi Vận Đầu Năm cho vương quốc của Thiên Ban nhé.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ với ~(1 \leq n \leq 10^5)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ với (~1\leq a_i \leq 10^5~)
• Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \dots, b_n~ với (~1\leq b_i \leq 10^5~)

Output

In ra ~n~ số nguyên, trong đó số thứ ~i~ là giá trị của ~c_i~.

Subtask

Sample Input

4
2 0 2 5
2 0 2 6

Sample Output

4 0 12 30