#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef LOCAL # include "debug_print.hpp" # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast(0)) #endif using namespace std; namespace io { template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } template istream &operator>>(istream &is, array &v) { for (auto &x : v) is >> x; return is; } template istream& cin_tuple_impl(istream &is, T &t) { if constexpr (N < std::tuple_size::value) { auto &x = std::get(t); is >> x; cin_tuple_impl(is, t); } return is; } template istream &operator>>(istream &is, tuple &t) { return cin_tuple_impl(is, t); } template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template ostream &operator<<(ostream &os, const array &v) { size_t n = v.size(); for (size_t i = 0; i < n; i++) { if (i) os << " "; os << v[i]; } return os; } template ostream& cout_tuple_impl(ostream &os, const T &t) { if constexpr (N < std::tuple_size::value) { if constexpr (N > 0) os << " "; const auto &x = std::get(t); os << x; cout_tuple_impl(os, t); } return os; } template ostream &operator<<(ostream &os, const tuple &t) { return cout_tuple_impl(os, t); } void in() {} template void in(T &t, U &...u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template void outr(const T &t, const U &...u) { cout << t; outr(u...); } void __attribute__((constructor)) _c() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } } // namespace io using io::in; using io::out; using io::outr; using ll = long long; using D = double; using LD = long double; using P = pair; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using i128 = __int128; using u128 = unsigned __int128; using vi = vector; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template using vvvvc = vector>; template using vvvvvc = vector>; #define vv(type, name, h, ...) \ vector> name(h, vector(__VA_ARGS__)) #define vvv(type, name, h, w, ...) \ vector>> name( \ h, vector>(w, vector(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector>>> name( \ a, vector>>( \ b, vector>(c, vector(__VA_ARGS__)))) template using PQ = priority_queue>; template using minPQ = priority_queue, greater>; #define rep1(a) for(ll i = 0; i < a; i++) #define rep2(i, a) for(ll i = 0; i < a; i++) #define rep3(i, a, b) for(ll i = a; i < b; i++) #define rep4(i, a, b, c) for(ll i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep1(a) for(ll i = (a)-1; i >= 0; i--) #define rrep2(i, a) for(ll i = (a)-1; i >= 0; i--) #define rrep3(i, a, b) for(ll i = (b)-1; i >= a; i--) #define rrep4(i, a, b, c) for(ll i = (b)-1; i >= a; i -= c) #define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__) #define for_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s))) #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) #define SZ(v) ll(v.size()) #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(c, x) distance((c).begin(), lower_bound(ALL(c), (x))) #define UB(c, x) distance((c).begin(), upper_bound(ALL(c), (x))) template T SUM(const vector &v) { T res = 0; for(auto &&a : v) res += a; return res; } template vector> RLE(const vector &v) { if (v.empty()) return {}; T cur = v.front(); int cnt = 1; vector> res; for (int i = 1; i < (int)v.size(); i++) { if (cur == v[i]) cnt++; else { res.emplace_back(cur, cnt); cnt = 1; cur = v[i]; } } res.emplace_back(cur, cnt); return res; } template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, true : false); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, true : false); } void YESNO(bool flag) { out(flag ? "YES" : "NO"); } void yesno(bool flag) { out(flag ? "Yes" : "No"); } int popcnt(int x) { return __builtin_popcount(x); } int popcnt(u32 x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } int popcnt(u64 x) { return __builtin_popcountll(x); } int popcnt_sgn(int x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(ll x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(u64 x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int highbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int highbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int highbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int highbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template T get_bit(T x, int k) { return x >> k & 1; } template T set_bit(T x, int k) { return x | T(1) << k; } template T reset_bit(T x, int k) { return x & ~(T(1) << k); } template T flip_bit(T x, int k) { return x ^ T(1) << k; } template T popf(deque &que) { T a = que.front(); que.pop_front(); return a; } template T popb(deque &que) { T a = que.back(); que.pop_back(); return a; } template T pop(queue &que) { T a = que.front(); que.pop(); return a; } template T pop(stack &que) { T a = que.top(); que.pop(); return a; } template T pop(PQ &que) { T a = que.top(); que.pop(); return a; } template T pop(minPQ &que) { T a = que.top(); que.pop(); return a; } template ll binary_search(F check, ll ok, ll ng, bool check_ok = true) { if (check_ok) assert(check(ok)); while (abs(ok - ng) > 1) { ll mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; } template ll binary_search_real(F check, double ok, double ng, int iter = 60) { for (int _ = 0; _ < iter; _++) { double mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return (ok + ng) / 2; } // max x s.t. b*x <= a ll div_floor(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b - (a % b < 0); } // max x s.t. b*x < a ll div_under(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b - (a % b <= 0); } // min x s.t. b*x >= a ll div_ceil(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b + (a % b > 0); } // min x s.t. b*x > a ll div_over(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b + (a % b >= 0); } // x = a mod b (b > 0), 0 <= x < b ll modulo(ll a, ll b) { assert(b > 0); ll c = a % b; return c < 0 ? c + b : c; } // (q,r) s.t. a = b*q + r, 0 <= r < b (b > 0) // div_floor(a,b), modulo(a,b) pair divmod(ll a, ll b) { ll q = div_floor(a,b); return {q, a - b*q}; } template struct BinaryTrie { public: struct Node { Node *nxt[2]; int exist; vector accept; Node(): nxt{nullptr, nullptr}, exist(0) {} }; Node *root; T lazy; explicit BinaryTrie(): root(new Node()), lazy(T(0)) {} void insert(const T &x, int idx = -1) { insert(root, x, MAX_LOG, 1, idx); } void erase(const T &x) { insert(root, x, MAX_LOG, -1, -1); } Node *find(const T &x) { return find(root, x, MAX_LOG); } int count(const T &x) { Node *nx = find(x); return nx == nullptr ? 0 : nx->exist; } pair min_element() { assert(root->exist > 0); return kth_element(0); } pair max_element() { assert(root->exist > 0); return kth_element(root->exist - 1); } pair kth_element(int k) { assert(0 <= k and k < root->exist); return kth_element(root, k, MAX_LOG); } int count_less(const T &x) { return count_less(root, x, MAX_LOG); } int count_leq(const T &x) { return count_less(root, x+1, MAX_LOG); } int count_greater(const T &x) { return root->exist - count_less(root, x+1, MAX_LOG); } int count_geq(const T &x) { return root->exist - count_less(root, x, MAX_LOG); } void operate_xor(const T &x) { lazy ^= x; } private: void insert(Node *n_cur, const T &x, int depth, int delta, int idx) { if (depth == -1) { n_cur->exist += delta; if (idx != -1) n_cur->accept.emplace_back(idx); } else { bool nxt_01 = (lazy >> depth & 1) ^ (x >> depth & 1); if(!n_cur->nxt[nxt_01]) n_cur->nxt[nxt_01] = new Node(); insert(n_cur->nxt[nxt_01], x, depth - 1, delta, idx); n_cur->exist += delta; } } Node *find(Node *n_cur, const T &x, int depth) { if (depth == -1) { return n_cur; } else { bool nxt_01 = (lazy >> depth & 1) ^ (x >> depth & 1); Node *n_nxt = n_cur->nxt[nxt_01]; return n_nxt == nullptr ? n_nxt : find(n_nxt, x, depth - 1); } } pair kth_element(Node *n_cur, int k, int depth) { if (depth == -1) { return make_pair(0, n_cur); } else { bool nxt_01 = lazy >> depth & 1; int comp = n_cur->nxt[nxt_01] == nullptr ? 0 : n_cur->nxt[nxt_01]->exist; if (comp <= k) { pair ret = kth_element( n_cur->nxt[nxt_01 ^ 1], k - comp, depth - 1); ret.first |= T(1) << depth; return ret; } else{ return kth_element(n_cur->nxt[nxt_01], k, depth - 1); } } } int count_less(Node *n_cur, const T &x, int depth) { if (depth == -1) return 0; int ret = 0; bool nxt_01 = lazy >> depth & 1; bool xi = x >> depth & 1; if (xi and n_cur->nxt[nxt_01] != nullptr) ret += n_cur->nxt[nxt_01]->exist; if (n_cur->nxt[nxt_01 ^ xi] != nullptr) ret += count_less(n_cur->nxt[nxt_01 ^ xi], x, depth - 1); return ret; } }; template struct BinaryTrie_Pool { struct Node { int nxt[2]; int exist; vector accept; Node(): nxt{-1, -1}, exist(0) {} }; vector nodes; int root; T lazy; explicit BinaryTrie_Pool(): root(0), lazy(T(0)) { nodes.emplace_back(Node()); } void insert(const T &x, int delta, int idx = -1) { int n_cur = root; for (int depth = MAX_LOG - 1; depth >= 0; depth--) { bool nxt_01 = (x >> depth & 1) ^ (lazy >> depth & 1); if (nodes[n_cur].nxt[nxt_01] == -1) { nodes[n_cur].nxt[nxt_01] = (int)nodes.size(); nodes.emplace_back(Node()); } nodes[n_cur].exist += delta; n_cur = nodes[n_cur].nxt[nxt_01]; } nodes[n_cur].exist += delta; if(idx != -1) nodes[n_cur].accept.emplace_back(idx); } void insert(const T &x, int idx = -1) { insert(x, 1, idx); } void erase(const T &x) { insert(x, -1, -1); } int find(const T &x) { int n_cur = root; for (int depth = MAX_LOG - 1; depth >= 0; depth--) { bool nxt_01 = (x >> depth & 1) ^ (lazy >> depth & 1); int n_nxt = nodes[n_cur].nxt[nxt_01]; if (n_nxt == -1) return -1; n_cur = n_nxt; } return n_cur; } int count(const T &x) { int nx = find(x); return nx == -1 ? 0 : nodes[nx].exist; } pair kth_element(int n_cur, int k, int depth) { if (depth == -1) return make_pair(0, n_cur); bool nxt_01 = (lazy >> depth) & 1; int comp = nodes[n_cur].nxt[nxt_01] == -1 ? 0 : nodes[n_cur].nxt[nxt_01].exist; if (comp <= k) { pair ret = kth_element( nodes[n_cur].nxt[nxt_01 ^ 1], k - comp, depth - 1); ret.first |= T(1) << depth; return ret; } else{ return kth_element(nodes[n_cur].nxt[nxt_01], k, depth-1); } } pair kth_element(int k) { assert(0 <= k and k < nodes[root].exist); int n_cur = root; T ret = 0; for (int depth = MAX_LOG - 1; depth >= 0; depth--) { bool nxt_01 = (lazy >> depth) & 1; int comp = nodes[n_cur].nxt[nxt_01] == -1 ? 0 : nodes[n_cur].nxt[nxt_01].exist; if (comp <= k) { k -= comp; n_cur = nodes[n_cur].nxt[nxt_01 ^ 1]; ret |= T(1) << depth; } else{ n_cur = nodes[n_cur].nxt[nxt_01]; } } return make_pair(ret, n_cur); // return kth_element(root, k, MAX_LOG - 1); } pair min_element() { assert(nodes[root].exist > 0); return kth_element(0); } pair max_element() { assert(nodes[root].exist > 0); return kth_element(nodes[root].exist - 1); } int count_less(int n_cur, const T &x, int depth) { if (depth == -1) return 0; int ret = 0; bool nxt_01 = (lazy >> depth) & 1; bool xi = (x >> depth) & 1; if (xi and nodes[n_cur].nxt[nxt_01] != -1) ret += nodes[nodes[n_cur].nxt[nxt_01]].exist; if (nodes[n_cur].nxt[nxt_01 ^ xi] != -1) ret += count_less(nodes[n_cur].nxt[nxt_01 ^ xi], x, depth - 1); return ret; } int count_less(const T &x) { int ret = 0; int n_cur = root; for (int depth = MAX_LOG - 1; depth >= 0; depth--) { bool nxt_01 = (lazy >> depth) & 1; bool xi = (x >> depth) & 1; if (xi and nodes[n_cur].nxt[nxt_01] != -1) { ret += nodes[nodes[n_cur].nxt[nxt_01]].exist; } if (nodes[n_cur].nxt[nxt_01 ^ xi] != -1) { n_cur = nodes[n_cur].nxt[nxt_01 ^ xi]; } else break; } return ret; // return count_less(root, x, MAX_LOG - 1); } int count_leq(const T &x) { return count_less(x+1); } int count_greater(const T &x) { return nodes[root].exist - count_less(x+1); } int count_geq(const T &x) { return nodes[root].exist - count_less(x); } void operate_xor(const T &x) { lazy ^= x; } }; int main() { ll n,k; in(n,k); vector a(n); in(a); BinaryTrie_Pool bt; rep(i,n) bt.insert(a[i]); int ans = binary_search([&](int m){ ll cleq = -n; rep(i,n) { bt.operate_xor(a[i]); cleq += bt.count_leq(m); bt.operate_xor(a[i]); } cleq /= 2; return cleq >= k; }, (1<<30)-1, -1, false); out(ans); }