Muối được thầy giao cho cả đống bài tập khó nhưng làm mãi mà không xong nên Muối quyết định đi ngủ. Ấy vậy mà trong giấc mơ, Muối lạc vào trong thế giới Ai Cập cổ đại, trước mặt Muối là Cleopatra mà trước giờ chỉ xuất hiện qua những trang truyện. Muối và Cleopatra nhanh chóng kết thân và chơi đùa rất vui vẻ. Thấy Muối là một người thông minh và có tố chất làm vua một nước nên Cleopatra xây cho Muối một Kim Tự Tháp, điểm đặc biệt là Kim Tự Tháp này có đáy là một hình vuông và có một mặt bên là tam giác vuông. Vốn dĩ là một người cầu toàn nên theo Cleopatra, một Kim Tự Tháp đẹp thì mặt bên là tam giác vuông phải thỏa mãn yêu cầu:

• Hiệu của cạnh huyền với ~1~ cạnh góc vuông là ~X~.
• Tổng của ~2~ cạnh góc vuông là ~Y~.

Biết rằng trong ~2~ cạnh góc vuông luôn có ~1~ cạnh có độ dài ngắn hơn cạnh còn lại. Hãy giúp Muối xác định độ dài các cạnh để lấy le với Cleopatra.

Input

• Một dòng chứa số nguyên ~X~ và ~Y~ lần lượt là hiệu của cạnh huyền với cạnh góc vuông và tổng của ~2~ cạnh góc vuông (~X~, ~Y~ ~\leq~ ~10^6~).

Output

• Một dòng chứa số thực ~a~, ~b~ và ~c~ lần lượt là độ dài cạnh góc vuông ngắn, cạnh góc vuông dài và cạnh huyền. Nếu tồn tại nhiều bộ ba ~a~, ~b~ và ~c~ khác nhau thỏa mãn yêu cầu của Cleopatra thì in ra một bộ ba bất kỳ. Kết quả in ra gồm ~9~ chữ số thập phân.

Sample Input

2 7

Sample Output

3.000000000 4.000000000 5.000000000

Subtask

• ~40\%~ số test có ~a~, ~b~, ~c~ là số nguyên.
• ~60\%~ số test còn lại không có điều kiện gì thêm.

Giải thích

Ta có: ~a~ = ~3.000000000~, ~b~ = ~4.000000000~, ~c~ = ~5.000000000~, bộ ba này tạo thành tam giác vuông và thỏa điều kiện:

~X~ = ~c - a~ = ~5.000000000 - 3.000000000~ = ~2.000000000~

~Y~ = ~a + b~ = ~3.000000000 + 4.000000000~ = ~7.000000000~

"Một nụ cười luôn hé, thế giới vẫn quay

Còn tôi vẫn nơi đây đưa bàn tay lên trời xanh

Ôm trọn vào lòng một khoảng trời nhỏ bé

Giữa những khát khao, cơ mà chỉ tôi với riêng tôi

Đêm nằm nghe một bài ca, về tình yêu, ôi chán ngắt"

Vốn là một người cô đơn, Muối ngân nga bài ca bất hủ này cả ngày và trong suy nghĩ Muối luôn ao ước một bờ vai. Trời không phụ lòng người thế nên ở trong giấc mơ Muối may mắn là người đàn ông duy nhất trên thế giới giữa vô vàn người phụ nữ. Hàng ngày, Muối luôn phải đau đầu lên danh sách những người phụ nữ mình đi chơi cùng nhưng chắc chắn là Muối không đủ sức để đi chơi hết với ~7~ tỷ người con gái trong thế giới này.

Anh lên danh sách chọn ra ~M~ người có độ xinh đẹp theo Muối đánh giá là ~a_i~, trong ~M~ người này Muối phải chọn ra đúng ~N~ người (~N \leq M~) có hiệu độ xinh đẹp giữa cô xinh nhất và cô kém xinh nhất không quá ~K~, vốn dĩ là một người yêu cái đẹp nên Muối muốn tổng độ xinh đẹp phải là lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên ~M~, ~N~ và ~K~.
• Dòng thứ hai chứa ~M~ số nguyên dương ~a_i~.

