#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> PII;
const int maxn=555555,maxsq=750,mod=998244353;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
	char ch=getchar();ll x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
inline int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;
	return ans;
}
int n,s,sq,tp,a[maxn],g[maxsq][maxsq],lt[maxn];
PII p[maxn][2];
ll f[maxn],ff[maxn],mx[maxn],st[20][maxn];
inline int gcd(int x,int y){
	if(x<=sq && y<=sq) return g[x][y];
	return y?gcd(y,x%y):x;
}
inline int w(int x,int y){
	ll l=1ll*x/gcd(x,y)*y;
	return s/l*l;
}
inline void update(int l,int r,ll v){
	if(l>r) return;
	int k=lt[r-l+1];
//	printf("update %d %d %lld,k=%d\n",l,r,v,k);
	st[k][l]=max(st[k][l],v);
	st[k][r-(1<<k)+1]=max(st[k][r-(1<<k)+1],v);
}
void solve(){
	n=read();s=read();tp=read();read();
	sq=sqrt(s);
	FOR(i,1,n) a[i]=read();
	FOR(i,0,sq) FOR(j,0,i){
		if(!i || !j) g[i][j]=i+j;
		else g[i][j]=g[j][i%j];
	}
	FOR(i,0,sq) FOR(j,i,sq) g[i][j]=g[j][i];
	ll ans=0;
	FOR(_,0,1){
		MEM(mx,~0x3f);
		FOR(i,1,n) if(a[i]<=s){
			if(a[i]<=sq){
				int cnt=0;
				ROF(j,i-1,1){
					if(a[j]<=sq) if(++cnt==2) break;
					f[i]=max(f[i],f[j]+w(a[i],a[j]));
				}
				cnt=0;
				FOR(j,i+1,n){
					if(a[j]<=sq) if(++cnt==2) break;
					f[j]=max(f[j],f[i]+w(a[i],a[j]));
				}
			}
			else{
				for(int j=0;j<=s;j+=a[i]) f[i]=max(f[i],mx[j]+j);
				for(int j=0;j<=s;j+=a[i]) mx[j]=max(mx[j],f[i]);
			}
			ans=max(ans,f[i]);
		}
		else f[i]=f[i-1];
		reverse(a+1,a+n+1);
		swap(f,ff);
	}
	printf("%lld ",ans);
	if(tp==0) return;
	reverse(ff+1,ff+n+1);
//	FOR(i,1,n) printf("f[%d]=%lld,ff[%d]=%lld\n",i,f[i],i,ff[i]);
	FOR(i,2,n) lt[i]=lt[i>>1]+1;
	FOR(i,1,n) if(a[i]<=sq){
		int cnt=0;
		ROF(j,i-1,1){
			if(a[j]<=sq) if(++cnt==3) break;
			update(j+1,i-1,f[j]+ff[i]+w(a[i],a[j]));
		}
		cnt=0;
		FOR(j,i+1,n){
			if(a[j]<=sq) if(++cnt==3) break;
			update(i+1,j-1,f[i]+ff[j]+w(a[i],a[j]));
		}
	}
//	puts("end");
	MEM(p,~0x3f);
	FOR(i,1,n) if(a[i]<=s && a[i]>sq){
		for(int j=0;j<=s;j+=a[i]){
			int k=p[j][0].se;
			if(k>=1) update(k+1,i-1,f[k]+ff[i]+j);
			k=p[j][1].se;
			if(k>=1) update(k+1,i-1,f[k]+ff[i]+j);
		}
		for(int j=0;j<=s;j+=a[i]){
			if(f[i]>=p[j][0].fi) p[j][1]=p[j][0],p[j][0]=MP(f[i],i);
		}
	}
	ROF(i,lt[n],1) FOR(j,1,n-(1<<i)+1){
		st[i-1][j]=max(st[i-1][j],st[i][j]);
		st[i-1][j+(1<<(i-1))]=max(st[i-1][j+(1<<(i-1))],st[i][j]);
	}
	ans=0;
	FOR(i,1,n) ans^=1ll*i*max(st[0][i],f[i-1]+ff[i+1]);//,printf("ans[%d]=%lld\n",i,max(st[0][i],f[i-1]+ff[i+1]));
	printf("%lld\n",ans);
	FOR(i,1,n) printf("%lld ",max(st[0][i],f[i-1]+ff[i+1]));
}
int main(){
	int T=1;
	while(T--) solve();
}