Mô tả vấn đề

Viết chương trình nhập số nguyên n và số thực x. Tính ~x^n~

Input

Một dòng duy nhất gồm một nguyên n và số thực x.

Output

In ra ~x^n~, làm tròn 3 chữ số thập phân

Sample Input 1

2 3.5

Sample Output 1

12.250

hpgiakhang1405 là một người thích sự hoàn hảo (có lẽ thế :v). Vì thế khi anh ấy thấy một con số không hoàn hảo thì trong ngày hôm ấy anh ấy sẽ không có mood làm gì cả. Bạn hãy xem rằng trong ngày hôm nay anh ấy có bị tụt mood không nhé.

Một số hoàn hảo được định nghĩa là tổng các ước của nó (ngoại trừ chính nó) bằng chính số đó.

Ví dụ:

• 6 = 1 + 2 + 3.

Hãy viết chương trình kiểm tra một số nguyên dương ~n~ (~1 \leq n \leq 10^6~) có phải là số hoàn hảo hay không.

Input

• Một số nguyên dương ~n~.

Output

• In ra "YES" nếu ~n~ là số hoàn hảo.
• In ra "NO" nếu không phải.

Sample Input 1

6

Sample Output 1

YES

Sample Input 1

12

Sample Output 1

NO

hpgiakhang1405 là một người thích sự hoàn hảo (có lẽ thế :v). Vì thế khi anh ấy thấy một con số không hoàn hảo thì trong ngày hôm ấy anh ấy sẽ không có mood làm gì cả. Bạn hãy xem rằng trong ngày hôm nay anh ấy có bị tụt mood không nhé.

Một số hoàn hảo được định nghĩa là tổng các ước của nó (ngoại trừ chính nó) bằng chính số đó.

Ví dụ:

• 6 = 1 + 2 + 3.

Hãy viết chương trình kiểm tra một số nguyên dương ~n~ (~1 \leq n \leq 10^{14}~) có phải là số hoàn hảo hay không.

Input

• Một số nguyên dương ~n~.

Output

• In ra "YES" nếu ~n~ là số hoàn hảo.
• In ra "NO" nếu không phải.

Sample Input 1

6

Sample Output 1

YES

Sample Input 1

12

Sample Output 1

NO

Ngày xửa ngày xưa, trong một vương quốc nọ có một cô công chúa xinh đẹp. Kluco muốn lấy cô công chúa xinh đẹp đó chỉ khi anh ấy trả lời được câu hỏi của nhà vua. Nhà vua cho anh ấy một số nguyên ~n~ và yêu cầu anh ấy viết ra số đảo ngược của nó. Là một lập trình viên tài ba, bạn hãy giúp Kluco lấy được cô công chúa xinh đẹp nhé!

Nhiệm vụ của bạn là viết chương trình mô phỏng chiếc gương thần kỳ này.

Input

• Một số nguyên dương ~n~ (~1 \leq n \leq 10^9~).

Output

• Số nguyên là kết quả khi viết ~n~ lên gương thần kỳ.

Sample Input 1

1234

Sample Output 1

4321

Sample Input 2

790

Sample Output 2

97

Mô tả vấn đề

Viết chương trình nhập 2 số nguyên dương, tìm ước số chung lớn nhất (gcd - greatest common divisor) và bội số chung nhỏ nhất (lcm - least common multiple)  của chúng.

Input

Nhập 2 số nguyên dương a và b (1 ≤ a, b ≤ 10~^5~)

Output

In ra ước chung lớn nhất và bội chung nhỏ nhất

Sample Input 1

2 4

Sample Output 1

2 4

Cho 1 số nguyên n (Với 1≤n≤10000). Kiểm tra xem số n có phải số nguyên tố hay không ? Biết số nguyên tố là số chỉ có 2 ước.

Ví dụ:

1 không phải số nguyên tố vì nó chỉ có 1 ước (1).

4 không phải số nguyên tố vì nó chỉ có 3 ước (1,2,4).

7 là phải số nguyên tố vì nó chỉ có 2 ước (1,7).

Input

