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.

Hàng của cô Ban hôm nay có nhập về một số lượng lớn kẹo, gồm ~n~ viên. Khách hàng thân thiết của cô là anh Mạnh và anh Vũ. Mạnh sẽ chọn trước một số ~k~ nguyên. Mỗi ngày Mạnh sẽ ăn ~k~ viên vào buổi sáng và Vũ sẽ 1/10 số kẹo còn lại vào buổi chiều (nếu số kẹo còn lại không chia hết cho 10 thì làm tròn xuống). Ngày nào cũng lặp lại như thế, đến khi ăn hết kẹo thì thôi. Mạnh muốn giành được sự quan tâm từ cô Ban nên muốn chọn số ~k~ sao cho số kẹo mà Mạnh ăn là >= số kẹo mà Vũ ăn. Bạn hãy giúp Mạnh tìm ra ~k~ nhỏ nhất để được điều này nhé.

Input

Một dòng duy nhất là số nguyên dương ~n~ với ~1 \le n \le 10^{18}.~

Output

Số ~k~ cần tìm.

Sample input

68

Sample output

3

*Giải thích: * với ~k=3~ viên thì quá trình ăn kẹo của các ngày sẽ diễn ra như sau:

~(65,59) \to (56,51) \to (48,44) \to (41,37) \to (34,31) \to (28,26) \to (23,21) \to (18,17) \to (14,13) \to (10,9) \to (6,6) \to (3,3) \to (0,0).~

Ta tính được Mạnh ăn ~39~ viên kẹo, nếu chọn ~k = 2~ thì số lượng này sẽ ít hơn.

Cho hai chuỗi ký tự ~s, t~ có cùng độ dài. Mỗi bước cho phép chọn một vị trí ~i~ nào đó và thực hiện SHIFT ký tự ~s_i~ hoặc ~t_i~ lên ~1~ bước, theo thứ tự: ~a \to b \to ... \to x \to y \to z \to a.~ Hỏi cần ít nhất mấy thao tác để làm cho hai chuỗi bằng nhau?

Input

Hai dòng gồm thông tin của hai chuỗi, độ dài giống nhau và không quá ~10^5.~

Output

Số bước tối thiểu cần thực hiện.

Sample input 1

abc
def

Sample output 1

9

Sample input 2

aa
az

Sample output 2

1

Giải thích: ta thực hiện SHIFT vị trí 1 ở ~s~ tất cả ~3~ lần, tương tự với vị trí ~2,3~ nên cần có ~3.3=9~ lần; trong VD2, ta thực hiện SHIFT vị trí 2 ở ~t~ tất cả ~1~ lần thì ~z \to a~.

Sau mùa code camp ở Tà Nung đáng nhớ, anh Trung đã về quê của mình trồng các cây thông. Bằng phương pháp đặc biệt, anh có thể trồng được các cây xứ lạnh đó ở vùng sông nước, để cứ mỗi chiều ra ngồi bên hàng thông để ngắm hoàng hôn và chill chill code. Tuy nhiên, một ngày nọ, có một Phú ông từ phương xa đến mua mua lại hàng thông với giá cao, đem về làm đồ nội thất, vì gỗ thông rất chắc chắn. Phú ông muốn mua một dãy liên tiếp các cây thông có chiều cao trung bình là ~k~, trong đó hàng thông của anh Trung thì có ~n~ cây với chiều cao ~h_1, h_2, ..., h_n~. Anh Trung cũng không ngại bán, vì bán xong thì trồng lại cũng không khó. Vì thế anh muốn chọn một dãy dài nhất có thể các cây thông của mình để bán cho Phú ông, hỏi dãy đó sẽ bắt đầu và kết thúc tại cây nào? Bạn hãy giúp anh Trung tính toán nhé: nếu không có cách nào bán được thì in ra ~0~, còn nếu có thì in ra vị trí bắt đầu ~L~ và độ dài dài nhất đó (nếu có nhiều cách chọn thì in ra ~L~ nhỏ nhất).

Input

Dòng đầu tiên gồm số nguyên ~n,k~ với ~1 \le n \le 10^5~ và ~1 \le k \le 10^9.~

Trong cac dòng tiếp theo là độ dài của các cây thông, giá trị nguyên dương không quá ~10^9.~

