Bạn Trung tham gia một khóa học thuật toán cấp tốc cùng chuyên gia, phải làm tổng cộng ~n~ bài kiểm tra với điểm trung bình mà bạn tính được là ~m~ (với ~m~ nguyên dương). Biết rằng chuyên gia sẽ chấm mỗi bài với mức điểm từ ~a~ đến ~b~ (điểm số cũng toàn là số nguyên). Do học hành vất vả nên có thể Trung đã tính toán có sai sót. Hãy giúp bạn ấy kiểm tra xem rằng tính toán có hợp lý hay không, và nếu đúng thì cho biết điểm của bài kiểm tra lớn nhất mà bạn có thể đạt được với thông tin đó là bao nhiêu?

Input

Một dòng duy nhất gồm bốn số ~n, m, a, b~ là các số nguyên dương trong miền từ ~1~ đến ~1000~, cho biết ~a \le b.~

Output

Nếu kết quả không hợp lý thì in ra ~-1~, còn nếu hợp lý thì in ra điểm lớn nhất mà bạn có thể nhận được.

Sample input 1

2 4 1 10

Sample output 1

7

Sample input 1

4 100 1 10

Sample output 1

-1

Giải thích trong VD1, ta thấy bạn có thể được điểm là 1 và 7 thì có trung bình là 4; còn trong VD2, ta thấy khoảng điểm là 1 đến 10 thì không thể có điểm trung bình là 100 được.

Câu chuyện trong buổi tối hôm nay kể về một em mèo mướp tội nghiệp. Vì ghen tị với độ dễ thương của em mèo nên vào một ngày nọ, mụ phù thủy độc ác đã nhốt em vào mê cung hình vuông kích thước ~n \times n~ mà khó tìm được lối thoát. Các vị trí trong mê cung được chia thành các ô vuông, mỗi ô vuông có thể là khoảng trống, hoặc là cạm bẫy. Em mèo được đặt vào một ô nào đó, xung quanh em có thể có toàn là cạm bẫy. Do hoang mang nên em mèo khi bắt đầu chạy thì chỉ biết chạy thẳng theo 1 trong các hướng: trái, phải, lên, xuống chứ không biết rẽ lần nào nữa. Hãy tính xem em mèo có thoát ra được mê cung hay không, với số bước ít nhất là bao nhiêu nhé? Chú ý rằng nếu em mèo đang ở biên của mê cung thì em chỉ cần nhảy thêm ~1~ bước là thoát khỏi, vì mê cung không có tường.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~3 \le n \le 100.~ Trong các dòng tiếp theo là mô tả cho thông tin các ô trong mê cung, ký hiệu ô trống bởi dấu O còn ô có cạm bẫy là X, chỉ có đúng một ô chứa ký hiệu M, chỉ vị trí của em mèo mướp.

Output

Số bước ngắn nhất để thoát khỏi mê cung nếu chỉ chạy thẳng, hoặc in ra ~-1~ nếu không có cách nào thoát khỏi.

Sample input 1

3
XOX
OMX
OXX

Sample output 1

2

Sample input 2

3
OXO
XMX
OXO

Sample output 2

-1

Sample input 3

4
OOXX
XOMX
OXOX
XXXX

Sample output 3

-1

Giải thích. trong VD1, em mèo có thể đi thẳng lên hoặc đi rẽ sang trái thì đều thoát được; còn trong VD2, xung quanh em đều là cạm bẫy nên không có lối thoát; trong VD3, em mèo dù có một cách thoát nhưng do em phải rẽ ít nhất một lần mới ra được và em cũng không thể thoát.

