問題文

長さ $N$ の数列 $a_i$ に $Q$ 個のクエリが与えられます。それぞれのクエリは以下のようなクエリです。

• $x$ が与えられるので、${a_i}$ の要素のうち $x$ より小さいものの個数を求めてください

なお、数列、クエリの個数は入力で与えられますが、その内容は共に乱数生成器により生成されます。

また、出力は $i(i = 1,2,...,Q)$ 個目のクエリの結果を $r_i$ として、
$r_i \times (i-1)$ をすべてxorしたものを出力してください。

つまり、$s_i = r_i \times (i-1)$ として、$s_1 \oplus s_2 \oplus ... \oplus s_Q$ を出力して下さい。

なお、クエリの結果をまとめているのは、出力にかかる時間を減らすためです(想定解では、すべてのクエリに対する答えを得ています)

C++、Java、D、3つの言語について、この問題の愚直解(非常に長い時間実行する必要があるが、正しい答えを出力するコード)を載せるので、入力の生成方法はこれを参考にしてください。なお、この3つの言語については時間制限に間に合う想定解があります。(C++: 1461ms, Java: 3627ms(は？), D:2721ms)

ソースコード

入力

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$

出力

最後に改行してください。

サンプル