#include using ll = long long; #define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i) #define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i) #define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i) #define rreps(i, n) for (int i = ((int)(n)); i > 0; --i) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) #define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++) constexpr int inf = 2000'000'000; constexpr ll linf = 4000000000000000000ll; constexpr ll M7 = 1000000007ll; constexpr ll M09 = 1000000009ll; constexpr ll M9 = 998244353ll; #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) using namespace std; template class BinaryTrie { public: struct Node { int next[2]; int common; Node() : common(0) { next[0] = next[1] = -1; } }; private: T lazy; vector _nodes; public: BinaryTrie() : lazy(T(0)) { _nodes = vector(1, Node()); } void insert(const T &x) { int node_id = 0; for (int i = 0; i < B; ++i) { int c = ((x ^ lazy) >> (B - i - 1)) & 1; if (_nodes[node_id].next[c] == -1) { _nodes[node_id].next[c] = int(_nodes.size()); _nodes.push_back(Node()); } ++_nodes[node_id].common; node_id = _nodes[node_id].next[c]; } ++_nodes[node_id].common; } void erase(const T &x) { int node_id = 0; --_nodes[node_id].common; for (int i = 0; i < B; ++i) { int c = ((x ^ lazy) >> (B - i - 1)) & 1; assert(_nodes[node_id].next[c] != -1); node_id = _nodes[node_id].next[c]; --_nodes[node_id].common; } } int size() const { return _nodes[0].common; } bool empty() const { return size() == 0; } void clear() { _nodes = vector(1, Node(0)); lazy = T(0); } T min_element() const { assert(!empty()); int node_id = 0; T ret = 0; for (int i = 0; i < B; ++i) { int lz = lazy >> (B - i - 1) & 1; int nxt = lz; if (_nodes[node_id].next[nxt] == -1 || _nodes[_nodes[node_id].next[nxt]].common == 0) nxt ^= 1; int next_node_id = _nodes[node_id].next[nxt]; ret |= (T(nxt ^ lz) << (B - i - 1)); node_id = next_node_id; } return ret; } T max_element() const { assert(!empty()); int node_id = 0; T ret = 0; for (int i = 0; i < B; ++i) { int lz = lazy >> (B - i - 1) & 1; int nxt = lz ^ 1; if (_nodes[node_id].next[nxt] == -1 || _nodes[_nodes[node_id].next[nxt]].common == 0) nxt ^= 1; int next_node_id = _nodes[node_id].next[nxt]; ret |= (T(nxt ^ lz) << (B - i - 1)); node_id = next_node_id; } return ret; } int search_id(const T &x) { int node_id = 0; for (int i = 0; i < B; ++i) { int c = ((x ^ lazy) >> (B - i - 1)) & 1; int next_id = _nodes[node_id].next[c]; if (next_id == -1) return -1; node_id = next_id; } return node_id; } bool contains(const T &x) { int node_id = search_id(x); return node_id != -1 && _nodes[node_id].common > 0; } int count(const T &x) { int node_id = search_id(x); return node_id == -1 ? 0 : _nodes[node_id].common; } T operator[](int k) { // k番目のノードの文字列を返す assert(0 <= k && k < size()); int node_id = 0; T res = 0; for (int i = 0; i < B; ++i) { int lz = lazy >> (B - i - 1) & 1; int left = lz, right = lz ^ 1; if (_nodes[node_id].next[left] != -1 && _nodes[_nodes[node_id].next[left]].common > k) { node_id = _nodes[node_id].next[left]; } else { if (_nodes[node_id].next[left] != -1) k -= _nodes[_nodes[node_id].next[left]].common; node_id = _nodes[node_id].next[right]; res |= (T(1) << (B - i - 1)); } } return res; } void apply_xor(const T &x) { lazy ^= x; } const vector &nodes() { return _nodes; } vector dump() { vector ret; auto f = [&](auto f, int i, int node_id, T x) -> void { if (i == B) { for (int j = 0; j < _nodes[node_id].common; ++j) ret.push_back(x); return; } int lz = lazy >> (B - i - 1) & 1; int left = _nodes[node_id].next[lz]; int right = _nodes[node_id].next[lz ^ 1]; if (left != -1 && _nodes[left].common > 0) f(f, i + 1, left, x << 1); if (right != -1 && _nodes[right].common > 0) f(f, i + 1, right, (x << 1) | 1); }; f(f, 0, 0, 0); return ret; } template pair greater_min_sub(const T &x, int node_id, int i, T y, bool equal) const { // xより真に大きい/以上の値の中で最小のものの値, 存在しなければ0,false if (i == B) { if constexpr (strict) return equal ? make_pair(T(0), false) : make_pair(y, true); else return make_pair(y, true); } int b = (x >> (B - i - 1)) & 1; // xのi桁目 int lz = lazy >> (B - i - 1) & 1; int left = lz, right = lz ^ 1; if (equal) { // まだ上の桁がxと一致しているので、小さい方に存在するならそちらを選び、ないなら大きい方 if (b == 0 && _nodes[node_id].next[left] != -1 && _nodes[_nodes[node_id].next[left]].common > 0) { auto [res, ok] = greater_min_sub(x, _nodes[node_id].next[left], i + 1, y << 1, true); if (ok) return {res, true}; } if (_nodes[node_id].next[right] != -1 && _nodes[_nodes[node_id].next[right]].common > 0) { auto [res, ok] = greater_min_sub(x, _nodes[node_id].next[right], i + 1, (y << 1) | 1, b == 1); if (ok) return {res, true}; } } else { // 既に大きいことが確定しているので、0を優先して選ぶ if (_nodes[node_id].next[left] != -1 && _nodes[_nodes[node_id].next[left]].common > 0) { auto [res, ok] = greater_min_sub(x, _nodes[node_id].next[left], i + 1, y << 1, false); if (ok) return {res, true}; } if (_nodes[node_id].next[right] != -1 && _nodes[_nodes[node_id].next[right]].common > 0) { auto [res, ok] = greater_min_sub(x, _nodes[node_id].next[right], i + 1, (y << 1) | 1, false); if (ok) return {res, true}; } } return {0, false}; } pair gt_min(const T &x) const { // xより真に大きい値の中で最小のものの値 return greater_min_sub(x, 0, 0, 0, true); } pair geq_min(const T &x) const { // x以上の値の中で最小のものの値 return greater_min_sub(x, 0, 0, 0, true); } template pair less_max_sub(const T &x, int node_id, int i, T y, bool equal) const { if (i == B) { if constexpr (strict) return equal ? make_pair(T(0), false) : make_pair(y, true); else return make_pair(y, true); } int b = (x >> (B - i - 1)) & 1; // xのi桁目 int lz = lazy >> (B - i - 1) & 1; int left = lz, right = lz ^ 1; if (equal) { // まだ上の桁がxと一致しているので、大きい方に存在するならそちらを選び、ないなら小さい方 if (b == 1 && _nodes[node_id].next[right] != -1 && _nodes[_nodes[node_id].next[right]].common > 0) { auto [res, ok] = less_max_sub(x, _nodes[node_id].next[right], i + 1, (y << 1) | 1, true); if (ok) return {res, true}; } if (_nodes[node_id].next[left] != -1 && _nodes[_nodes[node_id].next[left]].common > 0) { auto [res, ok] = less_max_sub(x, _nodes[node_id].next[left], i + 1, y << 1, b == 0); if (ok) return {res, true}; } } else { // 既に小さいことが確定しているので、1を優先して選ぶ if (_nodes[node_id].next[right] != -1 && _nodes[_nodes[node_id].next[right]].common > 0) { auto [res, ok] = less_max_sub(x, _nodes[node_id].next[right], i + 1, (y << 1) | 1, false); if (ok) return {res, true}; } if (_nodes[node_id].next[left] != -1 && _nodes[_nodes[node_id].next[left]].common > 0) { auto [res, ok] = less_max_sub(x, _nodes[node_id].next[left], i + 1, y << 1, false); if (ok) return {res, true}; } } return {0, false}; } pair lt_max(const T &x) const { // xより真に小さい値の中で最大のものの値 return less_max_sub(x, 0, 0, 0, true); } pair leq_max(const T &x) const { // x以下の値の中で最大のものの値 return less_max_sub(x, 0, 0, 0, true); } template int count_less(const T &x) const { // x未満の値の個数 if (empty()) return 0; int node_id = 0; int ret = 0; for (int i = 0; i < B; ++i) { int b = (x >> (B - i - 1)) & 1; int lz = lazy >> (B - i - 1) & 1; int left = lz, right = lz ^ 1; if (b == 0) { // xのi桁目が0のとき if (_nodes[node_id].next[left] == -1) break; node_id = _nodes[node_id].next[left]; } else { if (_nodes[node_id].next[left] != -1) ret += _nodes[_nodes[node_id].next[left]].common; if (_nodes[node_id].next[right] == -1) break; node_id = _nodes[node_id].next[right]; } } if constexpr (!strict) { if (_nodes[node_id].next[0] == -1 && _nodes[node_id].next[1] == -1) { // 子が存在しない=そのノードがx丁度 ret += _nodes[node_id].common; } } return ret; } template int count_greater(const T &x) const { // xより大きい値の個数 if (empty()) return 0; int node_id = 0; int ret = 0; for (int i = 0; i < B; ++i) { int b = (x >> (B - i - 1)) & 1; int lz = lazy >> (B - i - 1) & 1; int left = lz, right = lz ^ 1; if (b == 1) { // xのi桁目が1のとき if (_nodes[node_id].next[right] == -1) break; node_id = _nodes[node_id].next[right]; } else { if (_nodes[node_id].next[right] != -1) ret += _nodes[_nodes[node_id].next[right]].common; if (_nodes[node_id].next[left] == -1) break; node_id = _nodes[node_id].next[left]; } } if constexpr (!strict) { if (_nodes[node_id].next[0] == -1 && _nodes[node_id].next[1] == -1) { // 子が存在しない=そのノードがx丁度 ret += _nodes[node_id].common; } } return ret; } int cout_lt(const T &x) const { return count_less(x); } int count_leq(const T &x) const { return count_less(x); } int count_gt(const T &x) const { return count_greater(x); } int count_geq(const T &x) const { return count_greater(x); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; ll k; cin >> n >> k; vector a(n); rep(i, n) cin >> a[i]; auto bsearch = [&](auto cmp, ll ok, ll ng) { while (abs(ng - ok) > 1) { ll mid = (ng + ok) / 2; if (cmp(mid)) ok = mid; else ng = mid; } return ok; }; BinaryTrie<30> trie; rep(i, n) trie.insert(a[i]); auto cmp = [&](ll x) -> bool { ll cnt = 0; rep(i, n) { trie.apply_xor(a[i]); cnt += trie.count_leq(x) - 1; trie.apply_xor(a[i]); } cnt /= 2; return cnt >= k; }; int ans = bsearch(cmp, (1ll << 30) - 1, -1); cout << ans << '\n'; }