Output

• Dòng duy nhất chứa số nguyên là đáp án, nếu không tồn tại đáp án in ra ~-2~.

Sample Input

3 2 1
1 2 3

Sample Output

5

Subtask

• ~20\%~ số test có ~1 \leq N \leq M \leq 21~, ~0 \leq K, a_i \leq 10^5~
• ~80\%~ số test có ~1 \leq N \leq M \leq 10^6~, ~0 \leq K, a_i \leq 10^8~

Giải thích

Ta có thể chọn ~N~ người từ ~M~ người có độ xinh đẹp như sau: ~[1,2]~, ~[2,3]~, ~[3,1]~

Loại ~[1,3]~ vì (độ xinh đẹp lớn nhất) - (độ xinh đẹp nhỏ nhất) = ~3~ - ~1~ = ~2~ ( > ~K~ = ~1~ )

Ta chỉ có thể chọn ~[1,2]~ và ~[2,3]~ và cuối cùng chọn ~[2,3]~ vì có tổng độ xinh đẹp lớn nhất.

Trong giấc mơ vào năm ~2121~, mạng Internet giờ đây tràn ngập virus, mật độ virus dày đặc tới mức chỉ cần mở Google lên cũng có khả năng dính virus! Đương nhiên máy tính sinh ra không phải chỉ để chơi Pikachu. Là một nhà bảo mật hàng đầu vũ trụ, Muối lại có một khuyết điểm là rất thích chơi game crack, dù đó là game online! Muối biết rằng một ngày đẹp trời mình có thể bị con virus bê hết đống tài liệu học tập đi nên đã viết ra một phần mềm bảo mật tầm thiên hà khó bị phá vỡ.

Là người nhiều khuyết điểm, Muối còn bị chứng hay quên đến mức không thể nhớ nổi mật khẩu phần mềm này. Muối chỉ nhớ rằng mật khẩu của mình là số nhỏ nhất biểu diễn dưới dạng tứ phân có độ dài là ~S~, chứa ~A~ chứ số ~1~, ~B~ chữ số ~2~, ~C~ chữ số ~3~ ~(A + B + C \leq S)~. Đương nhiên mật khẩu tầm thường như vậy thì sẽ rất dễ bị hack nên mật khẩu của Muối luôn có dạng đối xứng. Hãy giúp Muối tìm ra mật khẩu. Biết rằng mật khẩu dạng tứ phân không bao gồm những chữ số ~0~ vô nghĩa ở đầu.

Input

• Dòng thứ nhất gồm số nguyên ~S~ ~(1 \leq S \leq 10^6)~.
• Dòng thứ hai bao gồm số nguyên không âm ~A~, ~B~ và ~C~.

Output

• Dòng duy nhất in ra phần dư của số thỏa mãn ở dạng thập phân trong phép chia cho ~727355608~. Nếu không tồn tại đáp án in ra Bedao!

Sample Input

3
2 1 0

Sample Output

25

Subtask

• ~10\%~ số test có ~1\leq S \leq 10~
• ~30\%~ số test có ~1 \leq S \leq 30~
• ~60\%~ số test còn lại có ~1 \leq S \leq 10^6~

Như một đoạn phim, các giấc mơ của Muối biến hóa liên tục, giờ đây Muối là một bài thủ kỳ cựu trong trò Yugioh. Không phải ngẫu nhiên người ta gọi Muối là "Vua Trò Chơi". Một ngày đẹp trời, Muối đã đụng độ chân ái của đời mình, đó chính là HienJeony. Bản tính vốn toxic nhưng HienJeony đánh bộ bài còn toxic hơn khiến Muối phải khốn đốn mặc dù đã phòng thủ rất quyết liệt. Đương nhiên Muối không phải Yugi trong truyện nên không thể sử dụng "sức mạnh tình bạn" được nhưng Muối chắc chắn là nhân vật chính trong giấc mơ của mình nên Muối đã bốc được một lá Spell có thể giúp Muối lật kèo, chuyển bại thành thắng.

