For convenience, we consider the sequence

\[C' = (C'_1, C'_2, \ldots, C'_{2N}) \coloneqq (C_1, C_2, \ldots, C_{N}, C_1, C_2, \ldots, C_{N}),\]

which is obtained by concatenating two copies of the given sequence, and regard that this problem asks to find the total number of balls in the boxes when operating against a segment \([l, l+N-1]\) of \(C'\) for each \(l = 1, 2, \ldots, N\). Let \(f(c, l, r)\) be the number of balls with color \(c\) in the segment \([l, r]\), and \(g(c)\) be \(f(c, 1, N)\), the number of balls of color \(c\) in the entire original sequence \(C\).

First, we consider how to find the answer for a fixed segment \([l, l+N-1]\). As a result of operating against the segment \([l, l+N-1]\), if \(b(c, l)\) boxes are used to store balls of color \(c\), then the number of balls of color \(c\) resulting in a box is \(\min\lbrace b(c, l) \times K, g(c)\rbrace\), so the answer is

\[\mathrm{ans}_l = \sum_{c = 1}^N \min\lbrace b(c, l) \times K, g(c)\rbrace.\]

Once we find \(b(c, l)\) for each color \(c\), we can also find \(\mathrm{ans}_l\), so we then consider how to find it.

A ball might be put into an empty box (which increments the number of boxes used for that color) if the ball is the \(1\)-st, \((K+1)\)-th, \((2K+1)\)-th, \((3K+1)\)-th, \(\ldots\) ball of that color to be processed. So let us call the \(1\)-st, \((K+1)\)-th, \((2K+1)\)-th, \((3K+1)\)-th, \(\ldots\) balls of each color to be processed chance balls.

Every time a chance ball (of any color) is processed, an empty box is consumed, so \(b(c, l)\) equals the number of color-\(c\) balls among the first \(M\) chance balls to be processed. So what is the position of the \(M\)-th chance ball to be processed?

When starting operation from the position \(l\), the number of chance balls of color \(c\) within the segment \([l, r]\) is \(\left\lceil f(c, l, r) / K \right\rceil\), so the number of chance balls (of any color) within the segment \([l, r]\) is

\[S(l, r) \coloneqq \sum_{c = 1}^N \left\lceil \frac{f(c, l, r)}{K} \right\rceil.\]

Thus, the position of the \(M\)-th chance ball to be processed is given as the minimum \(r\) such that \(S(l, r) \geq M\). Denoting it by \(r_l\), we have \(b(c, l) = \left\lceil f(c, l, r_l) / K \right\rceil\), so the sought answer is represented as

\[ \mathrm{ans}_l = \sum_{c = 1}^N \min\left\lbrace \left\lceil \frac{f(c, l, r_l)}{K} \right\rceil \times K, g(c) \right\rbrace. \tag{1} \]

(If no \(r \leq l+N-1\) satisfies \(S(l, r) \geq M\), then we let \(r_l \coloneqq l+N-1\) for convenience.) Therefore, in order to find \(\mathrm{ans}_l\), it is sufficient to find \(r_l\) for the fixed \(l\) and evaluate the expression (1) above. However, naively computing it for all \(l = 1, 2, \ldots, N\) is impossible to finish it within the execution time limit.

Instead, notice that it follows that \(r_1 \leq r_2 \leq \cdots \leq r_N\) from the discussion above. In order to evaluate the answer for \(l = 1, 2, \ldots, N\) in order, \(r_l\) can be efficiently found as \(l\) increases in manner of sliding window. While sliding window, one also maintain the value (1) corresponding to the current segment \([l', r']\), and apply delta update every time \(l'\) or \(r'\) increments by one, so that \(\mathrm{ans}_l\) are also found in a total of \(O(N)\) time.

The following is sample code in C++ for this problem.

#include <iostream>
using namespace std;

int n, m, k;
int c[400001], all[200001];
int cnt[200001], box[200001], sum, ans;

void add(int i,int x){
	ans -= min(box[i] * k, all[i]);
	sum -= box[i];
	box[i] -= (cnt[i]+k-1)/k;
	cnt[i] += x;
	box[i] += (cnt[i]+k-1)/k;
	sum += box[i];
	ans += min(box[i] * k, all[i]);
}

int main(void){
  cin >> n >> m >> k;
  for(int i = 1; i <= n; i++) cin >> c[i], c[n+i] = c[i], all[c[i]]++;

  int r = 0;
  for(int l = 1; l <= n; l++){
    while(r+1 < l+n && sum < m) r++, add(c[r], 1);
    cout << ans << "\n";
    add(c[l], -1);
  }

  return 0;
}