Cho số nguyên dương ~N~ (~1 \le N \le 100~) và phương trình bậc hai có dạng ~ax^2 + bx + c = 0~ (~a \ne 0~), trong đó ~a, b, c~ là hệ số, ~x~ là ẩn số (~x~ thuộc tập số thực).

Yêu cầu: Cho ~N~ bộ ba, mỗi bộ ba gồm 3 số nguyên ~a, b, c~ tương ứng là hệ số của phương trình bậc hai ~ax^2 + bx + c = 0~. Hãy đếm số lượng phương trình bậc hai có nghiệm.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~;
• ~N~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a, b, c~ (~-10^6 \le a, b, c \le 10^6~), mỗi số cách nhau bởi dấu cách.

Output

Xuất ra màn hình một số nguyên là số lượng phương trình bậc hai có nghiệm. Nếu không có phương trình nào thỏa mãn yêu cầu thì xuất ra số 0.

Sample Input 1

3
-5 3 2
9 3 8
1 -2 1

Sample Output 1

2

Có 3 phương trình:

• ~-5x^2 + 3x + 2 = 0~ có 2 nghiệm ~x_1 = 1~, ~x_2 = -0.4~.
• ~9x^2 + 3x + 8 = 0~ vô nghiệm.
• ~x^2 - 2x + 1 = 0~ có nghiệm ~x_1 = x_2 = 1~.

Vậy kết quả là 2.

Các em đã biết câu chuyện Alibaba và 40 tên cướp. Hôm nay, Alibaba lại vào hang của bọn cướp để lấy vàng. Trong hang có ~N~ (~1 \le N \le 10^5~) túi vàng, trong túi vàng thứ ~i~ (~1 \le i \le N~) có ~a_i~ đồng tiền vàng. Alibaba muốn lấy được số đồng tiền vàng tối đa có thể, đối với mỗi túi vàng Alibaba phải lấy hết số vàng trong túi hoặc không lấy túi đó. Tuy nhiên, lần này để ra khỏi hang, Thần giữ cửa yêu cầu Alibaba chỉ được lấy số lượng đồng tiền vàng là một số chẵn.

Yêu cầu: Tính tổng số đồng tiền vàng tối đa là số chẵn mà Alibaba có thể lấy được. Nếu Alibaba không lấy đồng tiền vàng nào ra khỏi hang coi như tổng số đồng tiền vàng Alibaba lấy là 0.

Input

• Dòng đầu tiên chứa một số nguyên dương ~N~ là số lượng túi vàng trong hang;
• Dòng tiếp theo chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ (~1 \le a_i \le 10^9, 1 \le i \le N~) lần lượt là số đồng tiền vàng trong mỗi túi, mỗi số cách nhau 1 khoảng trắng.

Output

Xuất ra màn hình một số nguyên duy nhất là tổng số đồng tiền vàng tối đa và là số chẵn mà Alibaba có thể lấy được.

Sample Input 1

4
1 2 3 7

Sample Output 1

12

Giải thích: Trong ví dụ thứ nhất, Alibaba lấy các túi vàng có số đồng tiền vàng tương ứng là ~2 + 3 + 7 = 12~ tối đa và là một số chẵn.

Sample Input 2

3
9999 9999 9999

Sample Output 2

19998

Giải thích: Ví dụ thứ hai, Alibaba lấy 2 túi trong 3 túi vàng, tổng số đồng tiền vàng là ~9999 + 9999 = 19998~ tối đa và là một số chẵn.

Subtasks

• Có 90% số test ứng với 90% số điểm thỏa mãn: ~a_1 + a_2 + ... + a_N~ là số chẵn;
• Có 10% số test còn lại ứng với 10% số điểm: không có ràng buộc gì thêm.

