非常厉害的题。

首先先把 $k$ 变成 $k+t$，这样就是整体加 $t$ 之后单点减 $k$。

此时有一个很好的事情，就是我们可以快速判断 $C$ 次操作是否合法，只需要分成加和减两个步骤来考虑，判断加完以后减成非正的最小操作次数是否小于等于 $C$，即 $\sum\limits_{i=1}^n\max(0,\lceil \frac{a_i+Ct}{k}\rceil)\le C$。

然后想到二分 check，但是试了一下发现没有单调性，然后就倒闭了。不过我们可以再观察一下性质。

并不是所有的数都会被操作的，将所有数从大到小排序后，我们会操作的数显然是一个前缀，设为 $[1,p]$。当 $k\le tp$ 的时候，我们操作这个前缀反而会让总和变大，这显然是没有道理的。所以我们找到 $k>tp$ 的最大的 $p$，那么这个前缀就是我们可能操作的。

接下来有一个重要的观察，就是如果当前合法，给 $[1,p]$ 每个位置都进行一遍操作，那么还是合法的。反映在上面那个式子里面就是当 $C$ 变为 $C+p$ 时，每个分母都增加了 $tp<k$，所以每个元素操作次数增加不超过 $1$，而右边增加 $p$，显然小于等于限制仍然满足。所以说，每一个模 $p$ 的等价类里面是有单调性的。

于是我们枚举答案模 $p$ 是多少，然后直接二分，但是 check 太慢了，怎么办？

刚才那个式子首先可以二分 $a_i+Ct>0$ 的最长前缀把对 $0$ 取 max 去掉。接下来的 $\lceil \frac{a_i+Ct}{k}\rceil$ 可以拆成 $\lceil \frac{a_i}{k}\rceil+\lceil \frac{Ct}{k}\rceil$ 再减去一个 $0$ 或 $1$ 的修正量的形式，而修正量的计算是一个偏序形式（可以自己推一推），使用主席树做在线二维数点可以做到单次查询 $O(\log V)$。

现在得到了两个 log 的方法，能不能再优化呢？其实是可以的，这个题有一个很好的性质在于我们可以很容易判断模 $p$ 得到某个余数 $i$ 意义下是否可能产生更优的解，即直接 check 当前小于等于当前答案的最大模 $p$ 于 $i$ 数的合法性，这是单 log 而不是双 log 的。于是我们直接将所有余数进行随机顺序的 check，这样对答案可能产生更新的余数期望只有 $O(\log n)$ 个（第 $i$ 个余数有 $\frac{1}i$ 的概率是当前答案，期望为 $\sum\limits_{i=1}^n\frac{1}i=O(\log n)$），只有这些时候我们需要二分，其它时候都只需要一次 check。于是我们做到了单 log。

有以下注意事项：

• 注意特判 $k=0$。

• 你需要判断不需要操作的数会不会因为你的全局加而大于等于 $0$，但是不能在 check 里面判断，否则会失去单调性。因为你做的整个操作就是找最优解，只需要在找出解以后判断就可以知道是否有合法解了。

• 新的 $k\le 2\times 10^9$，主席树数组不要开小。

代码写的很混乱，谨慎参考。

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define pi pair<int,signed>
using namespace std;
mt19937 rnd(time(0));
pi a[N];
int n,k,t,pre[N];
signed sum[N*32],lc[N*32],rc[N*32],idx,rt[N],xu[N];
void pushup(int x){
	sum[x]=sum[lc[x]]+sum[rc[x]];
}
int update(int x,int l,int r,int kk,int v){
	sum[++idx]=sum[x];lc[idx]=lc[x];rc[idx]=rc[x];
	x=idx;
	if(l==r){
		sum[x]+=v;return x;
	}
	int mid=(l+r)>>1;
	if(kk<=mid)lc[x]=update(lc[x],l,mid,kk,v);
	else rc[x]=update(rc[x],mid+1,r,kk,v);
	pushup(x);
	return x;
}
int query(int x,int l,int r,int ql,int qr){
	if(!x||ql>qr)return 0;
	if(ql<=l&&r<=qr)return sum[x];
	int mid=(l+r)>>1,ans=0;
	if(ql<=mid)ans+=query(lc[x],l,mid,ql,qr);
	if(qr>mid)ans+=query(rc[x],mid+1,r,ql,qr);
	return ans;
}
int rev[N],p;
int ans=1e18,inf=1e18;
bool check(int mid){
	int pos=lower_bound(rev+1,rev+n+1,(__int128)mid*t)-rev-1;
	if(pos<0)return 1;
	pos=min(pos,p);
	return pre[pos]+((__int128)mid*t+k-1)/k*pos-query(rt[pos],0,k-1,k-(k-(__int128)mid*t%k)%k,k-1)<=mid;
}
signed main(){
	//freopen("construct.in","r",stdin);
	//freopen("construct.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>k>>t;
	k+=t;
	for(int i=1;i<=n;++i){
		cin>>a[i].first;a[i].second=i;
	}
	if(!k){
		int f=1;
		for(int i=1;i<=n;++i)f&=(a[i].first<=0);
		if(f){
			cout<<"0\n";
			for(int i=1;i<=n;++i)cout<<"0 ";
		}
		else cout<<"-1\n";
		return 0;
	}
	sort(a+1,a+n+1,greater<pi>());
	for(int i=1;i<=n;++i){
		pre[i]=pre[i-1]+(a[i].first+k-1+(__int128)k*inf)/k-inf;
	}
	p=n;
	for(int i=1;i<=n;++i){
		if(k<=i*t){
			p=i-1;break;
		}
	}
	for(int i=1;i<=n;++i)rt[i]=update(rt[i-1],0,k-1,(k-a[i].first%k)%k,1);
	for(int i=1;i<=n;++i)rev[i]=-a[i].first;
	for(int i=0;i<p;++i)xu[i]=i;
	shuffle(xu,xu+p,rnd);
	int ff=0;
	for(int i=0;i<p;++i){
		int now=xu[i];
		int rr=ans/p*p+now;
		if(rr>ans)rr-=p;
		if(check(rr)){
			int l=0,r=rr/p;
			while(l<=r){
				int mid=(l+r)>>1;
				if(check(p*mid+now))ans=p*mid+now,ff=1,r=mid-1;
				else l=mid+1;
			}
		}
	}
	if(!ff)cout<<"-1\n";
	else{
		if(p+1<=n&&a[p+1].first+(__int128)ans*t>0)return cout<<-1,0;
		memset(rev,0,sizeof(rev)); 
		cout<<ans<<'\n';
		for(int i=1;i<=p;++i){
			rev[a[i].second]=max(0ll,(int)((a[i].first+(__int128)ans*t+k-1+(__int128)k*inf)/k-inf));
		}
		for(int i=1;i<=n;++i)cout<<rev[i]<<" ";
	}
	return 0;
}