Output

Đáp số của bài toán: vị trí ~L~ và độ dài.

Sample input

4 5
2
4
5
6

Sample output

2 3

Subtasks

• Sub1 (40%): ~1≤ N ≤ 500~
• Sub2 (30%): ~1≤ N ≤ 5000~
• Sub3 (30%): ~1≤ N ≤ 10^5.~

Sau một buổi ôn luyên mệt mỏi thì ctanh2610dona và HoNhatTruong đã quyết định chơi một ván Caro để giải xì trét. Nhưng luật chơi hôm nay lạ hơn một tí sẽ vừa chơi kéo búa bao và cờ caro cùng một lúc, cụ thể hơn thì ai thắng 1 ván kéo búa bao sẽ được đánh thêm một dấu trên bàn caro. Sau một hồi chơi còn mệt hơn cả coding thì cả 2 đã quyết định về nhà ngủ nhưng vì quá mệt và hoa mắt nên ctanh2610dona và HoNhatTruong vẫn chưa biết ai thắng nên đã nhờ bạn xem giúp.

Biết rằng để thắng một ván Caro thì phải có ít nhất 5 quân liên tiếp đứng theo chiều ngang, dọc hoặc chéo.

Input

• Hai số nguyên ~N,M~ ~(5 \leq N,M \leq 10^3)~ , đại diện cho chiều cao và chiều rộng của bàn Caro.
• ~N~ dòng tiếp theo gồm ~M~ ký tự ~c_{i,j}~ ~(c_{i,j} ∈ \{X,O,.\})~ dại diện cho trạng thái của ô ~i,j~ trên bàn Caro là ~X~ đánh hoặc ~O~ đánh hoặc ~.~ là không ai cả

Output

• Nếu ~X~ thắng thì trả lời là X thang.
• Nếu ~O~ thắng thì trả lời là O thang.
• Nếu không ai thắng thì trả lời là Khong ai thang.
• Nếu cả hai đều thắng thì trả lời là Vo ly.

Sample Input

5 6
..OXX.
OO.X.O
OXXXO.
...X.O
OX.X..

Sample Output

X thang

Robert Duong Hoan là một đại kiện tướng cờ vua của CLB H3.2 với thành tích bất bại trong những lần tham gia hội thao toàn trường. Tuyệt kỹ của anh là: phế hậu tạo sát cục, chiếu hết trong vòng 10 nước, phong tỏa quân bắt tượng, chiếu rút bắt xe, ... đã là nỗi ám ảnh của các cao thủ. Với sự tin tưởng của người hâm mộ, anh đã được giao tổ chức một giải đấu rất đặc sắc nhân dịp kỷ niệm ngày 26/3. Luật chơi như sau:

• Nếu hiện có ~n~ chẵn kỳ thủ thì họ sẽ chia cặp và thi đấu loại trực tiếp, ai thua sẽ bị loại ngay; giải đấu sẽ tiếp tục với ~n/2~ kỳ thủ còn lại.
• Nếu hiện có ~n~ lẻ kỳ thủ thì họ sẽ thi đấu vòng tròn tính điểm (mỗi người đấu với tất cả những người kia), đấu tổng cộng ~n(n-1)/2~ ván (chú ý nếu ~n=1~ thì không cần đấu nữa); xong là kết thúc luôn.

Giả sử rằng không có trận nào hòa. Chẳng hạn: nếu có ~28~ kỳ thủ thì: lượt 1 họ đấu cặp với tổng ~14~ ván, còn ~14~ kỳ thủ; lượt 2 họ lại đấu cặp, thêm ~7~ ván và còn ~7~ kỳ thủ; lượt 3 do còn lẻ kỳ thủ nên họ đấu vòng tròn, thêm ~7(7-1)/2=21~ ván và kết thúc. Tổng cộng có ~14+7+21=42~ ván.

Robert được giao tổ chức đúng ~m~ ván đấu, nhưng bạn ấy thắc mắc rằng số kỳ thủ ít nhất cần mời để có số trận đấu như thế là bao nhiêu. Bạn hãy giúp bạn ấy với nhé.

Input

Một số nguyên dương ~m~ duy nhất là số ván đấu, với ~1 \le m \le 10^{18}.~