Trong một khu phố, người ta có thiết kế một hệ thống thoát nước ngầm dưới mặt đất bao gồm ~N~ chốt được đánh số ~1,2,\ldots ,N~ cùng ~M~ đường ống hai chiều nối giữa ~N~ cặp chốt có dạng ~(i,j)~ với ~i\ne j~ và ~1\le i,j\le N.~ Ban đầu các chốt trong hệ thống được đóng nắp và nước bên ngoài không thể chảy vào. Khi có một chốt ~X~ nào đó được mở nắp để nước chảy vào, dòng nước sẽ chảy đến các chốt khác có đường ống nối với ~X~ (vì dòng nước chảy ngầm nên khi đó cho dù các chốt này có được mở nắp hay không thì nước vẫn chảy đến được); nước sẽ từ các chốt đó lại chảy tiếp thông qua các đường ống và lan sang một phần của hệ thống để thoát bớt đi. Bây giờ người ta muốn mở nắp khóa của không quá ~K~ chốt trong hệ thống với ~1\le K\le N~ sao cho dòng nước bên ngoài có thể chảy vào hệ thống thông qua các chốt đó và lan ra càng nhiều chốt trong hệ thống càng tốt. Ngoài ra, để hệ thống ổn định thì các chốt được mở nắp khóa phải có cùng số lượng đường ống nối vào. Hỏi số lượng chốt nhiều nhất mà nước có thể chảy đến là bao nhiêu?

Input

Dòng đầu tiên có chứa số ~N,M,K~ với ~1\le K\le N\le {{10}^{5}}~ và ~0\le M\le \min \left\{ \frac{n(n-1)}{2},{{10}^{5}} \right\}~. Trong ~M~ dòng tiếp theo, mỗi dòng có một cặp số ~i,j~ cho biết có đường ống nước nối giữa chốt ~i~ và ~j,~ các cặp số ~(i,j)~ này phân biệt nhau giữa các dòng.

Output

In ra một số nguyên duy nhất là số lượng chốt nhiều nhất mà nước có thể chảy đến khi mở nắp khóa của không quá ~K~ chốt mà các chốt được mở này phải có cùng số lượng đường ống nối vào.

Sample input 1

6 3 3
1 2
2 3
4 5

Sample output 1

5

Sample input 2

6 0 5

Sample output 2

5

Giải thích: trong VD1, ta chọn chốt 1 và chốt 4 là hai chốt mà có cùng 1 đường ống nối vào. Ở chốt 1, nước sẽ chảy đến: ~1, 2, 3~; ở chốt 4, nước sẽ chảy đến: ~4, 5~. Tổng cộng nước chảy đến được ~3 + 2 = 5~ chốt, đây là số lượng chốt lớn nhất mà nước có thể chảy đến; trong VD2, ta thấy cả ~6~ chốt đều có cùng số lượng đường ống (là ~0~) nối ra, nên ta có thể chọn chốt nào cũng được, và do được chọn tối đa ~5~ chốt nên kết quả cũng là ~5.~

Một trong các team ICPC mạnh nhất năm 2025 của IUH có các thành viên tên là: Tài, Lộc, Ban. Để lấy hên cho team, thầy Tina bèn đặt "nghệ danh" cho các thành viên, mỗi người lót thêm cùng một chữ Phát cho hay, học hành mau tiến bộ. Cụ thể là: Phát Tài, Phát Lộc, Phát Ban. Tuy vậy, các bạn này học hành độc lập nhau và ít chia sẻ tài liệu cho nhau. Một dịp nọ được đi code camp ở một vùng quê xa, các bạn ngồi mỗi một góc và tọa độ được cho trước. Các bạn được thầy Tina phát cho cùng một chiếc đèn bàn với độ sáng giống nhau, có thể chiếu một vùng sáng hình tròn với cùng bán kính ~R~. Vì biết ý của các học trò, thầy chọn bán kính đó lớn nhất có thể sao cho không có vùng sáng nào của đèn hai bạn nào trong team đó là cắt nhau (chạm vào thì vẫn được). Hãy giúp thầy tính ra được bán kính đó nhé.

Input

