#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
#define fi first
#define se second
const int N=5e5+5,M=750;
int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
ll f[N],g[N],mx[N],mx1[N],w[20][N];
template<class T>inline void gmax(T&x,T y){x=(x>y?x:y);}
void upd(int l,int r,ll v) {
	if(l>r)return;int k=__lg(r-l+1);
	gmax(w[k][l],v),gmax(w[k][r-(1<<k)+1],v);
} 
int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>S>>type>>tid;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]=min(a[i],S+1);
	for(int i=1;i<=S+1;i++)b[i]=S/i*i;
	int B=sqrt(S);
	for(int i=1;i<=B;i++)for(int j=0;j<i;j++)G[i][j]=i/__gcd(i,j);
	memset(mx,-0x3f,sizeof(mx));
	for(int i=1;i<=n;i++) {
		if(a[i]<=B) {
			for(int j=i-1,k=(a[j]<=B);j&&k<3;j--,k+=a[j]<=B)gmax(f[i],f[j]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
			for(int j=i+1,k=(a[j]<=B);j<=n&&k<3;j++,k+=a[j]<=B)gmax(f[j],f[i]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
		}else {
			f[i]=max(f[i],f[i-1]);
			int st=(S/2+a[i]-1)/a[i]*a[i]; 
			for(int j=st;j<=S;j+=a[i])gmax(f[i],mx[j]+j);
			for(int j=st;j<=S;j+=a[i])mx[j]=f[i];
		}
	}
	cout<<f[n]<<' ';
	if(!type)return 0;
	memset(mx,-0x3f,sizeof(mx)),memset(mx1,-0x3f,sizeof(mx1));
	for(int i=n;i;i--) {
		if(a[i]<=B) {
			for(int j=i+1,k=(a[j]<=B);j<=n&&k<3;j++,k+=a[j]<=B)gmax(g[i],g[j]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
			for(int j=i-1,k=(a[j]<=B);j&&k<3;j--,k+=a[j]<=B)gmax(g[j],g[i]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
		}else {
			gmax(g[i],g[i+1]);
			int st=(S/2+a[i]-1)/a[i]*a[i]; 
			for(int j=st;j<=S;j+=a[i])if(lst[j])upd(i+1,lst[j]-1,mx[j]+f[i]+j),gmax(w[0][lst[j]],mx1[j]+f[i]+j),gmax(g[i],mx[j]+j);
			for(int j=st;j<=S;j+=a[i])mx1[j]=mx[j],lst[j]=i,mx[j]=g[i];
		}
	}
	memset(lst,0,sizeof(lst));
	for(int i=1;i<=n;i++)if(a[i]<=B) {
		int l=max(1,i-1),r=min(n,i+1);
		for(int k=(a[l]<=B);l>1&&k<3;l--,k+=a[l]<=B);
		for(int k=(a[r]<=B);r<n&&k<3;r++,k+=a[r]<=B);
		ll mx=0;for(int j=l;j<i;j++)gmax(w[0][j],mx),gmax(mx,f[j]+g[i]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
		mx=0;for(int j=r;j>i;j--)gmax(w[0][j],mx),gmax(mx,f[i]+g[j]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
	}
	for(int i=19;i;i--)for(int j=1;j<=n-(1<<i)+1;j++)gmax(w[i-1][j],w[i][j]),gmax(w[i-1][j+(1<<i-1)],w[i][j]); 
	ll ans=0;
	for(int i=1;i<=n;i++)ans^=max(f[i-1]+g[i+1],w[0][i])*i;
	cout<<ans<<'\n';
	return 0;
}
/*
5 10 1 1
3 2 1 4 5

10 9999 1 1
93 120 538 410 1 248 100 11 45 14
*/