Dòng đầu tiên có chứa 1 số nguyên n (Với 1≤n≤10000).

Output

Một dòng duy nhất chứa "YES" nếu n là số nguyên tố. Nếu n không là số nguyên tố thì chứa "NO".

Examples

Input

1

Output

NO

Input

3

Output

YES

Cho 1 số nguyên n (Với 1≤n≤25). Tính số Fibonacci thứ n. Biết số Fibonacci - https://vi.wikipedia.org/wiki/Dãy_Fibonacci - là số mà số sau bằng tổng 2 số trước. Bắt đầu với số thứ 1 là 1 và số thứ 2 cũng là 1.

Input

Dòng đầu tiên có chứa 1 số nguyên n (Với 1≤n≤25).

Output

Một dòng duy nhất là 1 số là số Fibonacci thứ n.

Examples

Input

1

Output

1

Input

2

Output

1

Input

3

Output

2

Input

4

Output

3

Cho 1 số nguyên n (Với 1≤n≤10000). Tính số Fibonacci thứ n. Biết số Fibonacci - https://vi.wikipedia.org/wiki/Dãy_Fibonacci - là số mà số sau bằng tổng 2 số trước. Bắt đầu với số thứ 1 là 1 và số thứ 2 cũng là 1.

Lưu ý: Vì số đó có thể rất lớn nên sau khi tính xong lấy kết quả đó mod cho ~10^9~+7.

Ví dụ: số Fibonacci thứ 45 là : 1134903170. Sau khi mod nó (1134903170) cho ~10^9~+7 ta được số 134903163. Vậy đáp án là 134903163.

Input

Dòng đầu tiên có chứa 1 số nguyên n (Với 1≤n≤10000).

Output

Tính số Fibonacci thứ n sau khi đã mod cho ~10^9~+7.

Examples

Input

45

Output

134903163

Input

3

Output

2

Có những người bạn đang chơi game trên 1 bộ điều khiển. Bộ điều khiển này có 2 cái cần điều khiển, nhưng chỉ có 1 bộ sạc cho 2 cái cần này. Cần đầu tiên được sạc ở mức ~a_1~ phần trăm và cần thứ hai thì ở mức ~a_2~ phần trăm. Bộ sạc chỉ có thể sạc cho 1 cái cần ở đầu của mỗi phút. Trong mỗi phút, cái cần hoặc là giảm đi 2 phần trăm (nếu không kết nối với bộ sạc), hoặc là được sạc lên 1 phần trăm (nếu kết nối với bộ sạc).

Trò chơi tiếp tục trong khi cả hai cần điều khiển đều có năng lượng ở mức dương. Do đó, nếu vào đầu mỗi phút một cái cần điều khiển được sạc 1 phần trăm, nó phải được kết nối với bộ sạc, nếu không trò chơi sẽ dừng lại. Nếu mức năng lượng của 1 cái cần về 0 thì trò chơi cũng sẽ dừng lại.

Xác định số phút tối đa mà trò chơi có thể kéo dài. Biết rằng trò chơi không thể bị tạm dừng, hay nói cách khác, tại mỗi thời điểm, cả hai cần điều khiển đều phải được bật. Và cả 2 cần điều khiển đều có thể có mức năng lượng lớn hơn 100 phần trăm

Input

Dòng đầu tiên của input chứa 2 số nguyên dương ~a_1~ and ~a_2~ (1 ≤ ~a_1~,~a_2~≤100), lần lượt là mức năng lượng ban đầu của cần đầu vầ cần hai
Output

Một dòng duy nhất là diện tích hình vuông có cạnh là n.

Simple Examples

Input

3 5

Output

6

Input

4 4 

Output

5

Note
Ở ví dụ đầu, trò chơi kéo dài được 6 phút:

• ở ban đầu của phút thứ nhất, cái cần 1 được kết nối với bộ sạc, lúc kết thúc ở phút thứ nhất thì cái cần 1 có 4%, cần 2 thì 3%;

• tiếp tục trò chơi vào phút thứ hai, lúc kết thúc ở phúc thứ hai thì cái cần 1 có 5%, cần 2 thì 1%;