Tọa độ chỗ ngồi của các bạn, gồm ~6~ số nguyên có trị tuyệt đối không vượt quá ~10^6~ là: ~x_1, y_1, x_2, y_2, x_3, y_3.~ Cho biết rằng không có hai tọa độ nào trùng nhau.

Output

Bán kính lớn nhất cần tìm, kết quả làm tròn đến ~2~ chữ số thập phân.

Sample input

0 0 2 0 0 2

Sample output

1.00

Giải thích: bạn có thể vẽ hình ra cho dễ tưởng tượng.

Anh Mạnh là chuyên gia số học của CLB H3.2, cụ thể là về mảng tử vi lý số, coi bói đoán đường tình duyên. Vào một ngày gặp gỡ các bé K19, Mạnh đã cho một team ICPC ba người xem thử tài nghệ bói toán của mình. Mạnh cho các bạn này một số nguyên dương ~n~ rồi yêu cầu mỗi người chọn ra một ước dương tùy ý của ~n~, các ước phải phân biệt nhau sao cho tổng các số của hai bạn bất kỳ đều phải chẵn. Dựa vào các ước số đó, Mạnh có thể luận ra được nhiều quẻ rất hay, chẳng hạn bói xem có hai người nào đó cùng team là yêu nhau hay không, hay người team này yêu team khác, ... nói chung có nhiều chuyện để bói. Nhưng trước hết, bạn hãy giúp team này đếm xem có bao nhiêu cách chọn các bộ ba như thế nhé?

Input

Một dòng duy nhất gồm số nguyên dương ~n~ với ~1 \le n \le 10^9.~

Output

Số bộ ba cần tìm.

Sample input

15

Sample output

4

Giải thích: ta thấy số ~15~ có các ước là ~1,3,5,15~, ta chọn ra ba số tùy ý trong đó thì đều thỏa mãn, chẳng hạn chọn ~(1,3,5)~ thì tổng của các cặp số sẽ là ~4,8,6~ đều chẵn. Số lượng bộ ba cần tìm là ~4.~ Chú ý nếu không có bộ nào thỏa thì in ra ~0~.

Mong ước của anh ...

Chắc các bạn còn nhớ bài toán Mong ước của tớ trong contest Thử thách của Luna. Hôm nay chúng ta có một phiên bản khác. Sau những ngày rèn luyện với ICPC thì anh Phú đã về trên núi để tu luyện thêm cùng đàn cầy tơ. Anh có tất cả ~L~ em cầy tơ mà mỗi em có một độ ngon, à nhầm, cân nặng nhất định, là một số nguyên dương. Anh cần chia chúng thành ~G~ nhóm mà mỗi nhóm có số cầy tùy ý rồi nhốt vào chuồng để các em không chạy lung tung. Chi phí để nuôi mỗi chuồng bằng với tổng cân nặng nhân với số con trong chuồng đó. Chẳng hạn nếu có một chuồng có các em cầy có cân nặng: ~1,2,3~ thì chi phí nuôi là ~3(1+2+3)=18.~ Hãy giúp anh Phú nghiên cứu tìm ra cách chia sao cho chi phí nuôi nhốt là ít nhất nhé, chú ý rằng các em cầy phải chia trọn vẹn vào chuồng chứ không được cắt ra thành nhiều phần.

Input

Dòng đầu tiên gồm số nguyên dương ~L, G~ với ~1 \le L \le 8000~ và ~1 \le G \le 800.~

Mỗi dòng tiếp theo trong ~L~ dòng, ta có một số nguyên dương không vượt quá ~10^9.~

Output

Đáp số của bài toán.

Sample input

6 3
11
11
11
24
26
100

Sample output

299

Giải thích cách chia tối ưu là ~(11,11,11), (24,26), (100)~ với chi phí ~3.(11+11+11) + 2.(24+26)+ 1.100=299.~

