Let \(B\) denote \(A\) after the operations. Then each \(B_i\) is either \(0\) or \(A_i\).

Since we want the lexicographically smallest result, we process elements from left to right and determine for each element whether it can be made \(0\).

Let \(f_i\) be the number of operations performed on intervals that include \(A_i\) (with \(f_0=0\)).

Suppose the first \(i-1\) elements have been determined, and we are now determining the \(i\)-th element.

Since \(f_{i-1}\) operations were performed to bring \(A_{i-1}\) to \(B_{i-1}\), extending these intervals to cover position \(i\) makes the value of \(A_i\) equal to \(X=(A_i+f_{i-1}) \bmod M\). We can reduce \(X\) to \(0\) by removing \(X\) intervals that extend from \(A_{i-1}\) to \(A_i\), but the constraint \(f_i \geq 0\) may make this impossible. In that case, we can instead add intervals at positions where we previously removed intervals to set \(B_i=0\). This can be done by computing, for each such position, how many additional operations are needed to set \(B_i=0\), and maintaining them in a priority queue in ascending order of cost. If no matter what we do the total number of operations exceeds \(K\), then it is impossible to set \(B_i=0\), so \(B_i=A_i\). In that case, no operation can span across \(A_i\), so we must set \(f_i=0\) and clear the priority queue.

By implementing the above appropriately, you can solve this problem. The time complexity is \(O(N\log N)\).

Implementation example (Python3)

import sys
import heapq

input = sys.stdin.readline
for _ in range(int(input())):
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    f = 0
    q = []
    ans = [0] * N
    for i, a in enumerate(A):
        d = (f + a) % M
        f -= d
        heapq.heappush(q, M - d)
        if f < 0:
            if q[0] <= K:
                K -= heapq.heappop(q)
                f += M
            else:
                f = 0
                q.clear()
                ans[i] = a
    print(*ans)