Một hệ thống máy tính hiện đang lưu trữ ~N~ tập tin, tập tin thứ ~i~ (~1 \le i \le N~) được đặt tên là ~S_i~. Nhận thấy rằng có nhiều tập tin không cần thiết, người ta sẽ xóa đi một số tập tin của hệ thống máy tính. Cụ thể, người ta đã thực hiện ~Q~ thao tác xóa tập tin. Mỗi thao tác được biểu thị bởi một kí tự, cho biết thao tác này xóa đi các tập tin có tên chứa ít nhất một kí tự đã cho. Tuy nhiên có những thao tác không xóa tập tin nào cả vì trong hệ thống máy tính không còn tập tin nào thỏa mãn yêu cầu cần xóa.

Yêu cầu: Sau mỗi thao tác xóa, tính số lượng tập tin còn lại trong hệ thống máy tính.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~Q~ (~1 \le N, Q \le 10^5~);
• ~N~ dòng tiếp theo, dòng thứ ~i~ (~1 \le i \le N~) chứa 1 xâu kí tự ~S_i~ độ dài không vượt quá 8 kí tự, chỉ gồm các kí tự chữ cái Latin in thường, tên của tập tin thứ ~i~;
• ~Q~ dòng tiếp theo, mỗi dòng gồm một kí tự chữ cái Latin in thường, mô tả một thao tác xóa.

Output

~Q~ dòng, dòng thứ ~k~ (~1 \le k \le Q~) chứa 1 số nguyên là số lượng tập tin còn lại trong hệ thống máy tính sau khi thực hiện thao tác xóa thứ ~k~.

Sample Input 1

3 3
shoes
split
rect
o
z
s

Sample Output 1

2
2
1

Sau thao tác xóa thứ nhất, các tập tin còn lại là: split, rect; thao tác xóa thứ hai không xóa đi tập tin nào; sau thao tác xóa thứ ba, chỉ còn lại một tập tin rect;

Sample Input 2

1 3
abc
a
a
a

Sample Output 2

0
0
0

Sau thao tác thứ nhất, còn lại 0 tập tin, sau thao tác xóa thứ hai, thứ ba cũng còn lại 0 tập tin.

Subtasks

• Có 70% số test ứng với 70% số điểm thỏa mãn: ~N, Q \le 100~;
• Có 30% số test còn lại ứng với 30% số điểm: không có ràng buộc gì thêm.

Cho trước số nguyên dương ~N~ và dãy số nguyên ~a_1, a_2, ..., a_N~. Một đoạn con ~a_L, a_{L+1}, ..., a_R~ (~1 \le L \le R \le N~) được gọi là đoạn con đẹp nếu ~L, R~ đều là số nguyên tố.

Số nguyên tố là số chỉ có hai ước phân biệt 1 và chính nó, ví dụ: 3, 5, 11,..., là số nguyên tố; 4, 6, 15,..., không phải là số nguyên tố. Ví dụ: ~N = 4~, dãy số ~\{2, -4, 5, 7\}~ có các đoạn con đẹp lần lượt là: ~\{a_2\} = \{-4\}~ vì có ~L = 2, R = 2~ đều là số nguyên tố; ~\{a_3\} = \{5\}~ vì có ~L = 3, R = 3~ đều là số nguyên tố, ~\{a_2, a_3\} = \{-4, 5\}~ vì có ~L = 2, R = 3~ đều là số nguyên tố.

Tổng giá trị của đoạn con đẹp được tính bằng: ~a_L + a_{L+1} + ... + a_R~.

Yêu cầu: Hãy tìm đoạn con đẹp có tổng giá trị lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~2 \le N \le 10^6~);
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ (~|a_i| \le 10^6, 1 \le i \le N~), mỗi số cách nhau 1 khoảng trắng.

Output

Xuất ra màn hình một số nguyên duy nhất là tổng giá trị lớn nhất của đoạn con đẹp tìm được.

Sample Input 1

6
9 5 -2 6 -1 1

Sample Output 1

8

~N = 6~, dãy ~\{9, 5, -2, 6, -1, 1\}~ có các đoạn con đẹp là: ~\{5\}~, ~\{-2\}~, ~\{-1\}~, ~\{5, -2\}~, ~\{-2, 6, -1\}~, ~\{5, -2, 6, -1\}~, đoạn con đẹp có tổng lớn nhất là 8.

Subtasks

