#include<bits/stdc++.h>
#define pii pair<ll,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define ll long long
using namespace std;
const int N=5e5+100,M=sqrt(N)+10;
const ll inf=1e13+7;
int n,S,tp,id,BB;
ll A[N],B[N],ans[N<<1];
int a[N],b[N],lcm[M][M],Get[N];
//get[i] 表示 <=S 的最大的 i 的倍数 
 
namespace G
{
	pii g1[N],g2[N];
	void clear(){for(int i=0;i<N;i++)g1[i]=g2[i]=make_pair(-inf,0);}
	void push(int x,ll v,int i){pii res(v,i);for(int y=x;y<=S;y+=x)if(g1[y]<res)g2[y]=g1[y],g1[y]=res;}
	ll get(int x){ll t=0;for(int y=x;y<=S;y+=x)t=max(t,g1[y].fi+y);return t;}
}
//namespace CT
//{
//	int a[N];
//	void build(int n){memset(a,0,sizeof(a));}
//	void update(int l,int r,int v){for(int i=l;i<=r;i++)a[i]=max(a[i],v);}
//	void query(int*ans){for(int i=1;i<=n;i++)ans[i]=max(ans[i],a[i]);}
//}
namespace CT//CatTree
{
	int n;
	int cnt[N<<1];
	ll pre[N<<1][21],nxt[N<<1][21];//前缀，后缀 
	void build(int _n)
	{
		n=1;while(n<_n)n<<=1;if(n>=N<<1)while(1);
		cnt[0]=-1;for(int i=1;i<=n;i++)cnt[i]=cnt[i>>1]+1;
	}
	void update(int l,int r,ll v)
	{
		if(l>r||v<0)return;int d=cnt[r-l+1];
		pre[l][d]=max(pre[l][d],v);nxt[r][d]=max(nxt[r][d],v);
		if(l/(1<<d)+2==r/(1<<d))nxt[l/(1<<d)+(1<<d)][d]=max(nxt[l/(1<<d)+(1<<d)][d],v);
	}
	void query(ll *a)
	{
		for(int i=0;i<=cnt[n];i++)
			for(int j=1;j<=n;j+=(1<<i))
			{
				for(int k=j+1;k<j+(1<<i);k++)pre[k][i]=max(pre[k][i],pre[k-1][i]);
				for(int k=j+(1<<i)-2;k>=j;k--)nxt[k][i]=max(nxt[k][i],nxt[k+1][i]);
				for(int k=j;k<j+(1<<i);k++)a[k]=max({a[k],pre[k][i],nxt[k][i]});
			}
	}
}
void getF(int*a,ll*f)
{
	G::clear();
	for(int i=1;i<=n;i++,f[i]=max(f[i],f[i-1]))
		if(a[i]<=BB)
		{
			for(int j=i-1,cnt=1+(a[j]<=BB);j>=1&&cnt<=3;j--,cnt+=a[j]<=BB)f[i]=max(f[i],f[j]+Get[lcm[a[i],a[j]]]);
			for(int j=i+1,cnt=1+(a[j]<=BB);j<=n&&cnt<=3;j++,cnt+=a[j]<=BB)f[j]=max(f[j],f[i]+Get[lcm[a[i],a[j]]]);
		}
		else f[i]=max(f[i],G::get(a[i])),G::push(a[i],f[i],i);
}
signed main()
{
	scanf("%d%d%d%d",&n,&S,&tp,&id);BB=sqrt(S);
	if(tp)return 0;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]=min(a[i],S+1);
	for(int i=1;i<=BB;i++)for(int j=1;j<=BB;j++)LCM[i][j]=i*j/__gcd(i,j); 
	for(int i=1;i<=S;i++)Get[i]=S/i*i;
	getF(a,A);reverse(a+1,a+n+1);getF(a,B);A[0]=A[n+1]=B[0]=B[n+1]=0;
	reverse(B+1,B+n+1);reverse(a+1,a+n+1);
	printf("%lld ",A[n]);if(!tp)return 0;
	CT::build(n);G::clear();
	for(int i=1;i<=n;i++)
		if(a[i]<=BB)
		{
			for(int j=i-1,cnt=1+(a[j]<=BB);j>=1&&cnt<=3;j--,cnt+=a[j]<=BB)CT::update(j+1,i-1,A[j]+B[i]+Get[lcm[a[i],a[j]]]);
			for(int j=i+1,cnt=1+(a[j]<=BB);j<=n&&cnt<=3;j++,cnt+=a[j]<=BB)CT::update(i+1,j-1,A[i]+B[j]+Get[lcm[a[i],a[j]]]);
		}
		else 
		{
			for(int y=a[i];y<=S;y+=a[i])CT::update(G::g1[y].se+1,i-1,G::g1[y].fi+B[i]+y),CT::update(G::g2[y].se+1,i-1,G::g2[y].fi+B[i]+y);
			G::push(a[i],A[i],i);
		}
	CT::query(ans);
	ll res=0;
	for(int i=1;i<=n;i++)ans[i]=max({ans[i],A[i-1]+B[i+1]}),res^=ans[i]*i;
//	for(int i=1;i<=n;i++)printf("%lld ",ans[i]);puts("SB");	
	printf("%lld\n",res);
	return 0;
}

answer.code: In function ‘void getF(int*, long long int*)’:
answer.code:63:109: error: invalid types ‘int [500100][int [717]]’ for array subscript
   63 |                         for(int j=i-1,cnt=1+(a[j]<=BB);j>=1&&cnt<=3;j--,cnt+=a[j]<=BB)f[i]=max(f[i],f[j]+Get[lcm[a[i],a[j]]]);
      |                                                                                                             ^
answer.code:64:109: error: invalid types ‘int [500100][int [717]]’ for array subscript
   64 |                         for(int j=i+1,cnt=1+(a[j]<=BB);j<=n&&cnt<=3;j++,cnt+=a[j]<=BB)f[j]=max(f[j],f[i]+Get[lcm[a[i],a[j]]]);
      |                                                                                                             ^
answer.code: In function ‘int main()’:
answer.code:73:53: error: ‘LCM’ was not declared in this scope
   73 |         for(int i=1;i<=BB;i++)for(int j=1;j<=BB;j++)LCM[i][j]=i*j/__gcd(i,j);
      |                                                     ^~~
answer.code:82:119: error: invalid types ‘int [500100][int [717]]’ for array subscript
   82 |                         for(int j=i-1,cnt=1+(a[j]<=BB);j>=1&&cnt<=3;j--,cnt+=a[j]<=BB)CT::update(j+1,i-1,A[j]+B[i]+Get[lcm[a[i],a[j]]]);
      |                                                                                                                       ^
answer.code:83:119: error: invalid types ‘int [500100][int [717]]’ for array subscript
   83 |                         for(int j=i+1,cnt=1+(a[j]<=BB);j<=n&&cnt<=3;j++,cnt+=a[j]<=BB)CT::update(i+1,j-1,A[i]+B[j]+Get[lcm[a[i],a[j]]]);
      |                                                                                                                       ^
answer.code:70:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |         scanf("%d%d%d%d",&n,&S,&tp,&id);BB=sqrt(S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:72:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   72 |         for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]=min(a[i],S+1);
      |                              ~~~~~^~~~~~~~~~~~