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.

Cho một mảng a có n phần tử ~a_0~, ~a_1~, ..., ~a_{n-1}~ và một số x. Bạn hãy in ra vị trí của x trong mảng a.

Chính xác hơn, hãy in ra vị trí i trong mảng với ~a_i~ = x. Các vị trí được in theo thứ tự tăng dần và chỉ số bắt đầu từ 0.

Input

Gồm 2 dòng.

Dòng thứ nhất là số nguyên n. (~n ≤ 10^5~)

Dòng thứ hai gồm n số ~a_0~, ~a_1~, ..., ~a_{n-1}~. (1 ≤ ~a_i~ ≤ ~≤ 10^3~)

Output

Một dòng duy nhất là vị trí của x trong mảng a và cách nhau bởi dấu cách. Nếu x không xuất hiện trong mảng a thì không in ra gì.

Examples

Input

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

Output

0 5 7

Truyện kể rằng HoanNONIT là một đứa trẻ với tâm hồn không bao giờ trưởng thành, Hoan thường làm những trò mèo trong Lab H3.2

Một hôm Banmkh6 đưa đến cho Hoan 7 cái lắc tay. Khi nhìn thấy chiếc lắc tay, Hoan dã rất thích thú. Ngày đêm ngắm nhìn lắc tay, mỗi ngày Hoan chuyển 1 chiếc lắc tay từ tay này sang tay khác, và sẽ chuyển ngược lại nếu như hết 1 tuần.

Sau ~n~ ngày, Ban gặp lại Hoan, hỏi rằng mỗi tay của Hoan có bao nhiêu lắc tay??(ban đầu Hoan đeo toàn bộ lắc tay ở tay phải)

Subtasks

• Subtasks 1: ~1 \leq n \leq 10^{6}~
• Subtasks 2: ~1 \leq n \leq 10^{10}~

Input

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

Output

Số lắc tay ở tay trái và số lắc tay ở tay phải của Hoan sau n ngày

Sample Input 1

5 

Sample Output 1

5 2  (đây là đáp án đã sửa)

Sample Input 2

12

Sample Output 2

2 5 (đây là đáp án đã sửa)

Tài là một học sinh giỏi lớp 5. Trong cuộc thi tuyển chọn học sinh giỏi toán cho trường, thầy giáo đã cho Tài một bài toán rất khó đối với học sinh lớp 5 là tính tổng của dãy các số nguyên 1 + 2 + 3 + ... + n. Vì trong lúc thi quá căng thẳng nên Tài đã quên công thức để tính tổng dãy số này nên Tài đã cộng từng số một lại với nhau. Tuy nhiên có quá nhiều số nên Tài đã lỡ quên không cộng một số x. Cho biết số nguyên dương n và tổng s mà Tài đã cộng. Bạn có thể giúp Tài xác định số x còn thiếu hay không?

Input

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

subtask 1: ~a ≤ 10^4, s  ≤ 10^9~

subtask 2: ~a ≤ 10^9, s  ≤ 10^{18}~

Output

Một dòng duy nhất là số x cần tìm.

Examples

Input

4 7 

Output

3

*Note: *Tài đã cộng các số 1 + 2 + 4 = 7 nên còn thiếu số 3.

Banmkh6 là một người bị ám ảnh bởi những con số, anh ấy thường nghĩ ra những bài toán liên quan tới những chữ số quái dị, và đây là một đề bài tương tự:

"Tôi có một số n và tôi muốn tách n thành tổng của các số nhị phân "

Biết rằng số nhị phân là các số mà các chữ số của nó chỉ bao gồm 0 và 1, và không bắt đầu bằng số 0(ngoại trừ số 0). Ví dụ số 10 11000 101 là các số nhị phân, nhưng các số 2 23 1201 lại không phải là số nhị phân.

Và yêu cầu của Ban là tìm số lượng số nhị phân ít nhất sao cho tổng của chúng là n.

Ví dụ n = 21 = 10 + 11 => số lượng số nhị phân ít nhất mà tổng bằng 21 là 2.

Subtasks

• Subtasks 1: ~1 \leq n \leq 10^{6}~
• Subtasks 2: ~1 \leq n \leq 10^{18}~

Input

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

Output

Số lượng số nhị phân ít nhất mà tổng bằng n.

*Sample Input *

21

*Sample Output *

2

Để 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

Vì bữa nay ăn nhiều bột ngọt quá, Banmkh6 thường xuyên bị lú lẫn.

Một ngày đẹp trời, Ban mua một chiếc két sắt khá đặc biệt, bên trên có n cái nút, các nút được đánh dấu từ 1 tới n.

Để mở được ổ khóa thì Ban phải ấn n nút đó theo 1 thứ tự nhất định. Nếu nhấn 1 nút chính xác thì các nút khác và nút đó sẽ giữ nguyên và không thay đổi, nếu nút đó bấm sai thời điểm, tất cả các nút đã nhấn sẽ bật lên, sau đó Ban phải nhấn nút lại từ đầu.

