Bạn đang chơi Minecraft, công việc của bạn là phải xây dựng một bức tường có độ cao lớn nhất có thể. Hiện tại, bạn đang có sẵn một bức tường có \(n\) cột, cột thứ \(i\) có chiều cao là \(a_{i}\). Hiện tại bạn có \(w\) khối, với mỗi khối bạn có thể nâng độ cao một cột bất kì thêm một đơn vị. Bạn muốn xây bức tường sao cho độ cao của cột có độ cao nhỏ nhất là lớn nhất có thể. Hỏi độ cao đó có thể bằng bao nhiêu?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(w\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq w \leq 10^{9})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \le 10^{9})\).

Output

• Một dòng chứa một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 100, w \leq 10^{5}\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{3}, w \leq 10^{6}\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3 9 
1 1 1

4

Lớp của Thuận tổ chức đi chơi du lịch đến Nha Trang. Khi đến Nha Trang, họ có một buổi chiều tắm biển rất vui vẻ. Sau khi chơi vui vẻ, họ quyết định trở về khách sạn. Đoạn đường từ biển về khách sạn có độ dài là \(l\) mét. Mỗi người đều có thể đi bộ với vận tốc là \(v_{1}\) mét mỗi giây. Tuy nhiên, do đã chơi cả chiều nên ai cũng thấm mệt, họ quyết định gọi xe để trở về khách sạn. Xe có thể chở tối đa \(k\) người trong cùng một thời điểm và có vận tốc là \(v_{2}\) mét mỗi giây. Mọi người sẽ chia nhau lên xe và đi bộ, tuy nhiên mỗi người sẽ chỉ lên xe nhiều nhất một lần.

Hãy xác định khoảng thời gian ngắn nhất để tất cả \(n\) người đều trở về được khách sạn, coi khoảng thời gian lên xe và xuống xe là ngay lập tức và ta có thể bỏ qua khoảng thời gian này.

Input

• Một dòng chứa năm số nguyên \(n, l, v_{1}, v_{2}, k\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq l \leq 10^{9}, 1 \leq v_{1} < v_{2} \leq 10^{9}, 1 \leq k \leq n)\).

Output

• Đưa ra một số thực là khoảng thời gian ngắn nhất (tính theo giây) để cả \(n\) người đều trở về được khách sạn. Sai số tối đa cho phép là \(10^{-6}\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(k = n\).
• Subtask \(2\) (\(30\%\) số điểm): \(\left\lceil \frac{n}{2} \right\rceil \leq k \leq n\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

5 10 2 4 5

2.5

Một công xưởng đã sản xuất ra một dãy \(n\) con chip được gắn liền kề với nhau, con chip thứ \(i\) đang hoạt động ở công suất \(a_{i}\). Vì được gắn liền kề nhau nên công suất của những con chip có sự tác động lẫn nhau và làm ảnh hưởng đến công suất hoạt động của cả đoạn. Ta định nghĩa tổng công suất của các con chip trong một đoạn chip \([l, r]\) \((1 \leq l \leq r \leq n)\) được xác định bởi giá trị nhỏ nhất của đoạn chip đó. Để chiết xuất một đoạn chip hoạt động hiệu quả, nhà sản xuất muốn biết rằng với mỗi số nguyên \(x\) từ \(1\) đến \(n\), đoạn chip có độ dài \(x\) có tổng công suất lớn nhất là bao nhiêu?

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 2 \times 10^{5})\) là số lượng chip của công xưởng.
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\) là công suất hoạt động của các con chip.

Output

• Gồm \(n\) số nguyên dương trên 1 dòng, số nguyên thứ \(x\) là tổng công suất lớn nhất của đoạn chip độ dài \(x\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 500\).
• Subtask \(2\) (\(10\%\) số điểm): \(n \leq 1000\).
• Subtask \(3\) (\(10\%\) số điểm): \(a_{i} \leq 100\).
• Subtask \(4\) (\(25\%\) số điểm): \(n \leq 5000\).
• Subtask \(5\) (\(35\%\) số điểm): không có ràng buộc gì thêm.

Example

4
2 1 4 5

5 4 1 1

Trong Geometry Dash, các chướng ngại vật thường có thể được chia thành hai loại chướng ngại vật chính là gai nhọn và bức tường. Việc thiết kế chướng ngại vật được gọi là thiết kế hay nếu như các chướng ngại vật bức tường không được đặt cạnh nhau quá nhiều. Một màn chơi đương nhiên sẽ hay nếu như màn chơi ấy được thiết kế hay.

Hiểu được điều này, Tèo đã vẽ ra \(t\) kế hoạch kinh doanh và mỗi kế hoạch có dạng như sau: Với mỗi kế hoạch Tèo sẽ dùng số tiền \(n\) đô la ít ỏi của mình để mua \(n\) chướng ngại vật trong game nhằm thiết kế một màn chơi hay để sinh lời. Tèo chọn ra một số \(k\) phong thủy là số bức tường tối đa có thể được đặt cạnh nhau. Dựa trên số cách có thể thiết kế màn chơi mà Tèo quyết định có dùng phương án này hay không.

Yêu cầu: Với mỗi kế hoạch, bạn hãy giúp Tèo đếm số cách thiết kế màn chơi nhé.

Input

• Dòng đầu tiên chứa \(T\) \((T \leq 10\)).
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số \(n\) và \(k\) \((1 \leq n \leq 10^{5}, 0 \leq k \leq \min(n, 20))\).

Output

• Gồm \(t\) dòng, dòng thứ \(i\) là kết quả của kế hoạch thứ \(i\), vì kết quả rất lớn nên chỉ cần in ra số dư của kết quả khi chia cho \(220220061\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm): \(k \leq 1\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

2
3 1
5 1

5
13