Hệ trục tọa độ ~Oxy~ chia mặt phẳng thành bốn phần: góc trên bên phải là góc phần tư thứ ~I~, cứ thế đi ngược chiều kim đồng hồ, ta sẽ có góc phần tư thứ ~II, III, IV~. Lần lượt cho vào các góc phần tư đó các điểm phân biệt (không nằm trên hai trục tọa độ) với số lượng là ~a,b,c,d~. Hãy tính xem có thể có nhiều nhất bao nhiêu tam giác với ba đỉnh (mỗi đỉnh ở 1 phần tư khác nhau) lấy từ các điểm đã cho và chứa gốc tọa độ ~O~ bên trong?

Input

Các số nguyên dương ~a,b,c,d~ không vượt quá ~10^6.~

Output

Một số nguyên duy nhất là đáp số của bài toán (cho biết rằng giá trị này vẫn tính được trong kiểu Int64).

Sample input

1 1 1 1

Sample output

2

Trong CLB lập trình H3.2, có hai bạn Hà và Vũ. Một ngày nọ, bạn Hà muốn gửi một thông điệp cho bạn Vũ nhưng vì hai bạn rất nhạy cảm với sự an toàn thông tin, sợ người khác biết nên đã bỏ thời gian một ngày để mã hóa nó. Thông điệp đó có thể coi là một từ gồm các ký tự tiếng Anh viết in thường và có độ dài không quá ~10^5.~ Với mỗi từ ~s~ như thế, Hà tiến hành ba bước như sau (theo đúng thứ tự):

• Hoán đổi các vị trí của ký tự có trong từ ~s~.
• Thêm một vài ký tự đằng trước ~s~ (có thể không thêm gì cả).
• Thêm một vài ký tự đằng sau ~s~ (có thể không thêm gì cả).

Sau khi mã hóa xong được thông điệp ~r~, Hà sẽ gửi cho bạn Vũ đọc. Do thực hiện gấp gáp nên Hà sợ rằng có bị nhầm lẫn và muốn kiểm tra xem chuỗi ~r~ có thể nhận được từ chuỗi ~s~ thông qua các bước mã hóa ở trên hay không. Bạn hãy giúp Hà thực hiện điều đó nhé.

Input

Dòng đầu tiên là ~T~, cho biết số lượng bộ tests, trong đó ~1 \le T \le 5~. Mỗi hai dòng tiếp theo sẽ có thông tin của: chuỗi ~r~, thông điệp đã mã hóa mà bạn Vũ nhận được, độ dài không quá ~10^5~, chuỗi ~s~, thông điệp gốc của bạn Hà, độ dài không quá ~10^5.~

Output

Ứng với mỗi test, in ra "YES" nếu ~r~ có thể nhận được từ ~s~ thông qua bước mã hóa trên. Ngược lại thì in ra "NO".

Sample input 1

1
abcd
cb

Sample output 1

YES

Sample input 2

1
aabbbbb
aba

Sample output 2

YES

Sample input 3

1
abcxyz
acz

Sample output 3

NO

Giải thích: Ở VD 1, ta thực hiện qua các bước như sau: ~cb \to bc \to abc \to abcd~. Ở VD 2, ta thực hiện qua các bước như sau: ~aba \to aab \to aab \to aabbbbb~. Ở VD 3, ta có thể chỉ ra được rằng ~abcxyz~ không sinh ra từ ~acz~.

Sau những ngày nuôi quân miệt mài, thầy Tina cũng đã có được một dàn chiến binh IUH hùng hậu. Mỗi người có một chỉ số chiến đấu biểu diễn bởi một số nguyên dương không vượt quá ~10^9.~ Các chiến binh này chỉ chờ ngày để chiến đấu tại đấu trường quốc gia vào tháng 11 sắp tới. Hiện tại, các chiến binh đang đứng thành một hàng dọc để được thầy Tina kiểm tra sức khỏe. Tuy nhiên, để biểu thị sức mạnh trước các trường khác thì thầy Tina muốn cho cho bạn có chỉ số sức mạnh càng cao thì càng phải được đứng trước. Bằng cách dùng không quá ~k~ lần swap hai bạn liền kề, hỏi thầy có thể tạo thành một dãy chỉ số chiến đấu mới với thứ tự từ điển lớn nhất là bao nhiêu?

