#include <bits/stdc++.h>
namespace IO {
template <class Stream>#include <bits/stdc++.h>
namespace IO {
template <class Stream>
void write_int128(Stream& out, __int128 v) {
if (v >= 10) {
write_int128(out, v / 10);
}
out << (int) (v % 10);
}
template <class Stream>
Stream& fmtbase(Stream& out, const char* format) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
throw std::invalid_argument("Error Number of Parameters!");
}
out << *format;
}
return out;
}
template <class Stream, class... Nxt>
Stream& fmtbase(Stream& out, const char* format, const __int128& value, const Nxt&... nxt) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
write_int128(out, value);
return fmtbase(out, format + 2, nxt...);
}
out << *format;
}
throw std::invalid_argument("Error Number of Parameters!");
}
template <class Stream, class Fst, class... Nxt>
Stream& fmtbase(Stream& out, const char* format, const Fst& value, const Nxt&... nxt) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
out << value;
return fmtbase(out, format + 2, nxt...);
}
out << *format;
}
throw std::invalid_argument("Error Number of Parameters!");
}
template <class... Ps>
std::string to_string(const char* format, const Ps&... ps) {
std::stringstream ss;
fmtbase(ss, format, ps...);
return ss.str();
}
template <class... Ps>
std::ostream& fmtout(const char* format, const Ps&... ps) {
return fmtbase(std::cout, format, ps...);
}
template <class... Ps>
std::ostream& fmterr(const char* format, const Ps&... ps) {
return fmtbase(std::cerr, format, ps...);
}
std::istream& allin() {
return std::cin;
}
template <class Fst, class ... Nxt>
std::istream& allin(Fst& fst, Nxt&... nxt) {
std::cin >> fst;
return allin(nxt...);
}
template <class Iter>
std::istream& rangin(Iter begin, Iter end) {
while (begin != end) {
std::cin >> *begin;
begin++;
}
return std::cin;
}
namespace Fast {
bool sync = false;
char buf[1 << 23];
char *p1 = buf, *p2 = buf;
void sync_with_ios(bool s) {
sync = s;
}
inline char getchar() {
if (sync) {
return (char) std::cin.get();
}
else {
return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 1 << 22, stdin)), p1 == p2 ? EOF : *p1++;
}
}
void read() { }
template <class T, class... U>
void read(T& x, U&... us) {
x = 0;
T pos = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') {
pos = -1;
}
c = getchar();
}
while (isdigit(c)) {
x = 10 * x + c - '0';
c = getchar();
}
x *= pos;
read(us...);
}
template <class T>
void write(const T& t) {
if (t > 10) {
write(t / 10);
}
std::cout << (int) (t % 10);
}
}
}
namespace Solve {
using namespace IO;
using ll = long long;
using ul = unsigned long long;
using db = double;
using ld = long double;
using ui = unsigned;
using ib = __int128;
using ub = __uint128_t;
int const INF = std::numeric_limits<int>::max();
int const NINF = std::numeric_limits<int>::min();
ll const LINF = std::numeric_limits<ll>::max();
ll const LNINF = std::numeric_limits<ll>::min();
ld const EPS = 1e-8;
std::mt19937_64 mt;
ll rnd(ll l, ll r) {
return std::uniform_int_distribution<ll>(l, r)(mt);
}
template <class T>
inline int isz(const T& v) {
return v.size();
}
template <class T>
inline T& ckmx(T& a, T b) {
return a < b ? (a = b) : a;
}
template <class T>
inline T& ckmi(T& a, T b) {
return b < a ? (a = b) : a;
}
int const N = (1 << 19) + 10;
int const LMT = 5;
int const LGN = 19;
int type, testid;
int n, S;
int a[N + 1];
ll f[N + 1];
ll g[N + 1];
std::vector<int> sml;
int h[N + 1][2];
ll pmx[LGN + 1][N + 1];
ll smx[LGN + 1][N + 1];
ll res[N + 1];
int vis[N + 1];
int cost(int i, int j) {
int d = std::__gcd(i, j);
ll lcm = (ll) i * j / d;
if (lcm > S) {
return 0;
}
return S / lcm * lcm;
}
bool small(int x) {
return (ll) x * x <= S;
}
void calc(int a[N + 1], ll f[N + 1]) {
sml.clear();
memset(h, 0, sizeof h);
for (int i = 1; i <= n; i++) {
if (small(a[i])) {
sml.push_back(i);
}
}
f[0] = 0;
for (int i = 1; i <= n; i++) {
ckmx(f[i], f[i - 1]);
{
auto it = std::lower_bound(sml.begin(), sml.end(), i);
for (int k = 1; k <= LMT && it != sml.begin(); k++) {
it--;
ckmx(f[i], f[*it] + cost(a[*it], a[i]));
}
}
if (!small(a[i])) {
for (int j = S / a[i] * a[i]; j >= S / 2; j -= a[i]) {
if (h[j][0]) {
ckmx(f[i], f[h[j][0]] + j);
}
if (h[j][1]) {
ckmx(f[i], f[h[j][1]] + j);
}
}
}
{
auto it = std::upper_bound(sml.begin(), sml.end(), i);
for (int k = 1; k <= LMT && it != sml.end(); k++, it++) {
ckmx(f[*it], f[i] + cost(a[i], a[*it]));
}
}
if (!small(a[i])) {
for (int j = S / a[i] * a[i]; j >= S / 2; j -= a[i]) {
if (h[j][1]) {
h[j][0] = h[j][1];
h[j][1] = i;
}
else if (h[j][0]) {
h[j][1] = i;
}
else {
h[j][0] = i;
}
}
}
}
}
void range_max(int l, int r, ll v) {
ckmx(l, 1);
ckmi(r, n);
if (l > r) {
return;
}
int d = LGN - (l != r ? std::__lg(l ^ r) + 1 : 0);
ckmx(pmx[d][l], v);
ckmx(smx[d][r], v);
}
void solve(int i, int l, int r) {
if (l == r) {
ckmx(res[l], pmx[i][l]);
ckmx(res[r], smx[i][l]);
}
else {
int mid = (l + r) >> 1;
solve(i + 1, l, mid);
solve(i + 1, mid + 1, r);
for (int k = r - 1; k >= mid + 1; k--) {
smx[i][k] = std::max(smx[i][k], smx[i][k + 1]);
}
for (int k = l + 1; k <= mid; k++) {
pmx[i][k] = std::max(pmx[i][k], pmx[i][k - 1]);
}
for (int k = l; k <= r; k++) {
ckmx(res[k], smx[i][k]);
ckmx(res[k], pmx[i][k]);
}
}
}
void main() {
std::cin >> n >> S >> type >> testid;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
if (small(a[i])) {
sml.push_back(i);
}
}
std::reverse(a + 1, a + n + 1);
calc(a, g);
std::reverse(g + 1, g + n + 1);
std::reverse(a + 1, a + n + 1);
calc(a, f);
ll ans = 0;
for (int i = 1; i <= n; i++) {
ckmx(ans, f[i]);
}
fmtout("{}", ans);
if (type == 1) {
memset(h, 0, sizeof h);
for (int i = 1; i <= n; i++) {
range_max(i + 1, n, f[i]);
range_max(1, i - 1, g[i]);
range_max(i, i, f[i - 1] + g[i + 1]);
{
auto it = std::lower_bound(sml.begin(), sml.end(), i);
for (int k = 1; k <= LMT && it != sml.begin(); k++) {
it--;
range_max(*it + 1, i - 1, f[*it] + cost(a[*it], a[i]) + g[i]);
}
}
if (!small(a[i])) {
for (int j = S / a[i] * a[i]; j >= S / 2; j -= a[i]) {
if (h[j][0] && !vis[h[j][0]]) {
vis[h[j][0]] = 1;
range_max(h[j][0] + 1, i - 1, f[h[j][0]] + j + g[i]);
}
if (h[j][1] && !vis[h[j][1]]) {
vis[h[j][1]] = 1;
range_max(h[j][1] + 1, i - 1, f[h[j][1]] + j + g[i]);
}
}
for (int j = S / a[i] * a[i]; j >= S / 2; j -= a[i]) {
if (h[j][0]) {
vis[h[j][0]] = 0;
}
if (h[j][1]) {
vis[h[j][1]] = 0;
}
}
}
{
auto it = std::upper_bound(sml.begin(), sml.end(), i);
for (int k = 1; k <= LMT && it != sml.end(); k++, it++) {
ckmx(f[*it], f[i] + cost(a[i], a[*it]));
range_max(i + 1, *it - 1, f[i] + cost(a[i], a[*it]) + g[*it]);
}
}
if (!small(a[i])) {
for (int j = S / a[i] * a[i]; j >= S / 2; j -= a[i]) {
if (h[j][1]) {
h[j][0] = h[j][1];
h[j][1] = i;
}
else if (h[j][0]) {
h[j][1] = i;
}
else {
h[j][0] = i;
}
}
}
}
solve(0, 0, (1 << LGN) - 1);
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans ^= i * res[i];
}
fmtout(" {}", ans);
}
fmtout("\n");
}
void init() {
}
void clear() {
}
}
signed main() {
#ifndef ONLINE_JUDGE
auto input_file = freopen("card.in", "r", stdin);
auto output_file = freopen("card.out", "w", stdout);
#endif
auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
IO::fmterr("seed: {}\n", seed);
Solve::mt.seed(seed);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
// std::cin >> t;
Solve::init();
for (int id = 1; id <= t; id++) {
Solve::main();
Solve::clear();
}
#ifndef ONLINE_JUDGE
std::cout.flush();
fclose(input_file);
fclose(output_file);
#endif
return 0;
}
void write_int128(Stream& out, __int128 v) {
if (v >= 10) {
write_int128(out, v / 10);
}
out << (int) (v % 10);
}
template <class Stream>
Stream& fmtbase(Stream& out, const char* format) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
throw std::invalid_argument("Error Number of Parameters!");
}
out << *format;
}
return out;
}
template <class Stream, class... Nxt>
Stream& fmtbase(Stream& out, const char* format, const __int128& value, const Nxt&... nxt) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
write_int128(out, value);
return fmtbase(out, format + 2, nxt...);
}
out << *format;
}
throw std::invalid_argument("Error Number of Parameters!");
}
template <class Stream, class Fst, class... Nxt>
Stream& fmtbase(Stream& out, const char* format, const Fst& value, const Nxt&... nxt) {
for (; *format; format++) {
if (*format == '{' && *(format + 1) == '}') {
out << value;
return fmtbase(out, format + 2, nxt...);
}
out << *format;
}
throw std::invalid_argument("Error Number of Parameters!");
}
template <class... Ps>
std::string to_string(const char* format, const Ps&... ps) {
std::stringstream ss;
fmtbase(ss, format, ps...);
return ss.str();
}
template <class... Ps>
std::ostream& fmtout(const char* format, const Ps&... ps) {
return fmtbase(std::cout, format, ps...);
}
template <class... Ps>
std::ostream& fmterr(const char* format, const Ps&... ps) {
return fmtbase(std::cerr, format, ps...);
}
std::istream& allin() {
return std::cin;
}
template <class Fst, class ... Nxt>
std::istream& allin(Fst& fst, Nxt&... nxt) {
std::cin >> fst;
return allin(nxt...);
}
template <class Iter>
std::istream& rangin(Iter begin, Iter end) {
while (begin != end) {
std::cin >> *begin;
begin++;
}
return std::cin;
}
namespace Fast {
bool sync = false;
char buf[1 << 23];
char *p1 = buf, *p2 = buf;
void sync_with_ios(bool s) {
sync = s;
}
inline char getchar() {
if (sync) {
return (char) std::cin.get();
}
else {
return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 1 << 22, stdin)), p1 == p2 ? EOF : *p1++;
}
}
void read() { }
template <class T, class... U>
void read(T& x, U&... us) {
x = 0;
T pos = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') {
pos = -1;
}
c = getchar();
}
while (isdigit(c)) {
x = 10 * x + c - '0';
c = getchar();
}
x *= pos;
read(us...);
}
template <class T>
void write(const T& t) {
if (t > 10) {
write(t / 10);
}
std::cout << (int) (t % 10);
}
}
}
namespace Solve {
using namespace IO;
using ll = long long;
using ul = unsigned long long;
using db = double;
using ld = long double;
using ui = unsigned;
using ib = __int128;
using ub = __uint128_t;
int const INF = std::numeric_limits<int>::max();
int const NINF = std::numeric_limits<int>::min();
ll const LINF = std::numeric_limits<ll>::max();
ll const LNINF = std::numeric_limits<ll>::min();
ld const EPS = 1e-8;
std::mt19937_64 mt;
ll rnd(ll l, ll r) {
return std::uniform_int_distribution<ll>(l, r)(mt);
}
template <class T>
inline int isz(const T& v) {
return v.size();
}
template <class T>
inline T& ckmx(T& a, T b) {
return a < b ? (a = b) : a;
}
template <class T>
inline T& ckmi(T& a, T b) {
return b < a ? (a = b) : a;
}
int const N = (1 << 19) + 10;
int const LMT = 5;
int const LGN = 19;
int type, testid;
int n, S;
int a[N + 1];
ll f[N + 1];
ll g[N + 1];
std::vector<int> sml;
int h[N + 1][2];
ll pmx[LGN + 1][N + 1];
ll smx[LGN + 1][N + 1];
ll res[N + 1];
int vis[N + 1];
int cost(int i, int j) {
int d = std::__gcd(i, j);
ll lcm = (ll) i * j / d;
if (lcm > S) {
return 0;
}
return S / lcm * lcm;
}
bool small(int x) {
return (ll) x * x <= S;
}
void calc(int a[N + 1], ll f[N + 1]) {
sml.clear();
memset(h, 0, sizeof h);
for (int i = 1; i <= n; i++) {
if (small(a[i])) {
sml.push_back(i);
}
}
f[0] = 0;
for (int i = 1; i <= n; i++) {
ckmx(f[i], f[i - 1]);
{
auto it = std::lower_bound(sml.begin(), sml.end(), i);
for (int k = 1; k <= LMT && it != sml.begin(); k++) {
it--;
ckmx(f[i], f[*it] + cost(a[*it], a[i]));
}
}
if (!small(a[i])) {
for (int j = S / a[i] * a[i]; j >= S / 2; j -= a[i]) {
if (h[j][0]) {
ckmx(f[i], f[h[j][0]] + j);
}
if (h[j][1]) {
ckmx(f[i], f[h[j][1]] + j);
}
}
}
{
auto it = std::upper_bound(sml.begin(), sml.end(), i);
for (int k = 1; k <= LMT && it != sml.end(); k++, it++) {
ckmx(f[*it], f[i] + cost(a[i], a[*it]));
}
}
if (!small(a[i])) {
for (int j = S / a[i] * a[i]; j >= S / 2; j -= a[i]) {
if (h[j][1]) {
h[j][0] = h[j][1];
h[j][1] = i;
}
else if (h[j][0]) {
h[j][1] = i;
}
else {
h[j][0] = i;
}
}
}
}
}
void range_max(int l, int r, ll v) {
ckmx(l, 1);
ckmi(r, n);
if (l > r) {
return;
}
int d = LGN - (l != r ? std::__lg(l ^ r) + 1 : 0);
ckmx(pmx[d][l], v);
ckmx(smx[d][r], v);
}
void solve(int i, int l, int r) {
if (l == r) {
ckmx(res[l], pmx[i][l]);
ckmx(res[r], smx[i][l]);
}
else {
int mid = (l + r) >> 1;
solve(i + 1, l, mid);
solve(i + 1, mid + 1, r);
for (int k = r - 1; k >= mid + 1; k--) {
smx[i][k] = std::max(smx[i][k], smx[i][k + 1]);
}
for (int k = l + 1; k <= mid; k++) {
pmx[i][k] = std::max(pmx[i][k], pmx[i][k - 1]);
}
for (int k = l; k <= r; k++) {
ckmx(res[k], smx[i][k]);
ckmx(res[k], pmx[i][k]);
}
}
}
void main() {
std::cin >> n >> S >> type >> testid;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
if (small(a[i])) {
sml.push_back(i);
}
}
std::reverse(a + 1, a + n + 1);
calc(a, g);
std::reverse(g + 1, g + n + 1);
std::reverse(a + 1, a + n + 1);
calc(a, f);
ll ans = 0;
for (int i = 1; i <= n; i++) {
ckmx(ans, f[i]);
}
fmtout("{}", ans);
if (type == 1) {
memset(h, 0, sizeof h);
for (int i = 1; i <= n; i++) {
range_max(i + 1, n, f[i]);
range_max(1, i - 1, g[i]);
range_max(i, i, f[i - 1] + g[i + 1]);
{
auto it = std::lower_bound(sml.begin(), sml.end(), i);
for (int k = 1; k <= LMT && it != sml.begin(); k++) {
it--;
range_max(*it + 1, i - 1, f[*it] + cost(a[*it], a[i]) + g[i]);
}
}
if (!small(a[i])) {
for (int j = S / a[i] * a[i]; j >= S / 2; j -= a[i]) {
if (h[j][0] && !vis[h[j][0]]) {
vis[h[j][0]] = 1;
range_max(h[j][0] + 1, i - 1, f[h[j][0]] + j + g[i]);
}
if (h[j][1] && !vis[h[j][1]]) {
vis[h[j][1]] = 1;
range_max(h[j][1] + 1, i - 1, f[h[j][1]] + j + g[i]);
}
}
for (int j = S / a[i] * a[i]; j >= S / 2; j -= a[i]) {
if (h[j][0]) {
vis[h[j][0]] = 0;
}
if (h[j][1]) {
vis[h[j][1]] = 0;
}
}
}
{
auto it = std::upper_bound(sml.begin(), sml.end(), i);
for (int k = 1; k <= LMT && it != sml.end(); k++, it++) {
ckmx(f[*it], f[i] + cost(a[i], a[*it]));
range_max(i + 1, *it - 1, f[i] + cost(a[i], a[*it]) + g[*it]);
}
}
if (!small(a[i])) {
for (int j = S / a[i] * a[i]; j >= S / 2; j -= a[i]) {
if (h[j][1]) {
h[j][0] = h[j][1];
h[j][1] = i;
}
else if (h[j][0]) {
h[j][1] = i;
}
else {
h[j][0] = i;
}
}
}
}
solve(0, 0, (1 << LGN) - 1);
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans ^= i * res[i];
}
fmtout(" {}", ans);
}
fmtout("\n");
}
void init() {
}
void clear() {
}
}
signed main() {
#ifndef ONLINE_JUDGE
auto input_file = freopen("card.in", "r", stdin);
auto output_file = freopen("card.out", "w", stdout);
#endif
auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
IO::fmterr("seed: {}\n", seed);
Solve::mt.seed(seed);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
// std::cin >> t;
Solve::init();
for (int id = 1; id <= t; id++) {
Solve::main();
Solve::clear();
}
#ifndef ONLINE_JUDGE
std::cout.flush();
fclose(input_file);
fclose(output_file);
#endif
return 0;
}