• ở ban đầu của phút thứ ba, cần 2 được kết nối với bộ sạc, lúc kết thúc thì cái cần 1 có 3%, cái cần 2 thì là 2%;

• tiếp tục trò chơi mà không thay đổi cần được sạc, lúc kết thúc phút thứ tư cần 1 có 1%, cần 2 thì là 3%; ở ban đầu của phút thứ năm, cần 1 được kết nối với bộ sạc, lúc kết thúc của phút thứ năm thì thì cần 1 có 2%, cần 2 thì là 1%;

• ở ban đầu của phút thứ năm, cần 2 được kết nối với bộ sạc, lúc kết thúc thì cần thứ nhất chỉ còn 0%, cần 2 thì có 2%.

Sau đấy, trò chơi dừng lại vì có một cái cần đã về 0

Trong một ngôi làng nhỏ, có một số nguyên ~n~ luôn khát khao trở thành giống số nguyên ~m~. Bạn của n là hai số 2 và 3. Một ngày nọ, ~n~ tâm sự về ước mơ của mình. Nghe xong câu chuyện, số 2 và số 3 cảm động và ngỏ lời với ~n~: "Hãy kết hợp với chúng tôi, biết đâu bạn có thể trở thành ~m~ bằng cách nhân với 2 hoặc 3."

Bạn hãy thử tính xem, khi ~n~ được nhân với 2 hoặc 3, nó có thể trở thành ~m~ hay không nhé!

Input

Hai số nguyên ~n~ và ~m~ ~(1 \le n, m \le 10^{18})~.

Output

In ra số lần kết hợp của ~n~ với số 2 và 3 để trở thành ~m~. Nếu không thể, in ra −1.

Sample Input

120 51840

Sample Output

7

Giải thích

Trong ví dụ trên N có thể di chuyển như sau:

~(120 → 240 → 720 → 1440 → 4320 → 12960 → 25920 → 51840)~.

Lưu ý : Nếu trình chấm phát hiện AI sẽ bị BAN.

Sau khi hoàn thành hết bài tập lớn của học kỳ này, Hiếu cuối cuối cùng cũng có thời gian rảnh rỗi để chơi võ lâm. Vì lâu quá không chơi nên Hiếu quên mất password và phải tạo lại nhân vật mới để chơi. Mỗi nhân vật của trò chơi võ lâm này chỉ có 2 chỉ số quan trọng là lực và trí. 2 chỉ số đó luôn là số nguyên dương để game thủ dễ tính toán.

Sau một hồi đắn đo, Hiếu đã chọn ra môn phái cho nhân vật của mình và nhân vật đó có khởi điểm là l lực và t trí . Sau khi chọn xong, hệ thống cho Hiếu d điểm để cộng vào cho 2 chỉ số lực (l) và trí (t) để tạo sự tuỳ biến cho trò chơi.

Vì đống bài tập lớn đã hành hạ Hiếu nên giờ đây anh ấy chỉ muốn tạo ra 1 nhân vật lực (l) nhiều hơn trí (t) để khi chơi nhân vật sẽ lăn xả nhiều hơn để có nhưng pha combat mãn nhãn.

Hỏi vậy liệu anh Hiếu có bao nhiêu cách tạo nhân vật theo ý mình ?

Lưu ý d (điểm) phải được cộng hết thì mới hoàn thành bước tạo nhân vật.

Input

Dòng đầu tiên chứa 3 số nguyên dương là l, t, d lần lượt là lực , trí của nhân vật anh Hiếu chọn và điểm được hệ thống cho. (Với 1≤l,t,d≤10000)

Output

Một dòng duy nhất là số cách tạo nhân vật theo ý của anh Hiếu.

Examples

Input

1 1 1

Output

1

Input

3 1 1

Output

2

Input

9 3 8

Output

7

Note

Test 1: Anh Hiếu 1 cách tạo nhân vật có cặp chỉ số lực và trí là (l=2,t=1).

Test 1: Anh Hiếu 2 cách tạo nhân vật có cặp chỉ số lực và trí là (l=4,t=1) và (l=3,t=2).

