Nhân một ngày nghỉ, Sơn ngồi học toán và nghĩ ra một số có tính chất đặc biệt: số chỉ có đúng ~3~ ước. Ví dụ số ~25~ có ~3~ ước là ~1, 5, 25~.

Yêu cầu: Cho số tự nhiên ~n~ (~n \le 10^9~), hãy kiểm tra ~n~ có là số đặc biệt không?

Input

Đọc từ file văn bản SOHOC.inp chứa số ~n~.

Output

Ghi ra file văn bản SOHOC.out:

• Ghi số ~1~ nếu ~n~ là số đặc biệt.
• Ghi số ~0~ nếu ~n~ không là số đặc biệt.

Ràng buộc

• ~n \le 10^9~

Sample Input

25

Sample Output

1

Nam được bố mẹ tặng cho chiếc điện thoại mới, do dùng điện thoại quá nhiều nên bây giờ mắt của Nam nhìn không rõ và chỉ nhầm hai số ~5~ và ~6~, đôi khi chép nhầm ~5~ thành ~6~ và ngược lại. Ví dụ số ~25~ có thể ghi thành số ~26~. Do đó, nếu đầu bài cho ~12 + 25~ thì Nam có thể cho kết quả là ~37~ hoặc ~38~.

Yêu cầu: Cho ~2~ số nguyên dương ~a~ và ~b~. Hãy xác định tổng nhỏ nhất và lớn nhất của hai số ~a~, ~b~ mà ta có thể chờ đợi ở Nam.

Input

Đọc từ file văn bản MISTAKE.inp gồm một dòng chứa hai số nguyên dương ~a~ và ~b~ (~a < 10^9~, ~b < 10^9~).

Output

Ghi ra file văn bản MISTAKE.out trên một dòng gồm hai số: tổng nhỏ nhất và tổng lớn nhất có thể nhận được.

Sample Input

12 25

Sample Output

37 38

Cho số nguyên dương ~N~, hãy tìm số nguyên ~S~ thoả mãn:

• ~S \ge N~ và ~S~ là số nhỏ nhất,
• ~S~ chia hết cho ~N~,
• Trong hệ thập phân, ~S~ chỉ chứa các chữ số trong tập ~{7, 2, 0}~,
• ~S \le 10^9~.

Input

Đọc từ file văn bản BHK.inp chứa duy nhất một số nguyên dương ~N~ (~N \le 500000~).

Output

Ghi ra file văn bản BHK.out một số nguyên ~S~ tìm được, hoặc ghi ~0~ nếu không tồn tại ~S~.

Sample Input

```id="y0tqzv" 3

## Sample Output

```id="ah9qk4"
27

Jame có ~N~ món quà, món quà thứ ~i~ có giá trị là ~A_i~. Jame muốn tặng ~N~ món quà này cho hai bạn sao cho độ chênh lệch giữa tổng giá trị các món quà mà mỗi bạn nhận được là nhỏ nhất.

Yêu cầu: Tìm độ chênh lệch nhỏ nhất giữa tổng giá trị các món quà mà mỗi bạn nhận được.

Input

Đọc từ file văn bản GIFT.inp gồm:

• Dòng thứ nhất chứa số nguyên dương ~N~ là số món quà (~N \ge 2~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, … , A_N~ là giá trị của các món quà.

Output

Ghi ra file văn bản GIFT.out độ chênh lệch nhỏ nhất giữa tổng giá trị các món quà mà mỗi bạn nhận được.

Ràng buộc

• ~N \le 10^3~
• ~A_i \le 10^5~

Các test tương ứng:

• ~50%~ số điểm có ~N \le 10^2~, ~A_i \le 10^3~.
• ~50%~ số điểm còn lại có ~N \le 10^3~, ~A_i \le 10^5~.

Sample Input

7
6 25 41 10 35 27 16

Sample Output

4

Nhân dịp con trai đạt kết quả cao trong kì thi học sinh giỏi, Ông Jasson đã nghĩ ra món quà đặc biệt tặng con trai. Đó là chiếc bánh do chính tay ông tự làm, thành phần của bánh là bánh mì (~B~), xúc xích (~X~) và pho mát (~P~) tạo thành từng lớp. Các lớp bánh đi từ dưới lên trên, ví dụ như công thức ~"BXPBX"~ là miếng bánh gồm bánh mì, xúc xích, pho mát, bánh mì và xúc xích.

Ông Jasson đang có ~m~ miếng bánh mì, ~n~ miếng xúc xích và ~k~ miếng pho mát. Giá mua thêm mỗi thành phần như sau: mỗi miếng bánh mì là ~t_1~ đồng, mỗi miếng xúc xích là ~t_2~ đồng và mỗi miếng pho mát là ~t_3~ đồng.

Yêu cầu: Hãy xác định số bánh ông có thể làm được nhiều nhất với chi phí mua thêm các thành phần không quá ~r~ đồng.

Input

Đọc từ file văn bản HUMBERGER.inp gồm nhiều bộ dữ liệu (số bộ dữ liệu không quá ~10^7~), mỗi bộ dữ liệu gồm ~4~ dòng:

• Dòng 1: Chứa một xâu (độ dài lớn hơn ~0~ và không quá ~100~) chỉ chứa các ký tự ~'B'~, ~'X'~, ~'P'~ thể hiện công thức làm một chiếc bánh của Jasson.
• Dòng 2: Chứa ba số tự nhiên ~m~, ~n~, ~k~.
• Dòng 3: Chứa ba số nguyên dương ~t_1~, ~t_2~, ~t_3~.
• Dòng 4: Chứa một số nguyên dương ~r~.

Output

Ghi ra file văn bản HUMBERGER.out, tương ứng với mỗi bộ dữ liệu là số lượng bánh tối đa ông có thể làm được.

Ràng buộc

• ~50%~ số test có ~m, n, k, t_1, t_2, t_3 \le 10^3~, ~r \le 10^{12}~.
• ~50%~ số test còn lại có ~m, n, k, t_1, t_2, t_3 \le 10^9~, ~r \le 10^{12}~.

Các số trên cùng một dòng của dữ liệu vào hoặc kết quả cách nhau ít nhất một dấu cách.

Sample Input

BBBXXP
6 4 1
1 2 3
4
BBP
1 10 1
1 10 1
21

Sample Output

2
7

Giải thích: Với ~4~ đồng có thể mua thêm ~1~ miếng pho mát hết ~3~ đồng. Khi đó tổng cộng có ~6~ miếng bánh mì, ~4~ miếng xúc xích và ~2~ miếng pho mát, nên có thể làm được ~2~ chiếc bánh.