• Có 40% số test ứng với 40% số điểm thỏa mãn: ~N \le 10^2~;
• Có 30% số test khác ứng với 30% số điểm thỏa mãn: ~N \le 3000~;
• Có 30% số test còn lại ứng với 30% số điểm thỏa mãn: ~N \le 10^6~.

Sau khi học lý thuyết ở trường, học sinh phải làm bài tập luyện tập. Thầy Minh đã xây dựng chương trình luyện tập trực tuyến trên Internet cho học sinh, thầy đã lên chương trình luyện tập cho ~N~ học sinh. Ban đầu, học sinh thứ ~i~ (~1 \le i \le N~) có kỹ năng làm bài tập là ~a_i~. Thầy Minh chuẩn bị ~M~ bài tập, bài thứ ~j~ (~1 \le j \le M~) có độ khó là ~b_j~. Thầy Minh chỉ định trình tự luyện tập các bài tập tùy thuộc vào kỹ năng làm bài tập ban đầu của từng học sinh và mỗi bài tập chỉ làm tối đa một lần để tránh nhàm chán. Để làm bài tập có độ khó ~x~, học sinh phải có kỹ năng làm bài tập không nhỏ hơn ~x~ và sau khi hoàn thành bài tập, kỹ năng làm bài tập của học sinh sẽ tăng thêm ~x~ đơn vị.

Để đánh giá tính hiệu quả của chương trình luyện tập, Thầy Minh cần biết kỹ năng làm bài tập cao nhất có thể của từng học sinh đạt được sau khi hoàn thành chương trình luyện tập.

Yêu cầu: Biết kỹ năng làm bài tập ban đầu của ~N~ học sinh và độ khó của ~M~ bài tập. Hãy tính kỹ năng làm bài tập cao nhất của từng học sinh đạt được sau khi hoàn thành chương trình luyện tập.

Input

• Dòng thứ nhất ghi 2 số nguyên dương ~N~ và ~M~ (~1 \le N, M \le 5 \times 10^5~) tương ứng là số lượng học sinh và số lượng bài tập;
• Dòng thứ hai ghi ~N~ số nguyên ~a_1, a_2, ..., a_N~ (~1 \le a_i \le 10^9, 1 \le i \le N~) tương ứng là kỹ năng làm bài tập ban đầu của từng học sinh;
• Dòng thứ ba ghi ~M~ số nguyên ~b_1, b_2, ..., b_M~ (~1 \le b_j \le 10^9, 1 \le j \le M~) tương ứng là độ khó của từng bài tập.
• Các số trên một dòng cách nhau một khoảng trắng.

Output

Xuất ra màn hình một dòng duy nhất chứa ~N~ số nguyên tương ứng là kỹ năng làm bài tập cao nhất của từng học sinh sau khi hoàn thành chương trình luyện tập, mỗi số cách nhau 1 khoảng trắng.

Sample Input 1

5 4
4 6 1 2 9
7 3 1 2 15

Sample Output 1

6 30 1 4 64

• Học sinh thứ nhất chỉ làm được bài tập số 3 được tăng kỹ năng làm bài tập ~4 + 2 = 6~.
• Học sinh thứ 2 lần lượt làm các bài tập số 3 được tăng kỹ năng làm bài tập ~6 + 2 = 8~, bài tập số 1 được tăng kỹ năng làm bài tập ~8 + 7 = 15~ và số 4 được tăng ~15 + 15 = 30~.
• Học sinh thứ 3 không làm được bài tập nào, kỹ năng làm bài tập là 1.
• Học sinh thứ 4 làm bài tập số 3 kỹ năng làm bài tập được tăng ~2 + 2 = 4~.
• Học sinh thứ 5 tương tự lần lượt làm các bài tập số 3, số 1, số 4 và số 2, kỹ năng làm bài tập là 64.

Subtasks

• Có 40% số test ứng với 40% số điểm thỏa mãn: ~M, N \le 10^3~;
• Có 20% số test khác ứng với 20% số điểm thỏa mãn: ~M, N \le 5 \cdot 10^4~;
• Có 40% số test còn lại ứng với 40% số điểm: không có ràng buộc gì thêm.