#include<bits/stdc++.h>
using namespace std;
#define int long long
#define md(a) a=(a%mod+mod)%mod
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)

bool ST;

const int N=500005,T=100;
int n,S,Type,Tid,B,a[N],Ans[N];
int P[N],Q[N],g[N][T],pos[T],gcd[710][710];vector<int>inc;int *f;
inline int lcm(int x,int y){if(x>y)swap(x,y);if(x<=B)return x*y/gcd[x][y%x];return x*y/__gcd(x,y);}
inline int w(int x,int y){int d=lcm(x,y);return (S/d)*d;}

inline void New(int j,int i,int v){f[i]=max(f[i],f[j]+v);}
inline void Calc(int *dp)
{
	f=dp;inc.clear();for(int i=n;i>=1;i--)if(a[i]<=B)inc.push_back(i);int mx=1;
	for(int i=1;i<=S;i++)for(int j=0;j<T;j++)g[i][j]=0;for(int j=0;j<T;j++)pos[j]=0;
	for(int i=1;i<=n;i++)
	{
		f[i]=max(f[i],f[i-1]);while(mx<i-1&&f[mx]+S<=f[i])mx++;
		if(i-mx<=20){for(int j=mx;j<i;j++)New(j,i,w(a[j],a[i]));}
		else
		{
			for(int t=0;t<T;t++)if(pos[t])New(pos[t],i,w(a[pos[t]],a[i]));
			if(a[i]>B){for(int j=a[i];j<=S;j+=a[i])for(int t=0;t<T;t++)if(g[j][t])New(g[j][t],i,j);}
		}

		if(a[i]<=B){for(int t=0;t<T-1;t++)pos[t]=pos[t+1];pos[T-1]=i;}
		else
		{
			for(int j=a[i];j<=S;j+=a[i]){for(int t=0;t<T-1;t++)g[j][t]=g[j][t+1];g[j][T-1]=i;}
			while(!inc.empty()&&inc.back()<=i)inc.pop_back();int s=inc.size();
			for(int t=1;t<=T;t++)if(s>=t)New(i,inc[s-t],w(a[i],a[inc[s-t]]));
		}
	}
}

vector<int>dat[N];
inline void Ins(int l,int r,int w){w+=P[l]+Q[r];l++,r--;if(l>r||!w)return ;dat[l].push_back(w),dat[r+1].push_back(-w);}

inline void Cat_Tree()
{
	// for(int i=1;i<=n;i++)cout<<P[i]<<' ';cout<<'\n';
	// for(int i=1;i<=n;i++)cout<<Q[i]<<' ';cout<<'\n';
	for(int i=1;i<=n;i++)Ans[i]=P[i-1]+Q[i+1];
	inc.clear();for(int i=n;i>=1;i--)if(a[i]<=B)inc.push_back(i);
	for(int i=1;i<=S;i++)for(int j=0;j<T;j++)g[i][j]=0;for(int j=0;j<T;j++)pos[j]=0;
	for(int i=1;i<=n;i++)
	{
		// for(int j=1;j<i;j++)Ins(j,i,w(a[j],a[i]));
		for(int t=0;t<T;t++)if(pos[t])Ins(pos[t],i,w(a[pos[t]],a[i]));
		if(a[i]>B){for(int j=a[i];j<=S;j+=a[i])for(int t=0;t<T;t++)if(g[j][t])Ins(g[j][t],i,j);}

		if(a[i]<=B){for(int t=0;t<T-1;t++)pos[t]=pos[t+1];pos[T-1]=i;}
		else
		{
			for(int j=a[i];j<=S;j+=a[i]){for(int t=0;t<T-1;t++)g[j][t]=g[j][t+1];g[j][T-1]=i;}
			while(!inc.empty()&&inc.back()<=i)inc.pop_back();int s=inc.size();
			for(int t=1;t<=T;t++)if(s>=t)Ins(i,inc[s-t],w(a[i],a[inc[s-t]]));
		}
	}
	multiset<int>s;
	for(int i=1;i<=n;i++){for(int x:dat[i])if(x>0)s.insert(x);else s.erase(s.find(-x));if(!s.empty())Ans[i]=max(Ans[i],*s.rbegin());}
}

bool ED;

signed main()
{
    // int time_st=clock();
	cerr<<(&ST-&ED)/1024.0/1024<<endl;ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	// file(card);
	cin>>n>>S>>Type>>Tid;B=sqrt(S);for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=0;i<=B;i++)for(int j=0;j<=B;j++)if(i||j)gcd[i][j]=__gcd(i,j);
	Calc(P);if(Type==0)return cout<<P[n],0;reverse(a+1,a+n+1),Calc(Q),reverse(a+1,a+n+1),reverse(Q+1,Q+n+1);
	Cat_Tree();int sum=0;for(int i=1;i<=n;i++)sum^=(i*Ans[i]);cout<<P[n]<<' '<<sum<<'\n';
    // cerr<<(clock()-time_st)/1e6<<endl;return 0;
}