Problem Statement

You are given a sequence $a_i$ of length $N$ and $Q$ queries. Each query is as follows.

• Given $x$, find the number of elements of ${a_i}$ that are less than $x$.

Note that the sizes of the sequence and the number of queries are given in the input, but their contents are both generated by a random number generator.

For the output, let $r_i$ be the result of the $i(i = 1,2,...,Q)$-th query, and
print the xor of all $r_i \times (i-1)$.

That is, let $s_i = r_i \times (i-1)$, and print $s_1 \oplus s_2 \oplus ... \oplus s_Q$.

The query results are combined in order to reduce the time spent on output (the intended solution does obtain the answers to all queries).

A naive solution to this problem (code that outputs the correct answer but takes a very long time to run) is provided for three languages, C++, Java, and D. Refer to it for how the input is generated. For these three languages, there are intended solutions that fit within the time limit. (C++: 1461ms, Java: 3627ms (what?), D: 2721ms)

Source code

Input

N Q Seed

$N = 2 \times 10^5$
$Q = 5 \times 10^7$
$1 \leq Seed \leq 10^9$
$0 \leq a_i, x \leq 2^{31} - 1$

Output

Print a newline at the end.

Sample