cho hai dãy có cùng \(n\) số nguyên dương \(a_1,a_2,...,a_n\) và \(b_1,b_2,...,b_n\).

shiba muốn tạo ra một dãy cũng có \(n\) số nguyên dương \(c_1,c_2,...,c_n\) thỏa mãn rằng \(c_k\) \((1 \le k \le n)\) là giá trị lớn nhất của \(a_i \times b_j\) với mọi \(1 \le i \le j \le k\). Hay nói một cách khác, shiba cần tạo ra một dãy thỏa mãn rằng \(c_k = max(a_i \times b_j)\) với mọi \((1 \le i \le j \le k)\).

Yêu cầu: Bạn hãy giúp shiba tạo và in ra dãy \(c\) thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n \le 10^6)\).
• Dòng tiếp theo chứa dãy \(a_1,a_2,...,a_n\) \((1 \le a_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.
• Dòng cuối cùng chứa dãy \(b_1,b_2,...,b_n\) \((1 \le b_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.

Output

• Gồm \(n\) dòng, dòng thứ \(i\) \((1 \le i \le n)\) in ra số \(c_i\) thỏa mãn điều kiện (\(i\) theo thứ tự tăng dần \(1,2,...,n\)).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): Có \(n \le 2 \times 10^5\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
3 2 20
1 4 1

3
12
20