Output

Số kỳ thủ ít nhất cần mời. Nếu không tồn tại cách mời thi in ra ~-1.~

Sample input 1

42

Sample output 1

28

Sample input 2

1

Sample output 2

2

Anh Ali Vũ có nuôi một đàn gồm ~n~ con bò sữa, mỗi con có một chuồng riêng. Tuy nhiên, đàn bò của anh rất kén ăn nên con nào cũng ốm yếu (xem trong ảnh), còn bỏ thừa cỏ: con thứ ~i~ đang bỏ thừa ~a_i~ đơn vị cỏ, giả sử đây là các số nguyên dương. Vì thế, một ngày nọ, anh đã bỏ đói chúng vài ngày rồi mới cho ăn: với độ đói bụng ~k~ là số nguyên dương, bò sẽ nhai lượng cỏ là ~k~ vừa đủ để hết đói bụng. Sau khi được anh Vũ nạp lại cỏ, lũ bò lại khá kén chọn, mỗi con chỉ bắt đầu ăn cỏ nếu số cỏ của chúng có là chia hết cho ~k~ (để ăn vừa hết trong vài lần nhai tiếp theo, không bỏ thừa nữa), số cỏ nào không chia hết thì bò lại tiếp tục nhịn, không thèm ăn. Hãy giúp anh Vũ chọn ra số ~k~ hợp lý để có ít nhất ~2~ con bò sẽ ăn cỏ và tổng lượng cỏ ăn được của các con bò là nhiều nhất nhé.

Input

Dòng đầu tiên ghi số nguyên dương ~n~ với ~2 \le n \le 2.10^5~, trong dòng thứ hai, ghi ~n~ số nguyên dương nằm trong phạm vi ~1,2,...,2.10^6~ (các số này không nhất thiết phân biệt).

Output

Số cỏ lớn nhất mà các con bò sẽ ăn nếu như anh Vũ bỏ đói chúng thích hợp.

Sample Input 1

3
2 3 5

Sample Output 1

3

Giải thích: anh Vũ sẽ bỏ đói các con bò với độ bỏ đói là ~1~, khi đó sẽ có ba con cùng ăn với tổng lượng cỏ là ~1 \times 3 = 3~; còn nếu bỏ đói với độ bỏ đói là ~5~ thì chỉ có con cuối là ăn cỏ, không thoả mãn điều kiện.

Sample Input 2

5
7 28 4 8 12

Sample Output 2

16

Giải thích : anh Vũ sẽ bỏ đói các con bò với độ bỏ đói là ~4~, khi đó sẽ có ~4~ con bò cuối ăn cỏ với tổng lượng ăn được là ~4 \times 4 = 16~, nếu anh Vũ bỏ đói chúng với độ bỏ đói là ~7~ thì hai con đầu sẽ ăn cỏ nhưng tổng lượng ăn được chỉ là ~2 \times 7 = 14~.

Mô tả

Cho một số nguyên dương ~N~. Hãy đếm xem có bao nhiêu số nguyên dương ~X~ thỏa mãn các điều kiện:

• ~X~ không lớn hơn ~N~.
• ~X~ chia hết cho ~3~, hoặc chia hết cho ~4~, hoặc chia hết cho cả ~3~ và ~4~.
• ~X~ không chia hết cho ~5~.

Input

Một dòng duy nhất gồm một số nguyên dương ~N~ ~(1 \leq N \leq 10^{18})~.

Output

Một dòng duy nhất là đáp án của bài toán.

Ví dụ

Input

2024

Output

810

Vào một ngày hè rãnh rỗi Tèo nghĩ ra một trò chơi thú vị, tư duy và không kém phần sáng tạo. Cậu ta lấy một sợi dây có độ dài là ~k~ cm (Với đầu mút bên trái là vị trí ~0~ và đầu mút bên phải là vị trí ~k~) và bôi một lớp mật ong lên sợi dây và căng ra hai đầu.

