問題文

長さ $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\le Seed\le {10}^9$
$0\le a_i,x\le 2^{31}-1$

出力

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

サンプル