Input

Dòng đầu tiên gồm số nguyên dương ~n, k~ trong đó ~1 \le n \le 10^5~ và ~0 \le k \le 10^9.~

Dòng tiếp theo gồm ~n~ số nguyên cho biết chỉ số chiến đấu của các chiến binh, các số này không quá ~10^9~ và không nhất thiết phân biệt.

Output

In ra danh sách chỉ số chiến đấu mới sau khi đã sắp xếp.

Sample input 1

3 2
1 2 3

Sample output 1

3 1 2

Sample input 2

4 2
3 2 2 1

Sample output 2

3 2 2 1

Giải thích: trong VD1, ta sẽ đổi ~(1,2,3) \to (1,3,2) \to (3,1,2)~, còn với VD2, do bộ ~(3,3,2,1)~ có thứ tự từ điển lớn nhất rồi nên không cần phải đổi gì nữa.

Kỳ thi Olympic Tin học ICPC năm nay là lần đầu mà team TriplẻK được tham gia, các bạn rất hào hứng. Bên cạnh việc luyện tập thì mỗi đêm, công việc chính của các bạn là nghiên cứu các địa điểm du lịch để đi chơi cho thỏa thích. Huế có nhiều nơi để tham quan như: Đại Nội, lăng tẩm các vị vua, cầu Tràng Tiền, và đặc biệt trong đó có Kinh thành Huế, nơi đóng đô của triều Nguyễn trong gần 150 năm. Khu di tích có ~n~ địa điểm tham quan được đánh số từ ~1~ đến ~n~ và điểm thứ ~i~ có tọa độ ~(x_i, y_i)~ được kết nối với nhau bằng một số con đường một chiều. Vì địa hình đặc thù nên những bậc tiền bối chỉ xây dựng đường đi từ địa điểm ~i~ đến ~j~ nếu như ~x_i > x_j~ và ~y_i < y_j~. Để chuẩn bị kỹ lưỡng cho việc du lịch kinh thành một cách hiệu quả, team TriplẻK muốn tính xem với mỗi số ~1 \le k \le n~ thì có bao nhiêu hành trình tham quan đi theo những con đường có sẵn mà qua đúng ~k~ điểm tham quan (hai con đường là khác nhau nếu có một địa điểm có trên đường này mà không có trên con đường kia). Team đang code để giải thử nhưng toàn bị TLE, WA, RTE, ..., nhờ các bạn hỗ trợ giúp nhé.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 2000~.

Dòng thứ hai là ~n~ số nguyên ~x_1, x_2, ..., x_n~ và dòng cuối là ~n~ số nguyên ~y_1, y_2, ..., y_n~. Các số này nguyên và có giá trị tuyệt đối không quá ~10^9.~

Output

In ra ~n~ số nguyên không âm, trong đó số thứ ~k~ là số lượng con đường đi qua ~k~ địa điểm mà team TriplẻK muốn đi, lấy modulo ~10^9+7.~

Sample input

6
3 2 6 4 5 1
5 5 6 2 1 4

Sample output

6 7 3 0 0 0

Giải thích:

• Các hành trình gồm 1 điểm tham quan: ~(1); (2); (3); (4); (5); (6).~
• Các hành trình gồm 2 điểm tham quan: ~(4, 1); (4, 2); (4, 6); (5, 1); (5, 2); (5, 4); (5, 6).~
• Các hành trình gồm 3 điểm tham quan: ~(5, 4, 2); (5, 4, 6); (5, 4, 1).~
• Không có hành trình thoả mãn đi qua 4, 5 hoặc 6 điểm tham quan