Cho một dãy gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~.

Hãy in ra số lượng phần tử trong dãy là số chính phương. Một số nguyên dương ~x~ được gọi là số chính phương nếu tồn tại một số nguyên dương ~k~ sao cho ~k^2 = x~.

Input

Dòng đầu tiên chứa một số nguyên dương ~N~ ~(1 \le N \le 10^5)~.

Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9, 1 \le i \le N)~.

Output

In ra số lượng số chính phương trong dãy.

Scoring

Sample Input 1

5
1 4 7 16 10

Sample Output 1

3

Notes

Có 3 số chính phương: ~1 = 1^2, 4 = 2^2, 16 = 4^2~.

Bạn có ~N~ lá bài đặt thành một hàng, lá bài thứ ~i~ có giá trị ~a_i~. Bạn chơi trò chơi sau:

• Trong mỗi lượt, lấy hai lá bài ở đầu hàng bên trái ra so sánh giá trị.

• Nếu một lá bài có giá trị lớn hơn, lá lớn hơn này được đặt lại vào đầu hàng, lá nhỏ hơn bị loại bỏ.

• Nếu hai lá bài có giá trị bằng nhau, cả hai đều bị loại bỏ.

Lặp lại cho đến khi còn tối đa 1 lá bài.

Hãy in ra giá trị của lá bài còn lại cuối cùng. Nếu không còn lá bài nào, in ra 0.

Input

Dòng đầu tiên chứa một số nguyên dương ~N~ ~(1 \le N \le 10^6)~.

Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9, 1 \le i \le N)~.

Output

In ra một số nguyên duy nhất: giá trị lá bài còn lại, hoặc 0 nếu không còn lá nào.

Scoring

Sample Input 1

5
3 1 4 1 5

Sample Output 1

5

Sample Input 2

4
2 2 3 3

Sample Output 2

0

Notes

Ví dụ 1:

• Lượt 1: so 3 và 1 ~\rightarrow~ 3 lớn hơn, hàng: ~[3, 4, 1, 5]~

• Lượt 2: so 3 và 4 ~\rightarrow~ 4 lớn hơn, hàng: ~[4, 1, 5]~

• Lượt 3: so 4 và 1 ~\rightarrow~ 4 lớn hơn, hàng: ~[4, 5]~

• Lượt 4: so 4 và 5 ~\rightarrow~ 5 lớn hơn, hàng: ~[5]~

• Còn lại: 5.

Ví dụ 2:

• Lượt 1: so 2 và 2 ~\rightarrow~ bằng, loại cả hai, hàng: ~[3, 3]~

• Lượt 2: so 3 và 3 ~\rightarrow~ bằng, loại cả hai, hàng: ~[]~

• Không còn lá nào ~\rightarrow~ 0.

Bạn cần lát đầy dải ô vuông kích thước ~1 \times N~ bằng các viên gạch có độ dài 1, 2, hoặc 3.

• Gạch có độ dài 1 có ~a~ màu khác nhau.

• Gạch có độ dài 2 có ~b~ màu khác nhau.

• Gạch có độ dài 3 có ~c~ màu khác nhau.

Hai cách lát được coi là khác nhau nếu tồn tại ít nhất một ô vuông kích thước ~1 \times 1~ mà viên gạch phủ trên đó khác nhau về độ dài hoặc màu sắc.

Hãy đếm số cách lát đầy dải ~1 \times N~, kết quả lấy dư cho ~998244853~.

Input

Dòng duy nhất chứa bốn số nguyên dương ~N, a, b, c~ ~(1 \le N \le 10^6, 1 \le a, b, c \le 10^9)~.

Output

In ra một số nguyên duy nhất: số cách lát dải, lấy dư cho ~998244853~.

Scoring

Sample Input 1

3 2 1 1

Sample Output 1

13

Notes

Ba gạch độ dài 1: ~2^3 = 8~ cách.

Gạch độ dài 1 + gạch độ dài 2: ~2 \times 1 = 2~ cách.

Gạch độ dài 2 + gạch độ dài 1: ~1 \times 2 = 2~ cách.

Một gạch độ dài 3: 1 cách.

Tổng = ~8 + 2 + 2 + 1 = 13~.

Trường H tổ chức chương trình tuyển chọn học sinh cho đội tuyển chuyên. Có 2026 chuyên đề kiến thức được đánh số thứ tự từ 1 đến 2026. Hội đồng chuyên môn xác định ~M~ chuyên đề trọng tâm, trong đó ~K~ chuyên đề đầu tiên được xem là các chuyên đề cốt lõi quan trọng nhất.

Mỗi học sinh đăng ký đúng ~K~ chuyên đề mà mình tự tin nhất (các chuyên đề đôi một khác nhau). Dựa trên mức độ phù hợp giữa lựa chọn của học sinh và danh sách chuyên đề trọng tâm, hội đồng phân loại học sinh theo các nhóm năng lực sau (ưu tiên nhóm có số thứ tự nhỏ nhất mà học sinh đạt được):

