Bài tập

Cho một dãy số gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^5, 1 \leq i \leq n \leq 10^5\)).

**Yêu cầu:** Tìm số $a_i$ có số ước nguyên dương nhiều nhất, nếu có nhiều số như vậy thì in ra số xuất hiện đầu tiên trong các số đó.

Input

Dữ liệu: Từ file UOCSO.INP gồm:

• Dòng đầu là số nguyên dương \(n\);
• Dòng tiếp theo là \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Mỗi số cách nhau một khoảng trắng.

Output

Kết quả: Ghi ra file UOCSO.OUT một số nguyên dương duy nhất là kết quả tìm được.

Example

5
10 6 8 7 12

12

4
10 6 8 7

10

Scoring

Ràng buộc:

• Có 80% số điểm ứng với \((1 \leq n \leq 10^5; 1 \leq a_i \leq 10^5)\);
• 20% số điểm còn lại không có ràng buộc gì thêm.

Trong một bài kiểm tra về Thuật toán Đệ quy (Recursion), giáo sư yêu cầu bạn sử dụng kỹ thuật Quay lui (Backtracking) để liệt kê tất cả các tập con của một tập hợp \(S\) cho trước.

Tập hợp \(S\) được định nghĩa là \(S = \{1, 2, 3, \ldots, N\}\).

Nhiệm vụ của bạn là viết một chương trình liệt kê tất cả \(2^N\) tập con của tập \(S\) bằng cách mô phỏng quá trình xây dựng tập con theo từng phần tử.

Input

• Dòng đầu tiên và duy nhất chứa số nguyên \(N\) (\(1 \le N \le 15\)) --- kích thước của tập hợp \(S\).

Output

In ra tất cả các tập con của \(S\).

• Mỗi tập con được in trên một dòng riêng biệt.
• Các phần tử trong mỗi tập con được in ra theo thứ tự tăng dần, cách nhau bởi một dấu cách.
• Tập rỗng được biểu thị bằng \t\.

Example

3

{}
3
2
2 3
1
1 3
1 2
1 2 3

In ra các số từ 1 đến 5 trên cùng một dòng, cách nhau bởi dấu cách.

Input

Không có dữ liệu đầu vào.

Output

Một dòng chứa các số 1 2 3 4 5.

Example

Nothing

1 2 3 4 5

In kết quả của các phép toán sau:

• \(10 + 5\)

• \(10 - 5\)

• \(10 * 5\)

• \(10 / 5\)

Input

Không có dữ liệu đầu vào.

Output

Bốn dòng chứa kết quả của các phép toán.

Example

nothing

10 + 5 = 15
10 - 5 = 5
10 * 5 = 50
10 / 5 = 2