Hay lú lẫn nên Ban lỡ làm rớt mật khẩu khi đang đi về nhà. Thế là Ban phải mò từng mật khẩu một. Ban không biết là cần nhấn ít nhất bao nhiêu nút để chắc chắn rằng sẽ mở được ổ khóa??

NOTE

Vì đáp án có thể rất lớn nên lấy đáp án chia dư cho ~10^9+7~

Input

Dòng đầu tiên chứa 1 số nguyên n là số nút của két sắt~(1 \leq n \leq 10^{5})~

Output

In ra số lượng lần bấm ít nhất để chắc chắn sẽ mở két sắt.

*Sample Input *

3

*Sample Output *

7

Giải thích test đề

Giả sử mật khẩu đúng là nhấn lần lượt các nút 1 2 3.

Đầu tiên Ban nhấn nút 2 thì sai nên bật lên lại(lần 1), Ban biết chắc chắn rằng số 2 nhấn đầu tiên là sai nên Ban bấm số 3, nút số 3 lại bật lên(lần 2)... "ơ, lại sai rồi, thế chắc chắn rằng nút đầu tiên luôn luôn là số 1", sau đó Ban nhấn nút số 1(lần 3) và không có gì xảy ra cả, Ban lại nhấn nút số 3(lần 4) thì cả nút số 1 và số 3 bật lên, Ban lại nghĩ :"vậy chắc chắn phải nhấn nút số 1 đầu tiên, sau đó phải nhấn nút số 2 và cuối cùng là nhấn nút số 3", sau đó Ban lại nhấn lần lượt nút số 1(lần 5) rồi số 2(lần 6) và số 3(lần 7) và chiếc két sắt đã mở ra. Vậy sau ít nhất 7 lần thì chiếc két sắt chắc chắn mở ra.

Cho một số nguyên không âm ~n~. Hãy hỏi có bao nhiêu cách chọn ra bộ 5 biến ~a, b, c, d, e~ là số nguyên không âm sao cho tổng lại bằng ~n~:

~a + b^2 + c^3 + d^2 + e = n~

Giới hạn

• ~0 \leq n \leq 200~

Đầu vào

• Dòng đầu tiên: số nguyên không âm ~n~.

Đầu ra

• Một số nguyên duy nhất: số cách chọn ra bộ 5 biến không âm sao cho tổng bằng ~n~.

Sample Input

5

Sample Output

44

Nhập vào một mảng ~a~ gồm ~n~ phần tử.

Tìm giá trị lớn nhất của biểu thức sau:

~|a_i - a_j| + |a_j - a_k| + |a_k - a_l| + |a_l - a_i|~

Với ~1 \leq i, j, k, l \leq n~ và ~i, j, k, l~ phân biệt nhau.

Giới hạn

• ~4 \leq n \leq 100~
• ~-10^6 \leq a_i \leq 10^6~

Đầu vào

• Dòng đầu tiên: số nguyên ~n~.
• Dòng thứ hai: ~n~ số nguyên ~a_i~.

Đầu ra

• Một số nguyên duy nhất: giá trị lớn nhất của biểu thức.

Sample Input

5
1 2 3 4 5

Sample Output

12

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

Cho một ma trận (mảng hai chiều), có kích thước ~n~ x ~n~ và số nguyên dương ~k~ là ước của ~n~. Giả sử ~a_{i, j}~ là giá trị tại hàng ~i~ và cột ~j~ của ma trận. Hiện tại dữ liệu của ma trận này đang bị lặp lại nhiều lần làm cho ma trận có kích thước lớn, bạn hãy thu gọn ma trận này nhé. Cụ thể khi chia đều ma trận ban đầu thành các ma trận kích thước ~k~ x ~k~, thì các giá trị có được này giống nhau, ta chỉ cần lưu giá trị này một lần. Hãy xem ví dụ để hiểu thêm nhé.

Input

Dòng đầu tiên, gồm cặp số số nguyên ~n~ và ~k~ là kích thước của ma trận và kích thước của ma trận lặp.

Tiếp theo, gồm ~n~ dòng mỗi dòng gồm ~n~ giá trị ~a_{i, 0}, a_{i, 1}, ..., a_{i, n - 1}~ đại diện cho ~n~ các giá trị thuộc dòng thứ ~i~.

Output

Hãy in ma trận đã được rút gọn của ma trận ban đầu.

Constraints

~1 \le n \le 10^3~

~a_{i, j} \in \{0, 1\}~

Input Sample 1

4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Output Sample 1

0

Input Sample 2

6 3
0 0 0 1 1 1
0 0 0 1 1 1
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 0 0 0
1 1 1 0 0 0

Output Sample 2

0 1
1 0

Input Sample 3

6 2
0 0 1 1 0 0
0 0 1 1 0 0
1 1 1 1 1 1
1 1 1 1 1 1
1 1 0 0 0 0
1 1 0 0 0 0

Output Sample 3

0 1 0
1 1 1
1 0 0