Số học sinh trong phòng học 1A và 1B lần lượt là ~a~ và ~b~ (~1 \le a, b \le 50~). Có 2 loại bàn học, loại thứ nhất mỗi bàn học ngồi được ~x~ học sinh và loại thứ hai mỗi bàn ngồi được ~y~ học sinh (~1 \le x, y \le 4~). Thầy Minh muốn chọn các loại bàn xếp vào hai phòng thỏa mãn các điều kiện:

• Trong mỗi phòng học chỉ được xếp cùng một loại bàn và số chỗ ngồi vừa đủ với số học sinh (không có thiếu hoặc thừa). Cả hai phòng có thể cùng sử dụng một loại bàn giống nhau.
• Nếu có nhiều cách xếp thỏa mãn thì chọn cách xếp có tổng số bàn ít nhất.

Yêu cầu: Em hãy giúp thầy Minh tính tổng số bàn sử dụng biết rằng luôn tồn tại cách xếp thỏa mãn.

Input

Gồm bốn số nguyên dương lần lượt ~a, b, x, y~.

Output

Ghi ra tổng số bàn ít nhất cần sử dụng cho cả hai phòng.

Sample Input 1

32 40 4 4

Sample Output 1

18

Sample Input 2

30 40 2 1

Sample Output 2

35

Ràng buộc

• Có 40% số điểm: ~x = y~.
• Có 30% số điểm: ~x = 2~ và ~y = 1~.
• Có 30% số điểm còn lại không có ràng buộc gì thêm.

Để phục hồi mật thư ~R~ từ một xâu đã được mã hóa ~S~, người chơi cần thực hiện:

• Ghép các chữ cái in hoa trong xâu ~S~ theo đúng thứ tự xuất hiện của chúng tạo thành xâu ~X~;
• Tính tổng các số nguyên trong xâu ~S~ rồi ghép vào cuối xâu ~X~ để tạo thành xâu ~R~. Nếu trong ~S~ không có số nguyên nào thì ~R = X~.

Ví dụ: ~S = a8bTxb6IN11k~ thì xâu ~X = TIN~ và tổng các số trong ~S~ là ~8 + 6 + 11 = 25~ nên mật thư ~R = TIN25~.

Yêu cầu: Tìm mật thư ~R~ từ xâu mã hóa ~S~ có ~n~ ký tự.

Input

• Dòng đầu ghi số nguyên dương ~n~ (~1 \le n \le 10^5~).
• Dòng thứ hai ghi ~n~ ký tự của xâu ~S~ gồm chữ số và các chữ cái tiếng Anh.

Output

Xâu mật thư ~R~.

Sample Input 1

5
HcOzc

Sample Output 1

HOC

Sample Input 2

12
a8bTxb6IN11k

Sample Output 2

TIN25

Ràng buộc

• Có 40% số điểm: xâu ~S~ chỉ gồm các chữ cái và ~n \le 200~.
• Có 30% số điểm: các số nguyên trong xâu ~S~ chỉ có một chữ số và ~n \le 200~.
• Có 30% số điểm còn lại: các số nguyên trong ~S~ có giá trị không vượt quá ~10^3~.

Khu rừng có ~N~ cây gỗ quý với lượng gỗ dự kiến khai thác được lần lượt là ~v_1, v_2, ..., v_N~. Có ~P~ phương án khai thác được đưa ra, phương án thứ ~i~ (~1 \le i \le P~) đề xuất khai thác tất cả các cây có lượng gỗ từ ~k_i~ trở lên (~1 \le k_i \le 10^6, 1 \le i \le P~).

Yêu cầu: Em hãy giúp ban quản lý rừng xác định tổng lượng gỗ khai thác được của mỗi phương án.

Input

• Dòng đầu ghi số nguyên dương ~N~ (~1 < N \le 10^6~).
• Dòng thứ hai ghi ~N~ số nguyên ~v_1, v_2, ..., v_N~ (~1 \le v_j \le 10^6, 1 \le j \le N~).
• Dòng thứ ba ghi số nguyên dương ~P~ (~1 \le P \le 10^5~).
• Dòng cuối cùng ghi ~P~ số nguyên ~k_1, k_2, ..., k_P~.

Output

Ghi ra ~P~ dòng, mỗi dòng ghi lần lượt tổng lượng gỗ khai thác được tương ứng của từng phương án.

Sample Input 1

5
1 2 3 4 5
1
4

Sample Output 1

9

Sample Input 2

5
1 10 4 5 2
2
4 5

Sample Output 2

19
15

Ràng buộc

• Có 40% số điểm: ~P = 1~.
• Có 30% số điểm: ~2 \le N, P \le 1000~.
• Có 30% số điểm còn lại không có ràng buộc gì thêm.

Số nguyên dương ~N~ được gọi là số đẹp nếu tích các số từ 1 đến ~N~ chia hết cho tổng các số từ 1 đến ~N~. Ví dụ 3, 7, 8 là những số đẹp.

Yêu cầu: Kiểm tra số nguyên ~N~ có phải là số đẹp hay không?

Input

• Dòng đầu ghi số nguyên dương ~T~ (~1 \le T \le 10~) là số lượng test cần kiểm tra.
• ~T~ dòng tiếp theo, mỗi dòng ghi một số nguyên dương ~N~ (~1 \le N \le 10^9~).

Output

Ghi ra ~T~ dòng, mỗi dòng là kết quả tương ứng các lượt kiểm tra, nếu ~N~ là số đẹp thì ghi YES, ngược lại ghi NO.

Sample Input 1

2
6
7

Sample Output 1

NO
YES

Ràng buộc

• Có 40% số điểm: ~N \le 15~.
• Có 30% số điểm: ~15 < N \le 10^6~.
• Có 30% số điểm còn lại không có ràng buộc gì thêm.