import std.conv, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; } int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); } int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); } /********/ ulong seed; int next() { seed = seed ^ (seed << 13); seed = seed ^ (seed >> 7); seed = seed ^ (seed << 17); return cast(int)(seed >> 33); } /********/ enum L = 10^^5; int N, Q; int[] A; void main() { try { for (; ; ) { N = readInt(); Q = readInt(); seed = readLong(); foreach (i; 0 .. 10000) { next(); } A = new int[N]; foreach (i; 0 .. N) { A[i] = next(); } debug { writeln("A = ", A[0 .. min(10, $)]); } A.sort; auto xs = new int[L]; auto js = new int[L]; auto work = new int[L]; auto buckets = new int[0x10001]; auto ans = new int[L]; long ansSum; for (int qL = 0; qL < Q; qL += L) { const qR = min(qL + L, Q); foreach (q; qL .. qR) { xs[q - qL] = next(); } const len = qR - qL; debug { if (qL / L < 10) { writeln("queries ", xs[0 .. min(len, 10)]); } } foreach (j; 0 .. len) { js[j] = j; } // radix sort buckets[] = 0; foreach (j; 0 .. len) ++buckets[(xs[js[j]] & 0xffff) + 1]; foreach (h; 0 .. 0x10000) buckets[h + 1] += buckets[h]; foreach (j; 0 .. len) work[buckets[xs[js[j]] & 0xffff]++] = js[j]; buckets[] = 0; foreach (j; 0 .. len) ++buckets[(xs[work[j]] >> 16) + 1]; foreach (h; 0 .. 0x10000) buckets[h + 1] += buckets[h]; foreach (j; 0 .. len) js[buckets[xs[work[j]] >> 16]++] = work[j]; debug { if (qL / L < 10) { writeln("js = ", js[0 .. min(len, 10)]); } } for (int i = 0, j = 0; j < len; ++j) { for (; i < N && A[i] < xs[js[j]]; ++i) {} ans[js[j]] = i; } foreach (q; qL .. qR) { ansSum ^= cast(long)(ans[q - qL]) * q; } } writeln(ansSum); } } catch (EOFException e) { } }