Test 1: Anh Hiếu 7 cách tạo nhân vật có cặp chỉ số lực và trí là (17,3), (16,4), (15,5), (14,6), (13,7), (12,8), (11,9).

Để gấp được một chiếc máy bay bằng giấy, người ta phải sử dụng một tờ giấy hình chữ nhật. Từ một tờ giấy có kích thước chuẩn, bạn có thể làm được s chiếc máy bay.

Một nhóm gồm k người quyết định chia nhau làm n chiếc máy bay giấy cho từng người. Họ sẽ đi mua một vài gói giấy, mỗi gói chứa p tờ giấy, và sau đó họ chia các tờ giấy cho mọi người. Mỗi người cần có đủ số tờ giấy để làm ra n máy bay. Hỏi họ nên mua bao nhiêu gói giấy?

Input
Một dòng duy nhất chứa 4 số nguyên k, n, s, p (1 ≤ k, n, s, p ≤ ~10^4~) — lần lượt là số người tham gia, số lượng máy bay mỗi người cần làm, số máy bay có thể làm từ một tờ và số tờ trong một gói
Output

In một số nguyên duy nhất — Số gói giấy tối thiểu mà họ nên mua.

Simple Examples

Input

5 3 2 3

Output

4

Input

5 3 100 1

Output

5

Note
Trong ví dụ đầu tiên họ phải mua 4 gói giấy: sẽ có tổng cộng 12 tờ giấy, và phát cho mỗi người 2 tờ giấy là đủ nhu cầu của mọi người.

Trong ví dụ thứ hai, họ phải mua một gói cho mỗi người vì họ không thể dùng chung một tờ giấy.

Ở Berland có 1 chiếc đồng hồ ma thuật bị hỏng. Trên mặt đồng hồ đã xuất hiện một vài cái lỗ là hậu quả của những viên đạn có hình quả bóng được bắn từ các khẩu pháo trong thời kì chiến tranh, cư dân ở đây rất lo ngại về việc sửa chữa. Cái đồng hồ ma thuật có thể được biểu diễn như một mặt phẳng Cartesian vô hạn, nơi gốc tọa độ tương ứng với tâm đồng hồ. Đồng hồ được sơn hai màu như trong hình:

Hình ảnh chỉ hiển thị phần trung tâm của đồng hồ. Màu này được mở rộng tự nhiên đến vô hạn.

Các quả bóng có thể được lấy làm điểm trên mặt phẳng. Hãy tìm màu của khu vực bị hư hỏng bởi quả bóng đã cho.

Tất cả các điểm nằm trên biên giới của một trong các khu vực được tô màu đen.

Input

Một dòng chứa 2 số nguyên x và y — tọa độ của lỗ tạo bởi quả bóng trên đồng hồ. Hai số x và y có giá trị tuyệt đối không vượt quá 1000.

Output

Tìm màu cần thiết.

Tất cả các điểm giữa điểm được cho và điểm gốc tọa độ có khoảng cách là giá trị tích phân đều được sơn màu đen

Simple Examples

Input

-2 1

Output

white

Input

2 1

Output

black

Input

4 3

Output

black

Cho n số nguyên dương với số thứ i có giá trị là ~a_i~ (Với 1 ≤ n, ~a_i~ ≤ 10000). Tính tổng các số lẻ trong n số nguyên dương đã cho.

Input

Dòng đầu tiên là chứa số nguyên dương n (Với 1 ≤ n ≤ 10000) - là số lượng số.

Dòng tiếp theo chứa n số nguyên dương là ai (Với 1 ≤ ~a_i~ ≤ 10000) - giá trị của phần tử thứ i.

Output

Một dòng duy nhất là tổng của n số nguyên dương đã cho.

Simple Examples

Input

1
1

Output

1

Input

3
1 1 3

Output

5

Input

9
3 8 1 2 1 8 2 6 2

Output

5

Cho 2 số nguyên a, b (Với 1≤a,b≤10000). Tính phần thực và phần nguyên của biểu thức a/b. Nếu kết quả đó là số vô hạn tuần hoàn thì in phần thực là −1.

