#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,m,tp,testid;
int a[500005],occ[500005][2];
ll _val[500005][2];

#define maxlim 800
int lim;
int _gcd[maxlim + 5][maxlim + 5];

ll res[500005];//buc 是小项的贡献,comb 是给小项的贡献
ll f[500005],g[500005];
vector <pii> S[500005];
inline int calc(int x,int y){//assume x <= lim
	uint L = (uint)x * y / _gcd[x][y % x];
	return (m / L) * L;
}

inline int _calc(int x,int y){
	ll L = 1ll * x / gcd(x,y) * y;
	return (m / L) * L;
}

ll result[500005];

ll ST[20][500005];
const int _mem = 10000000;
void upd(int l,int r,ll v){
	if(l > r) return;
	int x = __lg(r - l + 1);
	chkmax(ST[x][l],v);chkmax(ST[x][r - (1 << x) + 1],v);
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&tp,&testid);
	while((lim + 1) * (lim + 1) <= m) lim++;
	rep(i,0,lim){
		_gcd[i][0] = i;
		rep(j,1,i) _gcd[i][j] = _gcd[j][i % j];
	}
	rep(i,1,n){
		scanf("%d",&a[i]);
		chkmin(a[i],m + 1);
	}

	int p1 = 0,p2 = 0,p3 = 0,sum,pos = 1;
	memset(res,0xcf,sizeof(res));
	rep(i,1,n){
		while(f[pos] + m < f[i - 1]) pos++;
		f[i] = f[i - 1];
		if(a[i] <= lim){
			sum = 0;
			per(k,i - 1,1){
				sum += (a[k] <= lim);
				if(sum == 3) break;
				chkmax(f[i],f[k] + calc(a[i],a[k]));
			}
			p3 = p2;
			p2 = p1;
			p1 = i;
		}else{
			if(p1) chkmax(f[i],f[p1] + calc(a[p1],a[i]));
			if(p2) chkmax(f[i],f[p2] + calc(a[p2],a[i]));

			if(i - pos <= 50){
				rep(k,pos,i - 1) chkmax(f[i],f[k] + _calc(a[i],a[k]));
			}else{
				for(int v = a[i];v <= m;v += a[i]) chkmax(f[i],res[v]);
			}
			for(int v = a[i];v <= m;v += a[i]) chkmax(res[v],f[i] + (m / v) * v);	
		}
	}

	memset(res,0xcf,sizeof(res));
	p1 = p2 = p3 = pos = n + 1;
	per(i,n,1){
		while(g[pos] + m < g[i + 1]) pos--;
		g[i] = g[i + 1];
		if(a[i] <= lim){
			sum = 0;
			rep(k,i + 1,n){
				sum += (a[k] <= lim);
				if(sum == 3) break;
				chkmax(g[i],g[k] + calc(a[i],a[k]));
			}
			p3 = p2;
			p2 = p1;
			p1 = i;
		}else{
			if(p1 != n + 1) chkmax(g[i],g[p1] + calc(a[p1],a[i]));
			if(p2 != n + 1) chkmax(g[i],g[p2] + calc(a[p2],a[i]));

			if(pos - i <= 50){
				rep(k,i + 1,pos) chkmax(g[i],g[k] + _calc(a[i],a[k]));
			}else{
				for(int v = a[i];v <= m;v += a[i]) chkmax(g[i],res[v]);
			}
			for(int v = a[i];v <= m;v += a[i]) chkmax(res[v],g[i] + (m / v) * v);	
		}
	}	

	p1 = p2 = p3 = 0;
	rep(i,1,n){
		if(a[i] <= lim){
			p3 = p2;
			p2 = p1;
			p1 = i;
		}
		if(p1) upd(p1 + 1,i - 1,f[p1] + g[i] + calc(a[p1],a[i]));
		if(p2) upd(p2 + 1,i - 1,f[p2] + g[i] + calc(a[p2],a[i]));	
		if(p3) upd(p3 + 1,i - 1,f[p3] + g[i] + calc(a[p3],a[i]));
	}

	p1 = p2 = p3 = n + 1;
	per(i,n,1){
		if(a[i] <= lim){
			p3 = p2;
			p2 = p1;
			p1 = i;
		}
		if(p1 != n + 1) upd(i + 1,p1 - 1,f[i] + g[p1] + calc(a[p1],a[i]));
		if(p2 != n + 1) upd(i + 1,p2 - 1,f[i] + g[p2] + calc(a[p2],a[i]));	
		if(p3 != n + 1) upd(i + 1,p3 - 1,f[i] + g[p3] + calc(a[p3],a[i]));		
	}
	rep(i,1,n) chkmax(result[i],f[i - 1] + g[i + 1]);

	rep(i,1,n){
		if(a[i] <= lim) continue;

		for(int v = a[i];v <= m;v += a[i]){
			if(occ[v][0]) upd(occ[v][0] + 1,i - 1,_val[v][0] + g[i] + (m / v) * v);
			if(occ[v][1]) chkmax(result[occ[v][0]],_val[v][1] + g[i] + (m / v) * v);
			occ[v][1] = occ[v][0];_val[v][1] = _val[v][0];
			occ[v][0] = i;_val[v][0] = f[i];
		}
	}

	per(i,18,1){
		rep(j,1,n){
			if(j + (1 << i) - 1 > n) break;
			chkmax(ST[i - 1][j],ST[i][j]);
			chkmax(ST[i - 1][j + (1 << (i - 1))],ST[i][j]);
		}
	}
	rep(i,1,n) chkmax(result[i],ST[0][i]);
	ll output = 0;
	rep(i,1,n) output ^= 1ll * i * result[i];
//	rep(i,1,n) printf("%lld ",result[i]);
//	printf("\n");
	if(!tp) printf("%lld\n",f[n]);
	else printf("%lld %lld\n",f[n],output);
	return 0;
}

answer.code: In function ‘int _calc(int, int)’:
answer.code:65:26: error: ‘gcd’ was not declared in this scope; did you mean ‘_gcd’?
   65 |         ll L = 1ll * x / gcd(x,y) * y;
      |                          ^~~
      |                          _gcd
answer.code: In function ‘int main()’:
answer.code:82:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   82 |         scanf("%d%d%d%d",&n,&m,&tp,&testid);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:89:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   89 |                 scanf("%d",&a[i]);
      |                 ~~~~~^~~~~~~~~~~~