#include <bits/extc++.h>
#define endl '\n'
typedef long long ll;
#define int ll
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
constexpr int inf = 0x3f3f3f3f3f3f3f3f;
mt19937 rand_get(chrono::steady_clock::now().time_since_epoch().count());
int k4p;
struct ly
{
ly *lp = nullptr, *rp = nullptr;
int key, val;
int cost = 0, scs = 0;
uint32_t pri;
ly() = default;
ly(const int kkey, const int vval) : key(kkey), val(vval), pri(rand_get())
{
const int gap_len = val - key + 1;
cost = gap_len > 0 ? (gap_len + k4p - 1) / k4p : 0;
scs = cost;
}
};
constexpr int mxnn = 4e6;
ly np[mxnn];
int npi;
ly* nly(const int key, const int val)
{
np[npi] = ly(key, val);
return &np[npi++];
}
void pull(ly* t)
{
if (!t)
{
return;
}
const int l_sum = t->lp ? t->lp->scs : 0;
const int r_sum = t->rp ? t->rp->scs : 0;
t->scs = l_sum + r_sum + t->cost;
}
void split(ly* t, const int key, ly*& l, ly*& r)
{
if (!t)
{
l = r = nullptr;
return;
}
if (t->key < key)
{
split(t->rp, key, t->rp, r);
l = t;
}
else
{
split(t->lp, key, l, t->lp);
r = t;
}
pull(t);
}
ly* merge(ly* l, ly* r)
{
if (!l || !r)
{
return l ? l : r;
}
if (l->pri > r->pri)
{
l->rp = merge(l->rp, r);
pull(l);
return l;
}
r->lp = merge(l, r->lp);
pull(r);
return r;
}
void insert(ly*& t, ly* itt)
{
if (!t || itt == nullptr)
{
if (itt)
{
t = itt;
}
pull(t);
return;
}
ly *t1, *t2;
split(t, itt->key, t1, t2);
t = merge(merge(t1, itt), t2);
}
pair<int, int> fbri(ly* t, int bud)
{
if (!t)
{
return {-1, bud};
}
const int lsm = t->lp ? t->lp->scs : 0;
if (bud < lsm)
{
return fbri(t->lp, bud);
}
bud -= lsm;
if (bud < t->cost)
{
return {t->key, bud};
}
bud -= t->cost;
return fbri(t->rp, bud);
}
void Main()
{
int n, m;
cin >> n >> m >> k4p;
vector<int> a(n);
for (int& x : a)
{
cin >> x;
}
npi = 0;
auto gprt = nly(0, inf);
for (int i = 0; i < n; ++i)
{
const int cl = max(0ll, a[i] - k4p + 1);
const int cr = a[i];
ly *lp, *mp, *rp;
split(gprt, cl, lp, mp);
split(mp, cr + 1, mp, rp);
vector<pair<int, int>> ad2;
if (lp)
{
const ly* tmp = lp;
while (tmp->rp)
{
tmp = tmp->rp;
}
if (tmp->val >= cl)
{
ly *curl, *i2p;
split(lp, tmp->key, curl, i2p);
if (i2p->key < cl)
{
ad2.emplace_back(i2p->key, cl - 1);
}
if (i2p->val > cr)
{
ad2.emplace_back(cr + 1, i2p->val);
}
lp = curl;
}
}
function<void(ly*)> pmnd = [&](ly* t)
{
if (!t)
{
return;
}
pmnd(t->lp);
pmnd(t->rp);
if (t->val > cr)
{
ad2.emplace_back(cr + 1, t->val);
}
};
pmnd(mp);
gprt = merge(lp, rp);
for (const auto& [x, y] : ad2)
{
if (x <= y)
{
insert(gprt, nly(x, y));
}
}
const auto [pos, rem] = fbri(gprt, m);
int res;
if (pos != -1)
{
res = pos + rem * k4p;
}
else
{
int lr = 0;
if (const ly* curr = gprt)
{
while (curr->rp)
{
curr = curr->rp;
}
lr = curr->val;
}
res = lr + 1 + rem * k4p;
}
cout << res << " ";
}
cout << endl;
}
#define CP_MULTI_TEST_CASES
signed main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
#ifdef CP_MULTI_TEST_CASES
cin >> t;
#endif
while (t--)
{
Main();
}
return cout << flush, fflush(stdout), 0;
}