Lưu ý: Phần thực không được dư số 0 ở cuối.

Ví dụ: Ta có phân số 1/4 = 0.25 thì kết quả hợp lệ là 0 25. Và nhưng kết quả không hợp lệ là 0 250 hoặc 0 025.

Input

Dòng đầu tiên chứa 2 số nguyên n, k (Với 1≤n,k≤10000).

Output

Một dòng duy nhất chứa 2 số nguyên là phần thực và phần nguyên của biểu thức a/b

Examples

Input

1 4

Output

0 25

Input

1 3

Output

0 -1

Input

4 3

Output

1 -1

Input

1 100

Output

0 01

Cho 1 số nguyên dương n (Với 1≤n≤10000). Xuất ra bàn cờ vua có kích thước nxn - n dòng và n cột. Quân đen thì in ra 1 còn quân trăng thì in ra 0. Và ô cờ đầu tiên ở gốc trái trên có màu trắng.

Input Dòng đầu tiên là chứa 2 số nguyên dương n, n (Với 1≤n≤10000)

Output

In ra nhiều dòng là bàn cờ vua với ô đen là số 1 và ô trắng là sô 0.

Simple Examples

Input

1

Output

0

Input

3

Output

010
101
010

Input

9

Output

010101010
101010101
010101010
101010101
010101010
101010101
010101010
101010101
010101010

Trên hành tinh AquariÚ, cuộc sống luôn chìm trong bóng tối, và mỗi cư dân đều phải mua một tờ vé số từ nhà đài Aquariumi, đơn vị độc quyền của hành tinh. Vào lúc 16h30 hàng ngày, kết quả xổ số sẽ được công bố. Người chiến thắng giải độc đắc sẽ được chọn, nhưng trên AquariÚ, việc trúng số không chỉ đơn thuần là may mắn. Thay vào đó, người trúng giải sẽ bị coi là quá tài năng và sẽ bị đưa đi hiến tế cho vị thần của núi, nơi mà thần AliEnder được cho là đã từng sinh sống.

Hôm nay, Đắt chưa kịp mua tờ vé số nào. Tuy nhiên, Đắt có khả năng đặc biệt là có thể biết trước liệu tờ vé số có trúng giải độc đắc hay không. Do thời gian gấp gáp và sự lo lắng ngày càng tăng, Đắt cần sự giúp đỡ của bạn để kiểm tra tờ vé số.

Tờ vé số được coi là trúng giải độc đắc khi tổng của ba số đầu tiên bằng tổng của ba số cuối cùng.

* Input *

Một số nguyên gồm 6 chữ số.

* Output *

In YES nếu số đó thỏa mãn điều kiện của Đắt. Ngược lại, in NO.

Sample Input

213231

Sample Output

YES

Vietminh123 được mời tham gia thử thách tìm kiếm đồng xu do Luv tổ chức. Trò chơi diễn ra trên một lưới tọa độ, nơi Vietminh123 bắt đầu tại vị trí ban đầu (0,0), và anh ta có thể di chuyển theo tám hướng: (x, y+1), (x+1, y+1), (x+1, y), (x+1, y-1), (x, y-1), (x-1, y-1), (x-1, y), (x-1, y+1). Ban đầu đồng xu ở một vị trí nào đó trong không gian, Mỗi lần Vietminh123 di chuyển, đồng xu cũng sẽ lùi xuống một đơn vị theo trục y (nếu đồng xu ở vị trí (x, y) thì sau khi Vietminh123 di chuyển vị trí đồng xu sẽ là xuống (x, y - 1)).

Vietminh123 vô tình nghe được vị trí ban đầu của đồng xu mà Luv sẽ đặt. Không muốn mất mặt trước đám đông, Vietminh123 đã nhờ bạn tính toán liệu anh ấy có thể lấy được đồng xu trước khi nó rơi quá xa hay không. Nếu có thể, in ra "YES", ngược lại in ra "NO".

Lưu ý: Vietminh123 có thể di chuyển 8 hướng, còn đồng xu thì chỉ rơi

Input

• Bao gồm 1 tọa độ x,y của đồng xu ~(-1000\le x,y \le 1000 )~

