Viết chương trình nhập vào số ngày ở khách sạn của một khách hàng. Tính số tiền phải trả theo công thức:

Tiền trả = Số tuần x 700000 + số ngày lẻ x 120000.

Input

Một dòng duy nhất chứa một số duy nhất n là số ngày ở khách sạn

Output

Một dòng duy nhất là số tiền ở khách sạn của khách hàng đó

Examples

Input

10

Output

1060000

Giải thích

Số tuần ở khách sạn là 1 tuần
Số ngày lẻ là 3 ngày
Số tiền phải trả là: 1*700000 + 120000*3 = 1060000 

Để cho cuộc thi sôi động hơn. Lab H3.2 quyết định sẽ mở ra một giải đặc biệt gồm những con số đặc biệt. Mỗi vòng chơi thì bạn được phép đoán rằng một số có phải số đặc biệt hay không?, nếu đoán trúng thì có cơ hội nhận phần thưởng là một chiếc điện thoại đời mới nhất dòng BanQ đa chức năng trị giá hàng chục tỷ đồng.

Một số đặc biệt là số chia hết cho tổng các chữ số của chính nó. Ví dụ 10 là số đặc biệt vì 10 chia hết cho 1+0.

Input

Dòng đầu tiên chứa 1 số nguyên n ~(1 \leq n \leq 10^{18})~

Output

Nếu n là số đặc biệt thì in ra YES,nếu không in ra NO

*Sample Input *

10

*Sample Output *

YES

Viết chương trình nhập vào số ngày và chuyển đổi số ngày thành năm, tuần và ngày.

Lưu ý: Bỏ qua năm nhuận.

Input

Một dòng duy nhất chứa số ngày n (1<=n<=10000)

Output

Một dòng chứa số năm, số tuần, số ngày cách nhau bới dấu cách

Examples

Input

1329

Output

3 33 3

*Note: *

1329 ngày là 3 năm, số ngày còn lại 1329 - 365 * 3 = 234

234 ngày là 33 tuần, số ngày còn lại 234 - 7 * 33 = 3

còn lại 3 ngày

Một buổi tối đẹp trời trong lúc ra đề cho các bạn của mình, Aquarius người bạn chăm chỉ của chúng ta bổng nhận được một tin không hay là xe của cậu đã bị thủng lốp trước Aquarius vô cùng buồn ~:<~ Và ròi bụt hiện ra và nói nếu con có thể giải được câu đố sau ta sẽ giúp con khôi phục chiếc xe của mình. Nhưng vì quá mệt mỗi nên Aquarius đành phải nhờ bạn giải giúp và nội dung câu đố như sau:

Bạn được cung cấp hai số nguyên N và M

Xét một đa giác đều lồi có N đỉnh. Nhắc lại rằng một đa giác đều là một đa giác (tất cả các góc đều bằng nhau) và các cạnh (tất cả các cạnh có cùng độ dài). Nhiệm vụ của bạn là cho biết liệu có thể xây dựng một đa giác đều khác với m đỉnh sao cho tâm của nó trùng với tâm của đa giác ban đầu và mỗi đỉnh của nó là một số đỉnh của đa giác ban đầu. Nếu có thể hãy in YES ngược lại in NO

Biết rằng ngoài kia trời đang mưa rất to, hãy giúp Aquarius nhanh chóng trở về thôi nào!!

*Ví dụ *

n=6 và m=3 ta sẽ được kết quả như sau:

Đầu Vào

Hai số nguyên 3 ≤ M < N ≤ 100.

input

6 3

Output

YES

input

5 3

Output

NO

Problem Statement

Sinh nhật lần thứ ~16~ của E869120 và square1001 sắp đến. Takahashi từ AtCoder Kingdom đã tặng họ một chiếc bánh tròn được cắt thành ~ 16 ~ miếng hình quạt bằng nhau.

