Xét trò chơi xếp hình chữ nhật với các que diêm như sau: Có ~n~ que diêm, que thứ ~i~ có độ dài ~d_i~. Người chơi cần chọn ra 4 que diêm để có thể xếp thành một hình chữ nhật, giả sử ~4~ que diêm mà người chơi chọn có độ dài lần lượt là ~a, b, c, d(a \leq b \leq c \leq d)~, khi đó có thể xếp được thành một hình chữ nhật nếu ~a=b~ và ~c=d~. Người chơi xếp được hình chữ nhật có diện tích càng lớn sẽ càng được điểm cao.

Yêu cầu: Cho ~d_1, d_2, \ldots, d_n~ là độ dài của ~n~ que diêm. Hãy tìm cách chọn ~4~ que diêm để xếp được thành một hình chữ nhật có diện tích lớn nhất.

Dữ liệu:

• Dòng đầu tiên ghi số nguyên dương ~K~ là số lượng bộ dữ liệu. Tiếp đến là ~K~ nhóm dòng, mỗi nhóm tương ứng với một bộ dữ liệu có cấu trúc như sau:
  • Dòng thứ nhất ghi một số nguyên dương ~n~;
  • Dòng tiếp theo chứa ~n~ số nguyên dương ~d_1, d_2, \ldots, d_n\left(d_i \leq 10^9\right)~.

Kết quả:

• Ghi ra gồm ~K~ dòng, mỗi dòng ghi một số nguyên là diện tích của hình chữ nhật xếp được tương ứng với bộ dữ liệu trong file dữ liệu vào (ghi -1 nếu không tồn tại cách chọn nào xếp được hình chữ nhật).

Ví dụ:

Sample Input

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

Sample Output

5
-1

Ràng buộc:

• Có ~40\%~ số test, ứng với ~40\%~ số điểm của bài có ~n \leq 30~;
• Có ~40\%~ số test, ứng với ~40\%~ số điểm của bài có ~n \leq 3000~;
• Có ~20\%~ số test còn lại, ứng với ~20\%~ số điểm của bài có ~n \leq 300000~.

Hãng cung cấp dịch vụ điện thoại ~XYZ~ khuyến khích nhiều người đăng kí thuê bao bằng cách: Khi khách hàng đến đăng ký thuê bao thì sẽ được cấp hai số may mắn là số nguyên dương ~n~ và ~k~, hãng sẽ khuyến mại người đó một số tiền nhận được từ số ~n~ sau khi xóa đúng ~k~ chữ số (~k~ nhỏ hơn số chữ số của ~n~).

Nam vừa mới đăng ký thuê bao của hãng và được cung cấp hai số ~n~ và ~k~, bạn hãy giúp Nam xóa đi ~k~ chữ số của số ~n~ để số nhận được là lớn nhất.

Dữ liệu:

• Dòng thứ nhất là số ~n~ (số chữ số của ~n \leq 10^5~);
• Dòng thứ hai là số ~k~ (~k \lt n~).

Kết quả:

• Một dòng duy nhất là số lớn nhất có được sau khi xóa đi ~k~ chữ số của ~n~.

Ví dụ:

Sample Input 1

58816
2

Sample Output 1

886

Sample Input 2

2357111317192329
6

Sample Output 2

7317192329

Ràng buộc:

• Có ~30\%~ số test, ứng với ~30\%~ số điểm của bài có số chữ số của ~n \leq 100~;
• Có ~30\%~ số test, ứng với ~30\%~ số điểm của bài có số chữ số của ~n \leq 255~;
• Có ~40\%~ số test còn lại, ứng với ~40\%~ số điểm của bài có số chữ số của ~n \leq 10^5~.

Cho phương trình: $$ x^2+S(x) x-N=0 $$ Trong đó ~x, N~ là những số nguyên dương, ~S(x)~ bằng tổng các chữ số của ~x~.

Yêu cầu: Cho trước giá trị ~N~. Hãy tìm giá trị ~x~ nhỏ nhất thỏa mãn phương trình trên.

Dữ liệu:

• Gồm một số nguyên duy nhất ~N\left(1 \leq N \leq 10^{18}\right)~.

Kết quả:

• Ghi ra một số nguyên duy nhất ~x~ nhỏ nhất thỏa mãn phương trình. Trong trường hợp không tìm được ~x~ thì ghi ra ~-1~ .

Ví dụ:

Sample Input 1

2

Sample Output 1

1

Sample Input 2

4

Sample Output 2

-1

Ràng buộc:

• Có ~40 \%~ số test ứng với ~40 \%~ số điểm của bài có ~N \leq 10^4~;
• Có ~30 \%~ số test khác ứng với ~30 \%~ số điểm của bài có ~N \leq 10^{10}~.
• Có ~30 \%~ số test còn lại ứng ~30 \%~ số điểm của bài có ~N \leq 10^{18}~.