Output

• In YES nếu vietminh123 có thể tìm kiếm được đồng xu.
• Ngược lại, In NO

Sample Input

-1 -1

Sample Output

YES

Sau những giờ học thuật toán căng thẳng tại H3.2. Phú và Tài quyết định chơi một ván cờ tướng để giải trí. Tuy nhiên, sau 100 nước thì Phú đã dồn Tài vào thế khó và chỉ còn 2 con mã. Bây giờ Tài đã căng rồi lại càng cảm thấy căng thẳng hơn. Tài muốn chiến thắng nên đã tính tất cả các nước mà 2 con mã có thể đi để tìm được nước đi tiếp theo để có khả năng chiến thắng là cao nhất và hai con mã này không được tấn công nhau. Hãy giúp Tài tính tất cả các trường hợp trên.

Cụ thể, cho bàn cờ có kích thước n x n. Hãy đếm số cách đặt 2 con mã sao cho chúng không tấn công nhau.

Trên bàn cờ thì một quân mã ở ô (x, y) có thế tấn công 8 ô (x-1, y-2), (x-2, y-1), (x-2, y+1), (x-1, y+2), , (x+1, y+2), (x+2, y+1), (x+2, y-1), , (x+1, y-2)

Input

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

Output

Một dòng duy nhất là số cách đặt 2 con mã sao cho chúng không tấn công nhau.

*Example 1 *

Input

2

Output

6 

Note: Các cách đặt 2 quân mã là:

(1, 1) và (1, 2)

(1, 1) và (2, 1)

(1, 1) và (2, 2)

(1, 2) và (2, 1)

(1, 2) và (2, 2)

(2, 1) và (2, 2)

Example 2

Input

3 

Output

28 

Ở một vương quốc nọ vô cùng rộng lớn có diện tích ~N \times M~ hẹt ta nhưng lại được cai trị bởi một vị vua bất tài tên là Kluco, vì sự kém cỏi của mình nên vương quốc thường xuyên bị các thế lực đen tối xâm chiếm và c.ư.ớ.p bóc, để an toàn Kluco đã phân bổ đều các thành phố trên toàn bộ lãnh thổ để giảm thiểu thiệt hại khi bị các thế lực khác xâm lược nên cứ mỗi 1 hẹt ta vuông thì sẽ mọc lên 1 thành phố ở trung tâm.

Vào một ngày nọ ma vương unKluco là một phiên bản Kluco hắc ám tới từ một vũ trụ song song và thấy vô cùng ngứa mắt với cách phân bổ này của Kluco nên unKluco đã tấn công vào vương quốc của Kluco để bóc lột, nếu không đưa đủ vàng thì unKluco sẽ xoá sổ toàn bộ vương quốc.

Ma vương unKluco rất ghét hình vuông nên đã đề nghị cứ mỗi bốn thành phố riêng biệt tạo nên một hình vuông hoàn chỉnh thì unKluco sẽ thu của Kluco ~1~ thỏi vàng. Vì bất tài nên Kluco cũng chả giỏi tính toán, trong lúc không thể tính được số vàng phải trả là bao nhiêu thì Kluco nhớ ra rằng vương quốc mình dẫn còn một lập trình viên tài ba đó chính là bạn.

Bạn hãy giúp Kluco pha này nhé, biết rằng ~1 \leq N,M \leq 2*10^5~ và unKluco không mang túi 9 gang nên chỉ nhận số vàng đã chia dư cho ~10^9 + 7~

Input

• Hai số nguyên ~N,M (1 \leq N,M \leq 2*10^5)~ , đại diện cho chiều dài và chiều rộng của vương quốc.

Output

• Một số nguyên duy nhất là số thỏi vàng unKluco nhận được.

Sample Input

3 3

Sample Output

6

Giới Hạn

• Có 20% số test với ~N, M \leq 10~
• Có 20% số test với ~N, M \leq 100~
• Có 20% số test với ~N, M \leq 300~
• Có 20% số test với ~N, M \leq 10^3~
• Còn lại không có ràng buộc nào