Lá Spell cho phép Muối lấy ~n~ lá bài quái thú có trong bộ bài lên tay, quái thú thứ ~i~ có sức tấn công là ~a_i~. Muối phải xếp bài nhanh nhất có thể sao cho các quái thú có sức tấn công là một số nguyên tố bé hơn hoặc bằng ~X~ được đặt cạnh nhau trong bộ bài. Biết rằng mỗi bước sắp xếp tương ứng với việc đổi chỗ ~2~ lá bài bất kỳ trong ~n~ lá.

Nếu Muối không thể xếp bài nhanh nhất thì Muối sẽ thua và tổn hại tên gọi "Vua Trò Chơi", ngược lại HienJeony sẽ thua và phải bỏ tính toxic suốt đời. Hãy tính giúp Muối số bước sắp xếp ít nhất để Muối có thể thắng. Biết rằng trong bộ bài của Muối có những lá bài vô dụng cực kỳ.

Input

• Dòng thứ nhất gồm ~2~ số nguyên dương ~n~ và ~X~ ~(1 \leq n, X \leq 10^6)~.
• Dòng thứ hai gồm ~n~ số nguyên mô tả các lá bài ~a_i~ ~(|a_i| \leq 10^9)~.

Output

• Một dòng duy nhất in ra số bước sắp xếp ít nhất thỏa mãn.

Sample Input

10 10
2 1 5 4 7 8 5 12 3 10

Sample Output

2

Subtask

• ~50\%~ số test có ~1 \leq n \leq 10^3~, ~1 \leq X \leq 10^4~, ~|a_i| \leq 10^4~.
• ~50\%~ số test có ~1 \leq n, X \leq 10^6~, ~|a_i| \leq 10^9~.

Giải thích

Cần ít nhất 2 bước để sắp xếp thỏa mãn là thực hiện ~swap(a_1, a_4)~ và ~swap(a_6,a_9)~.

Tỉnh dậy sau một giấc ngủ sảng khoái, Muối cảm thấy tràn đầy năng lượng và bắt tay vào làm đống bài tập thầy cho. Nhưng đang hay thì đứt dây đàn, biết rằng Muối không phải học sinh tầm thường nên thầy giáo cho Muối một bài tập vô cùng khó, bài tập như sau:

Cho tập ~A~ ban đầu là rỗng và ~Q~ truy vấn, mỗi truy vấn có dạng:

• ~1~ ~v~: Nếu trong ~A~ chưa có ~v~ thì thêm ~v~ vào ~A~, ngược lại xóa ~v~ khỏi ~A~.

• ~2~ ~x~: Tìm tập ~B~ có kích thước nhỏ nhất sao cho với mỗi ~Y~ thuộc ~[1,x]~ đều tồn tại tập con của ~B~ có tổng bằng ~Y~, biết rằng các phần tử của tập ~B~ đều thuộc ~A~ và cùng một phần tử của tập ~A~ có thể xuất hiện nhiều lần trong tập ~B~.

Input

• Dòng đầu tiên gồm số nguyên ~Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ~1~ truy vấn có dạng: ~1~ ~v~ hoặc ~2~ ~x~ ứng với truy vấn loại ~1~ hoặc loại ~2~

Output

• Ứng với mỗi truy vấn loại ~2~, in ra kích thước nhỏ nhất của tập ~B~ thỏa mãn yêu cầu. (Mỗi truy vấn in ra trên một dòng)
• Trong trường hợp không tìm được tập ~B~ thỏa mãn in ra ~-1~.

Sample Input

8
1 1
2 200 
1 42
2 200
1 84 
2 200
1 42
2 200

Sample Output

200
45
44
85

Subtask

• ~100\%~ số test có ~Q=200000~ và ~0 \le x,v \le {10}^{18}~

BÀI NÀY DÀNH CHO SMURF