E869120 và square1001 sắp ăn ~ A ~ và ~ B ~ trong số những miếng đó, tương ứng, khi họ tìm thấy một tờ giấy được đính kèm trên chiếc bánh với nội dung cùng một người không được lấy hai miếng bánh liền nhau.

Cả hai người họ có thể tuân theo hướng dẫn trong ghi chú và lấy số lượng miếng bánh mong muốn không?

Constraints

• ~ A ~ và ~ B ~ là các số nguyên từ ~ 1 ~ đến ~ 16 ~ (bao gồm).
• ~ A + B ~ tối đa là ~ 16 ~.

Input

Nhập Input theo format dưới đây:

~A~ ~B~

Output

Nếu cả E869120 và square1001 đều có thể tuân theo hướng dẫn trong ghi chú và lấy số lượng miếng bánh mong muốn, hãy in Yay!; nếu không, in :(.

Sample Input 1

5 4

Sample Output 1

Yay!

Sample Input 2

8 8

Sample Output 2

Yay!

Cả hai đều có thể lấy số lượng mảnh mong muốn như sau:

Sample Input 3

11 4

Sample Output 3

:(

Trong trường hợp này, không có cách nào để họ lấy số lượng mảnh mong muốn, thật không may.

Problem Statement

Alice and Bob are controlling a robot. They each have one switch that controls the robot.
Alice started holding down her button ~A~ second after the start-up of the robot, and released her button ~B~ second after the start-up.
Bob started holding down his button ~C~ second after the start-up, and released his button ~D~ second after the start-up.
For how many seconds both Alice and Bob were holding down their buttons?

Constraints

• ~0≤A<B≤100~ </li>
• ~0≤C<D≤100~ </li>
• All input values are integers.

Input

Input is given from Standard Input in the following format:

~A~ ~B~ ~C~ ~D~

Output

Print the length of the duration (in seconds) in which both Alice and Bob were holding down their buttons.

Sample Input 1

0 75 25 100

Sample Output 1

50

Alice started holding down her button ~0~ second after the start-up of the robot, and released her button ~75~ second after the start-up.
Bob started holding down his button ~25~ second after the start-up, and released his button ~100~ second after the start-up.
Therefore, the time when both of them were holding down their buttons, is the ~50~ seconds from ~25~ seconds after the start-up to ~75~ seconds after the start-up.

Sample Input 2

0 33 66 99

Sample Output 2

0

Alice and Bob were not holding their buttons at the same time, so the answer is zero seconds.

Sample Input 3

10 90 20 80

Sample Output 3

60

Cửa hàng quýt của Tuấn Anh đang tổ chức một chương trình khuyến mãi đặc biệt: cứ mang k cuống quýt đến cửa hàng, khách hàng sẽ được đổi lấy 1 trái quýt mới.

Hiện tại, Tuấn Anh đang có n trái quýt. Mỗi ngày, bạn ấy ăn hết đúng 1 trái quýt và giữ lại cuống để tham gia chương trình đổi quýt. Mỗi khi có đủ k cuống, Tuấn Anh sẽ ngay lập tức đổi chúng lấy một cây quýt mới và tiếp tục ăn vào những ngày sau.

Hãy tính xem Tuấn Anh có thể ăn quýt trong bao nhiêu ngày trước khi không còn trái quýt nào để ăn nữa nha 😜

Input

Một dòng gồm hai số nguyên n, k.

Output

Gồm một số nguyên duy nhất là số ngày trước khi bạn hết nấm.

Điều kiện

~1 \le n \le 10^5~.

~2 \le k \le 10^5~.

Input

10 3

Output

14

Giải thích: Ban đầu bạn có ~n = 10~ cây nấm. Mỗi ngày bạn ăn ~1~ cây nấm.

Ngày 1 đến Ngày 3: Bạn ăn ~3~ cây nấm đầu tiên. Lúc này bạn đã đổi được ~3~ chân nấm. Vì ~k = 3~, bạn đổi ~3~ chân nấm này để lấy thêm ~1~ cây nấm mới. Số nấm hiện có: ~10 - 3 + 1 = 8~ cây.

Ngày 4 đến Ngày 6: Bạn ăn tiếp ~3~ cây nấm. Đổi ~3~ chân nấm lấy thêm ~1~ cây nấm mới. Số nấm hiện có: ~8 - 3 + 1 = 6~ cây.

Ngày 7 đến Ngày 9: Bạn ăn tiếp ~3~ cây nấm. Đổi ~3~ chân nấm lấy thêm ~1~ cây nấm mới. Số nấm hiện có: ~6 - 3 + 1 = 4~ cây.

Ngày 10 đến Ngày 12: Bạn ăn tiếp ~3~ cây nấm. Đổi ~3~ chân nấm lấy thêm ~1~ cây nấm mới. Số nấm hiện có: ~4 - 3 + 1 = 2~ cây.

Ngày 13 và Ngày 14: Bạn ăn nốt ~2~ cây nấm còn lại. Đến lúc này bạn thu được ~2~ chân nấm, nhưng không đủ ~3~ chân nấm (~k = 3~) để đổi thêm cây nào nữa.

Tổng cộng bạn ăn được trong ~14~ ngày trước khi hết nấm.

→ Đáp án là 14.

Boingheo rất thích chơi với những con số. Một hôm, bạn ấy nghĩ ra một trò chơi nhỏ với hai số nguyên a và b.

Boingheo sẽ tìm tất cả các số nguyên dương d có thể chia hết cả a lẫn b. Tuy nhiên, thay vì chọn ước chung lớn nhất như bình thường, Boingheo lại đặt ra một luật đặc biệt hơn: số d được chọn phải có tổng các chữ số lớn nhất trong tất cả các ước chung của a và b.

Ví dụ, nếu có hai ước chung là 18 và 24 thì Boingheo sẽ thích 18 hơn vì tổng các chữ số của nó là 1 + 8 = 9, trong khi của 24 chỉ là 2 + 4 = 6.

Một số nguyên dương d được gọi là ước số chung đặc biệt của hai số a và b nếu:

• a chia hết cho d;
• b chia hết cho d;
• tổng các chữ số của d là lớn nhất trong tất cả các ước chung của a và b.

Hãy giúp Boingheo tìm tổng các chữ số của ước số chung đặc biệt của hai số a và b nhé 😜

Input

Trong một dòng duy nhất ghi hai số nguyên:

a, b (1 ≤ a, b ≤ 10^9).

Output

In ra một số nguyên duy nhất là tổng các chữ số của ước số chung đặc biệt của a và b.

Input

220 440

Output

10

Giải thích

Ta có:

220 và 440 có các ước chung là: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, 220.

Tổng các chữ số của một số ước chung tiêu biểu:

• 44 có tổng chữ số là 4 + 4 = 8.
• 55 có tổng chữ số là 5 + 5 = 10.
• 110 có tổng chữ số là 1 + 1 + 0 = 2.
• 220 có tổng chữ số là 2 + 2 + 0 = 4.

Ước chung có tổng các chữ số lớn nhất là 55, với tổng bằng: 10

Boingheo vừa viết lên bảng đầy đủ các số nguyên từ 1 đến n để chuẩn bị cho một trò chơi. Thế nhưng trong lúc đang hí hoáy lau bảng, Boingheo vô tình xóa mất đúng một số 😭.

Bây giờ trên bảng chỉ còn lại n - 1 số, và đặc biệt mỗi số đều khác nhau, nằm trong khoảng từ 1 đến n.

Boingheo nhìn mãi mà vẫn không nhớ mình đã xóa mất số nào. Hãy giúp Boingheo tìm ra con số mất tích nhé 🔍😜

Input

Dòng đầu tiên chứa số nguyên n.

Dòng thứ hai chứa n - 1 số nguyên phân biệt. Mỗi số nằm trong đoạn từ 1 đến n.

Output

In ra số duy nhất bị thiếu. Constraints ~2 ≤ n ≤ 2 × 10^5~

Input

5
2 3 1 5

Output

4

Giải Thích Vì các số từ 1 đến 5 phải là 1, 2, 3, 4, 5, nhưng trên bảng chỉ còn 1, 2, 3, 5, nên số bị Boingheo xóa mất là 4.

Longg đang hí hoáy tính giai thừa của một số nguyên n thì phát hiện ra một điều khá thú vị 🤔💭

Giai thừa của n, ký hiệu là n!, được tính bằng: n! = 1 × 2 × 3 × ... × n

Nhưng Longg không quan tâm n! lớn đến mức nào. Điều Longg tò mò là:

🔍 Có bao nhiêu chữ số 0 liên tiếp ở cuối của n!?

Với một số nguyên n cho trước, hãy giúp Longg tìm số lượng chữ số 0 liên tiếp ở cuối n! nhé 🧠✨

Điều kiện 1 ≤ n ≤ 10^9

Input

Dòng duy nhất chứa một số nguyên n.

Output

In ra một số nguyên duy nhất — số lượng chữ số 0 liên tiếp ở cuối n!.

Input

20

Output

4

Giải Thích

Ta có:

20! = 2432902008176640000

Phần cuối của số này là:

...0000

Có đúng 4 chữ số 0 liên tiếp ở cuối, vì vậy đáp án là: 4

Cho một chuỗi nhị phân ~t~=~t_1~~t_2~ ... ~t_m~ chỉ gồm các ký tự 0 và 1.

Các cặp ký tự kề nhau được xét gồm: ~t_1t_2,\ t_2t_3,\ldots,t_{m-1}t_m~ và thêm cặp ~t_mt_1~ tức là ký tự cuối được nối vòng với ký tự đầu. Do đó có đúng m cặp được xét.

Nếu chuỗi chỉ có một ký tự, cặp duy nhất là t1t1.

Chuỗi t được gọi là cân bằng tuần hoàn nếu số lượng của bốn loại cặp

• 00
• 01
• 10
• 11

đều bằng nhau.

Chi phí của một chuỗi

Chi phí của một chuỗi nhị phân là số ký tự ít nhất cần chèn thêm để biến nó thành một chuỗi cân bằng tuần hoàn.

Có thể chèn 0 hoặc 1 vào bất kỳ vị trí nào, kể cả trước ký tự đầu hoặc sau ký tự cuối. Không được xóa hoặc thay đổi các ký tự ban đầu.

Cho chuỗi nhị phân s và q truy vấn.

Mỗi truy vấn cho hai chỉ số l và r.

Hãy tìm chi phí của chuỗi con ~s_ls_{l+1}\ldots s_r.~

Input

Dòng đầu chứa hai số nguyên:

~1 \le n,q \le 3\cdot10^5~

trong đó:

• n là độ dài chuỗi.
• q là số truy vấn.

Dòng tiếp theo chứa chuỗi nhị phân s có độ dài n.

q dòng tiếp theo, mỗi dòng chứa: l r

Input

11 7
00111100000
1 8
1 1
1 2
1 4
3 6
2 7
7 11

Output

4
3
2
0
4
2
7 

Giải thích:

Truy vấn 1 1: chuỗi con là 0. Chèn thêm 011 để được 0011. Khi nối vòng, các cặp 00, 01, 11, 10 đều xuất hiện đúng 1 lần. → Cần 3 lần chèn.

Truy vấn 1 2: chuỗi con là 00. Chèn thêm 11 để được 0011, đây là chuỗi cân bằng tuần hoàn. → Cần 2 lần chèn.

Truy vấn 1 4: chuỗi con là 0011. Các cặp khi nối vòng là: 00, 01, 11, 10, mỗi loại xuất hiện đúng 1 lần. → Chuỗi đã cân bằng, đáp án là 0.

Truy vấn 2 7: chuỗi con là 011110. Có thể chèn thêm 2 ký tự 0 để tạo một chuỗi cân bằng như 00110110. → Đáp án là 2.