Steve từ nhỏ đã thích sách báo và có lúc còn mơ ước trở thành tổng biên tập của một nhà xuất bản. Dịp may đã đến khi Steve được nhận vào làm việc ở một tòa báo. Công việc đầu tiên được giao là bố trí thông tin cho một cửa sổ quảng. Cửa sổ quảng cáo có hình chữ nhật kích thước ~{w} \times {h}~. Nội dung quảng cáo có ~{n}~ từ. Khi in trong font chuẩn từ thứ ~{i}~ có độ dài ~{a}_{i}~ và độ cao là ~{b}_{i}~. Các từ phải ghi theo đúng trình tự từ trên xuống dưới và từ trái qua phải. Người ta muốn chữ phải ghi càng to càng tốt (nhưng vẫn phải nằm trong cửa sổ). Các chữ đều phải được phóng to (hoặc thu nhỏ) theo cùng một tỷ lệ ~{k}~. Như vậy, từ thứ ~{i}~ sẽ chiếm một diện tích là ~\left({k} \times {a}_{i}\right) \times\left({k} \times {b}_{i}\right)~. Nếu một dòng có nhiều từ thì các từ̀ này phải được in với cùng một độ cao.

Yêu cầu: Hãy xác định hệ số tỷ lệ ~{k}~ lớn nhất có thể chọn.

Dữ liệu:

• Dòng đầu tiên chứa ~3~ số nguyên ~{n}, {w}~ và ~{h}\left(1 \leq {n} \leq 10^5, 1 \leq {w}, {h} \leq 10^9\right)~;
• Dòng thứ ~{i}~ trong ~{n}~ dòng sau chứa ~2~ số nguyên ~{a}_{i}~ và ~{b}_i\left(1 \leq {a}_{i}, {b}_{i} \leq 10^9\right)~.

Kết quả:

• Đưa ra một số thực ~{k}~ với độ chính xác ~10^{-6}~.

Ví dụ:

Sample Input

3 10 7 
4 3 
3 2 
4 2

Sample Output

1.400000

Có một con mèo, ~k~ con chuột và một cái hang chuột trên một trục tọa độ ~Ox~. Con mèo nằm ở điểm ~0~, cái hang nằm ở điểm ~n~. Tất cả các con chuột nằm giữa con mèo và cái hang: Con chuột thứ ~i~ nằm ở điểm ~x_i(0 \lt x_i \lt n)~. Tại mỗi điểm có thể có nhiều con chuột.

Trong một giây, những điều sau đây sẽ thực hiện liên tục:

• Đầu tiên, có đúng một con chuột di chuyển sang bên phải ~1~ đơn vị. Nếu con chuột đến hang, nó sẽ trốn được mèo (tức là con chuột sẽ không di chuyển đến bất kỳ điểm nào nữa và sẽ không bị con mèo ăn thịt).

• Sau khi chuột di chuyển xong mèo di chuyển sang phải ~1~ đơn vị. Nếu ở vị trí mới của mèo có chuột, mèo sẽ ăn thịt chúng (những con chuột bị ăn thịt sẽ loại ra khỏi trục số).

Các hoạt động của mèo và chuột sẽ kết thúc khi mèo đến được vị trí ~n~ (tất nhiên những con chuột trốn trong hang tại vị trí ~n~ sẽ không bị ăn thịt).

Mỗi giây, bạn có thể chọn một con chuột sẽ di chuyển. Hỏi tối đa bao nhiêu con chuột lọt được vào hang mà không bị ăn thịt?

Dữ liệu:

Dòng đầu tiên chứa số nguyên dương ~t (1 \le t \le 10)~ là số lượng bộ test. Mỗi bộ test sẽ có dạng như sau:

• Dòng đầu tiên chứa số nguyên ~n~ và ~k (1 \le n \le 10^9; 1 \le k \le 5 \times 10^5)~;
• Dòng thứ hai chứa ~k~ số nguyên ~x_1, x_2, …, x_k (1 \le x_i \lt n)~ là vị trí của các con chuột.

Kết quả:

Gồm ~t~ dòng, mỗi dòng chứa một giá trị ~P~ là số lượng những con chuột đã trốn vào hang tương ứng với dữ liệu Input.

Ví dụ:

Sample Input

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

Sample Output

3
1

Ràng buộc:

• Subtask 1: Có ~20\%~ số test đầu tiên ~k=2~;
• Subtask 2: Có ~30\%~ số test tiếp theo ~n \le 500, k \le 10000~;
• Subtask 3: Có ~50\%~ số test cuối cùng không có ràng buộc gì.