Xếp nhóm

Trại hè Tin học miền Bắc có $n$ đoàn tham gia. Các đoàn được đánh số hiệu từ $1$ đến $n$, đoàn thứ $i$ có $a_i$ học sinh. Trong buổi sinh hoạt tập thể, ban tổ chức muốn tổ chức cho học sinh chơi trò chơi theo nhóm, mỗi nhóm có đúng $k$ học sinh và không nhóm nào có hai học sinh cùng đoàn (có thể có học sinh không được xếp vào bất cứ nhóm nào).

Ban đầu, chỉ có $m$ đoàn có số hiệu $1,2,\dots ,m$ ($m<n$) tham gia. Sau đó, các đoàn có số hiệu $m+1,m+2,\dots ,n$ lần lượt đăng kí tham gia. Mỗi khi có đoàn mới đăng kí tham gia, ban tổ chức sẽ sắp xếp lại các nhóm (từ toàn bộ học sinh của các đoàn đã tham gia) sao cho có nhiều nhóm chơi nhất theo quy định: mỗi nhóm có đúng $k$ học sinh và không nhóm nào có hai học sinh cùng đoàn.

Yêu cầu: Cho các số nguyên dương $a_1,a_2,\dots ,a_n$, $k$ và $m$. Hãy giúp ban tổ chức tính số nhóm nhiều nhất có thể xếp được mỗi khi có một đoàn mới đăng kí tham gia chơi.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương $T$ ($T\le 100$) là số bộ dữ liệu, mỗi bộ theo khuôn dạng sau:
  • Dòng thứ nhất gồm ba số nguyên dương $n,k,m$ ($k,m<n\le {10}^5$);
  • Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^9$).

Dữ liệu ra

In ra $T$ dòng, mỗi dòng ứng với một bộ dữ liệu gồm $n-m$ số nguyên: số thứ $j$ là số nhóm nhiều nhất xếp được khi đoàn $m+j$ đăng kí tham gia (khi đó các đoàn $1,2,\dots ,m+j$ đã tham gia), với $j=1,2,\dots ,n-m$. Hai số liên tiếp cách nhau một dấu cách.

Ràng buộc

• $1\le T\le 100$.
• $1\le k<n\le {10}^5$, $1\le m<n$.
• $1\le a_i\le {10}^9$.
• Có $30\%$ số test với $T=1$; $k,m<n\le {10}^3$.
• Có $30\%$ số test với $T\le 10$; $k,m<n\le {10}^3$.
• Có $40\%$ số test với $T\le 100$; $k,m<n\le {10}^5$.

Ví dụ