Cho bốn số nguyên dương ~a, b, c, d~. Biết rằng ~a, b~ là độ dài 2 cạnh của hình chữ nhật thứ nhất; ~c, d~ là độ dài 2 cạnh của hình chữ nhật thứ hai.

Yêu cầu: Hãy tính diện tích của hai hình chữ nhật và đưa ra diện tích lớn nhất.

Input

Gồm bốn số nguyên dương ~a, b, c, d~ (~a, b, c, d \le 10^9~).

Output

Là diện tích lớn nhất tìm được.

Sample Input 1

2 4 3 6

Sample Output 1

18

Số đặc biệt là số chia hết cho tích các chữ số của nó. Ví dụ, số 5 là số đặc biệt vì 5 chia hết cho 5; số 12 là số đặc biệt vì 12 chia hết cho 2 (~1 \times 2 = 2~); số 102 không phải là số đặc biệt vì tích các chữ số của nó bằng 0 (~1 \times 0 \times 2 = 0~).

Cho dãy số ~A~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ và 2 số nguyên dương ~l, r~.

Yêu cầu: Hãy liệt kê các số đặc biệt theo đúng thứ tự xuất hiện trong đoạn ~a_l, a_{l+1}, ..., a_r~.

Input

• Dòng đầu theo thứ tự gồm ba số nguyên dương ~n, l, r~ (~1 \le n \le 10^5~; ~1 \le l \le r \le n~);
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~; ~1 \le i \le n~).

Output

Gồm duy nhất một dòng ghi các số đặc biệt tìm được, các số cách nhau một dấu cách. Nếu không tìm được số đặc biệt nào thì in ra -1.

Sample Input 1

8 2 5
2 12 15 20 5 28 36 39

Sample Output 1

12 15 5

Trong một cuộc thi lập trình Robot, đội của An nhận được xâu tín hiệu ~S~ có độ dài không quá ~3 \times 10^6~ kí tự, chỉ gồm các chữ cái thường và chữ số gửi về thông qua đường truyền internet. An cần tách các số từ đoạn tín hiệu này và đếm số lượng số nguyên tố trong các số đã được tách. Biết rằng, mỗi số trong xâu ~S~ là một dãy các kí tự chữ số liên tiếp mà có các kí tự liền kề trước hoặc sau (nếu có) là kí tự chữ cái. Các số trong xâu ~S~ không vượt quá ~10^6~. Yêu cầu: Hãy viết chương trình đếm số lượng số nguyên tố được tách ra từ xâu ~S~.

Input

Gồm một xâu ~S~ chỉ chứa các kí tự chữ cái thường và chữ số.

Output

Ghi ra số lượng số nguyên tố trong các số được tách ra.

Sample Input 1

nb05hsg21bc3956tin19

Sample Output 1

2

Các số được tách từ xâu ~S~ gồm 4 số ~{5; 21; 3956; 19}~ có 2 số nguyên tố là 5 và 19.

Sample Input 2

nb1hsg09tin68thcs135

Sample Output 2

0

Trong xâu ~S~ không có số nguyên tố nào.

Subtasks

• Subtask 1: 25% số test tất cả các số trong xâu ~S~ đều có một chữ số;
• Subtask 2: 50% số test có độ dài của xâu ~S~ không vượt quá 1000 kí tự;
• Subtask 3: 25% số test không có ràng buộc gì thêm.

Cho dãy số ~A~ gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~, có thể chia dãy số này thành các đoạn liên tiếp sao cho tổng các số trong mỗi đoạn là lũy thừa cơ số 2. Ví dụ: dãy gồm 6 số ~A = \{5, 3, 1, 1, 1, 3\}~ có 2 cách chia thoả mãn:

• Cách 1: Chia 3 đoạn ~\{5, 3\}; \{1, 1\}; \{1, 3\}~ có tổng lần lượt là ~8 = 2^3; 2 = 2^1, 4 = 2^2~.
• Cách 2: Chia 4 đoạn ~\{5, 3\}; \{1\}; \{1\}; \{1, 3\}~ có tổng lần lượt là ~8 = 2^3; 1 = 2^0; 1 = 2^0, 4 = 2^2~.

Yêu cầu: Em hãy viết chương trình tìm cách chia dãy ~A~ trên thành các đoạn con liên tiếp sao cho số lượng đoạn con là ít nhất và tổng các số trong mỗi đoạn là lũy thừa cơ số 2?

Input

• Dòng 1 là số nguyên dương ~n~ (~1 \le n \le 10^5~);
• Dòng 2 gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~0 \le a_i \le 2 \times 10^4~; ~1 \le i \le n~).

Output

Một số nguyên là số đoạn ít nhất chia được. Nếu không chia được thì in ra -1.

Sample Input 1

6
5 3 1 1 1 3

Sample Output 1

3

Subtasks

Một số tự nhiên được gọi là "Số gần chính phương" nếu số đó thỏa mãn đồng thời ba điều kiện sau:

• Có từ 3 chữ số trở lên.
• Chữ số ở hàng cao nhất (hàng đầu tiên bên trái) là một số chính phương.
• Tổng của hai chữ số cuối cùng (hàng chục và hàng đơn vị) là một số chính phương.

Yêu cầu: Cho số nguyên dương ~M~, hãy đếm xem có bao nhiêu số "Số gần chính phương" trong đoạn từ 1 đến ~M~.

Input

Gồm một số nguyên dương ~M~.

Output

Gồm một số nguyên duy nhất là số lượng số "Số gần chính phương" tìm được.

Sample Input 1

105

Sample Output 1

3

Giải thích: Có 3 số từ 1 đến 105 là số gần chính phương gồm: 100; 101; 104.

Subtasks

• Subtask 1: 50% số test có ~100 \le M \le 999~;
• Subtask 2: 25% số test ~M~ có ~1000 \le M \le 10^6~;
• Subtask 3: 25% số test ~M~ có dạng ~10^K~ với ~6 < K < 18~.