#include "xorting.h"
#include <bits/stdc++.h>

using namespace std;

namespace atcoder {
	// Reference:
	// D. Gusfield,
	// Algorithms on Strings, Trees, and Sequences: Computer Science and
	// Computational Biology
	template <class T> std::vector<int> z_algorithm(const std::vector<T>& s) {
		int n = int(s.size());
		if (n == 0) return {};
		std::vector<int> z(n);
		z[0] = 0;
		for (int i = 1, j = 0; i < n; i++) {
			int& k = z[i];
			k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);
			while (i + k < n && s[k] == s[i + k]) k++;
			if (j + z[j] < i + z[i]) j = i;
		}
		z[0] = n;
		return z;
	}
};


constexpr int B = 30;

int min_xor_pair(std::vector<int> A) {
	struct node {
		array<int, 2> to{-1, -1};	
	};
	vector<node> trie(1);
	auto Add = [&](int x) {
		int v = 0;
		for (int b = B - 1; b >= 0; --b) {
			int bit = (x >> b) % 2;
			if (trie[v].to[bit] == -1) {
				trie[v].to[bit] = int(trie.size());
				trie.emplace_back();
			}
			v = trie[v].to[bit];
		}
	};

	auto Pair = [&](int x) {
		int v = 0, res = 0;
		for (int b = B - 1; b >= 0; --b) {
			int bit = (x >> b) % 2;
			int to = trie[v].to[bit];
			if (to == -1) {
				res |= 1 << b;
				to = trie[v].to[bit ^ 1];
			}
			v = to;
		}
		return res;
	};
	
	int min_pair = 1 << B;
	int n = int(A.size());
	for (int i = 0; i < n; ++i) {
		if (i > 0) min_pair = min(min_pair, Pair(A[i]));
		Add(A[i]);
	}
	return min_pair;
}

vector<int> find_best_rs(std::vector<int> C, int J) {
	int N = int(C.size());
	vector<int> suf(N + 1);
	for (int i = N - 1; i >= 0; --i) {
		suf[i] = suf[i + 1] ^ C[i];
	}

	int start = min_xor_pair(suf);
	vector<array<int, 2>> sorted_sufs(N + 1);
	for (int i = 0; i <= N; ++i) {
		sorted_sufs[i] = {suf[i], i};
	}
	sort(sorted_sufs.begin(), sorted_sufs.end());
	
	vector<int> best_r(N, -1);
	if (start != 0) {
		for (int i = 0; i < N; ++i) {
			int p = suf[i] ^ start;
			int r_i = int(lower_bound(sorted_sufs.begin(), sorted_sufs.end(), array<int, 2>{p, i}) - sorted_sufs.begin());
			if (r_i <= N && sorted_sufs[r_i][0] == p) {
				best_r[i] = sorted_sufs[r_i][1];
			}
		}
	} else if (J > 0) { //longest is optimal
		int i_s = 0;
		while (i_s <= N) {
			int i_e = i_s + 1;
			while (i_e <= N && sorted_sufs[i_e][0] == sorted_sufs[i_s][0]) i_e++;
			for (int i = i_s; i < i_e - 1; ++i) {
				best_r[sorted_sufs[i][1]] = sorted_sufs[i_e - 1][1];
			}
			i_s = i_e;
		}

	} else if (J == -1 || count(C.begin(), C.end(), 0) == 0) { //shortest is optimal
		int i_s = 0;
		while (i_s <= N) {
			int i_e = i_s + 1;
			while (i_e <= N && sorted_sufs[i_e][0] == sorted_sufs[i_s][0]) {
				best_r[sorted_sufs[i_e - 1][1]] = sorted_sufs[i_e][1];
				i_e++;
			}
			i_s = i_e;
		}
	} else { //just the longest consecutive zeroes
		int longest_l = -1, longest_r = -1;
		for (int i = N - 1, r = N; i >= 0; --i) {
			if (C[i] != 0) r = i;
			else if (longest_r - longest_l < r - i){
				longest_l = i, longest_r = r;
			}
		}
		best_r[longest_l] = longest_r;
	}
	return best_r;	
}


constexpr int max_N = int(1e6);
int z_cache[max_N * 2 + 1]; // array that the Z array is calculated on
vector<int> custom_z(int n, int matching_length) {
	std::vector<int> z(n);
	z[0] = 0;
	int offset = max_N - matching_length;
	for (int i = 1, j = 0; i < n; i++) {
		int& k = z[i];
		k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);
		while (i + k < n && z_cache[offset + k] == z_cache[offset + i + k] && k < matching_length) k++;
		if (j + z[j] < i + z[i]) j = i;
	}
	z.erase(z.begin(), z.begin() + matching_length);
	return z;
}

std::array<int, 2> xort(std::vector<int> C, int J) {
	int N = int(C.size());
	vector<int> best_r = find_best_rs(C, J);
	vector<int> consec_zero(N);
	for (int i = N - 1, j = N; i >= 0; --i) {
		consec_zero[i] = j - i;
		if (C[i] != 0) {
			j = i;
		}
	}

	vector<int> suf(N + 1);
	for (int i = N - 1; i >= 0; --i) {
		suf[i] = suf[i + 1] ^ C[i];
	}

	// Can return true when equal, doesn't matter 
	auto Cmp = [&](int l0, int l1, int lcp) -> bool {
		int r0 = best_r[l0];
		int r1 = best_r[l1];
		int s0 = r0 - l0;
		int s1 = r1 - l1;
		bool invert_verdict = false;
		if (s0 > s1) {
			invert_verdict = true;
			swap(s0, s1);
			swap(l0, l1);
			swap(r0, r1);
		}

		int first_non_J = l1 + s0;
		if (first_non_J < N && (suf[first_non_J] ^ suf[r1]) == J) {
			first_non_J += consec_zero[first_non_J];
		}
		
		bool verdict;
		if (lcp < min(s0, s1) - 1) { //minus one shouldn't matter but anyways
			verdict = (suf[l0 + lcp + 1] ^ suf[r0]) < (suf[l1 + lcp + 1] ^ suf[r1]);
		} else if (first_non_J < r1) {
			verdict = J < (suf[first_non_J] ^ suf[r1]);
		} else {
			verdict = false;
		}

		return verdict ^ invert_verdict;
	};
	
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	vector<int> valid_ls;
	for (int i = 0; i < N; ++i) {
		if (best_r[i] != -1) {
			valid_ls.push_back(i);
		}
	}
	shuffle(valid_ls.begin(), valid_ls.end(), rng);

	for (int i = 0; i < N; ++i) {
		z_cache[max_N + i] = C[i];
	}

	int ans_l = -1; vector<int> z_array;

	for (auto l : valid_ls) {
		if (ans_l == -1 || Cmp(l, ans_l, z_array[l])) {
			int s = best_r[l] - l;
			for (int i = 0; i < s; ++i) {
				z_cache[max_N - s + i] = C[l + i];			
			}
			
			ans_l = l;
			z_array = custom_z(N + s, s);
		}
	}

	return {ans_l, best_r[ans_l]};
}