• Nhóm năng lực 1: Toàn bộ ~K~ chuyên đề đăng ký đều nằm trong ~K~ chuyên đề cốt lõi.

• Nhóm năng lực 2: Toàn bộ ~K~ chuyên đề đăng ký đều nằm trong ~M~ chuyên đề trọng tâm.

• Nhóm năng lực 3: Có thể chọn ra ~K - 1~ chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc ~K - 1~ chuyên đề cốt lõi đầu tiên.

• Nhóm năng lực 4: Có thể chọn ra ~K - 1~ chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc ~K~ chuyên đề cốt lõi.

• Nhóm năng lực 5: Có thể chọn ra ~K - 1~ chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc ~M~ chuyên đề trọng tâm.

• Nhóm năng lực 6: Có thể chọn ra ~K - 2~ chuyên đề (không kể thứ tự) trong danh sách đăng ký sao cho tất cả đều thuộc ~M~ chuyên đề trọng tâm.

Có ~J~ học sinh tham gia đăng ký. Mỗi học sinh được xếp vào nhóm năng lực có số thứ tự nhỏ nhất mà học sinh đó thỏa mãn điều kiện.

Yêu cầu: Viết một chương trình để xác định:

• Nhiệm vụ 1: Số lượng học sinh được xếp vào nhóm năng lực ~C~ cụ thể. Các nhóm năng lực được đánh số ~1, 2, \dots, 6, 7~. Nhóm năng lực 7 dành cho những học sinh không thuộc nhóm nào ở trên.

• Nhiệm vụ 2: Các chuyên đề nhiều học sinh đăng ký nhất, được viết theo thứ tự tăng dần nếu có nhiều hơn 1 chuyên đề thỏa mãn.

Input

Dòng đầu tiên ghi mã số nhiệm vụ (1 hoặc 2).

Dòng thứ hai ghi 3 số ~M, K, C~ ~(1 \le M \le 2026, 5 \le K \le M, 1 \le C \le 7)~.

Dòng thứ ba ghi số thứ tự ~M~ chuyên đề trọng tâm, theo thứ tự ưu tiên (cốt lõi trước, mở rộng sau).

Dòng thứ tư ghi một số tự nhiên ~J~ ~(1 \le J \le 5 \times 10^4)~, biểu thị số lượng học sinh, và mỗi dòng trong số ~J~ dòng tiếp theo ghi ~K~ số tự nhiên, biểu thị các chuyên đề mà học sinh đó đăng ký.

Output

Đối với nhiệm vụ 1, in ra số lượng học sinh thuộc nhóm năng lực ~C~.

Đối với nhiệm vụ 2, in ra số thứ tự các chuyên đề được nhiều học sinh đăng ký nhất, viết theo thứ tự tăng dần.

Scoring

Sample Input 1

1
6 5 1
11 12 13 14 15 16
1
15 14 13 12 11

Sample Output 1

1

Notes

Nhiệm vụ 1. Hội đồng xác định 6 chuyên đề trọng tâm theo thứ tự là 11,12,13,14,15,16. Mỗi học sinh đăng ký 5 chuyên đề. Có một học sinh duy nhất. Học sinh này đăng ký các chuyên đề 15,14,13,12,11. Học sinh được xếp vào Nhóm 1 vì đã đăng ký đúng 5 chuyên đề cốt lõi đầu tiên.

Con mã (ô S) tấn công các ô vuông (dấu x) trên bàn cờ như hình dưới. Có một bàn cờ kích thước ~4 \times n~, với 4 hàng và ~n~ cột, trong đó ~1 \le n \le 100~. Gọi ~Z~ là tập các ô trên bàn cờ. Các hàng được đánh số thứ tự từ trên xuống dưới, từ 1 đến 4, các cột được đánh số thứ tự từ trái qua phải, từ 1 đến ~n~. Quân mã chỉ có thể được đặt trên các ô không thuộc ~Z~ và hai quân bất kỳ không được ăn nhau. Giả định trong mỗi cột có nhiều nhất một ô thuộc ~Z~. Vì vậy, tập ~Z~ có thể được mô tả bằng chuỗi ~k_1, k_2, \dots, k_n~ trong đó ~k_i~ thuộc ~\{0, 1, 2, 3, 4\}~. Nếu ~k_i = 0~ thì cột ~i~ không có ô nào thuộc ~Z~, ngược lại, ô ở hàng ~k_i~, cột ~i~ thuộc ~Z~.

Yêu cầu: Hãy tính số lượng tối đa của các quân mã ~M~, có thể đặt trên bàn cờ theo quy tắc trên và số lượng ~L~ cách sắp xếp có thể có của ~M~ quân mã trên bàn cờ này.

Input

Dòng đầu tiên là số nguyên dương ~n~ ~(1 \le n \le 100)~.

Mỗi dòng trong ~n~ dòng sau ghi một số 0, 1, 2, 3 hoặc 4.

Output

In ra hai số ~M~ và ~L~.

Scoring

Sample Input 1

2
1
0

Sample Output 1

4 8

Notes

Xếp được tối đa 4 con mã và có 8 cách bố trí hợp lệ như hình trên.