Sau đó, Tèo chợp mắt một lát trong lúc chờ đợi lũ kiến bị dụ đến. Lúc tỉnh dậy, Tèo đã thấy kiến bu đầy trên sợi dây. Một số con đang đi về đầu mút bên phải của sợi dây trong khi số còn lại thì đang đi về đầu mút bên trái. Vì sợi dây khá mảnh nên hai con kiến sẽ không thể đi qua nhau. Vì vậy chúng có một quy luật khá đặc biệt là: Nếu hai con kiến đụng đầu nhau, chúng sẽ lập tức đổi hướng đi. Tèo đã đánh số các con kiến trên dây từ ~1~ đến ~n~ và ghi lại vị trí cũng như hướng di chuyển của nó tương ứng ~a_i~ (với ~|a_i|~ là vị trí của con kiến và nếu ~a_i<0~ thì con kiến đang đi sang phải còn ~a_i>0~ thì con kiến đang đi sang trái). Nếu một con kiến đi tới một trong hai đầu mút của sợi dây thì ngay lúc đó nó coi như đã rời khỏi sợi dây.

Tèo muốn đố bạn rằng tổng thời gian để con kiến cuối cùng rời khỏi sợi dây là giây thứ mấy? Biết rằng các con kiến di chuyển với vận tốc ~1~cm/s.

Ví dụ: Sợi dây dài ~k = 4~ và ~3~ con kiến ở vị trí ~1~, ~2~, ~3~ và đi về hướng đầu mút lần lượt là phải, trái, trái.

Tại giây ~0.5~, con kiến ~1~ chạm con kiến ~2~ tại vị trí ~1.5~ và chúng đổi chiều.

Tại giây ~1~, con kiến ~2~ chạm con kiến ~3~ tại vị trí ~2~ và chúng đổi chiều.

Tại giây ~2~, con kiến ~1~ chạm đến vị trí đầu mút trái. Đồng nghĩa với việc con kiến ~1~ rời khỏi sợi dây.

Tại giây ~3~, con kiến ~2~ chạm đến vị trí đầu mút trái và con kiến số ~3~ chạm vị trí đầu mút phải. Đồng nghĩa với việc con kiến ~2~ và con kiến ~3~ rời khỏi sợi dây.

Vậy thời điểm con kiến cuối cùng rời khỏi sợi dây là giây thứ ~3~.

InputFile

Dòng đầu tiên chứa một số nguyên dương ~t~ - Số lượng testcase

~T~ bộ dòng tiếp theo mỗi dòng gồm ~2~ dòng:

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ lần lượt là số con kiến và độ dài của sợi dây ~(~Với ~0 < n < k)~.

• Dòng tiếp theo chứa ~n~ số nguyên ~a_i~ là vị trí và hướng của những con kiến đó. Với ~|a_i|~ là vị trí của nó trên sợi dây và nếu ~a_i~ là âm thì nó đang đi về đầu mút bên phải hoặc ~a_i~ là dương thì nó đang đi về đầu mút bên trái ~(~Với ~0 < |a_i| < k~, ~1 \le i \le n)~. Luôn đảm bảo ~0 < |a_1| < |a_2| < ... < |a_n| < k~.

Luôn đảm bảo tổng số ~n~ của tất cả testcase luôn ~\leq 10^{6}~

OutputFile

Một dòng duy nhất là một số nguyên dương đại diện cho thời điểm con kiến cuối cùng rời khỏi dây.

Sample Input

1 
3 4
-1 2 3

Sample Outpt

3

Cách tính điểm:

• Subtest 1: (~50\%~ số điểm) Với ~n \le 10^2~ và ~k \le 10^3~.
• Subtest 2: (~30\%~ số điểm) Với ~n \le 10^3~ và ~k \le 10^6~.
• Subtest 3: (~20\%~ số điểm) Với ~n \le 10^6~ và ~k \le 10^{18}~.

Cho một hình tròn với bán kính ~R~, hỏi xác suất chọn ra 3 điểm trên đường tròn để tạo thành 1 tam giác sao cho tam giác đó chứa tâm hình tròn là bao nhiêu ?

Ví dụ minh hoạ :

Input

• Số nguyên duy nhất là ~R~ ~(1 \leq R \leq 10^9)~ , đại diện cho bán kính hình tròn.

Output

• Xác suất để tam giác chứa tâm hình tròn (làm tròn tới 2 chữ số thập phân).

Sample Input

4

Sample Output

0.25