011 - K番目の排他的論理和

時間制限 3 秒 / メモリ制限 256 MB / 得点 12 / x 0 /


TLE
3sec
MLE
256MB
得点
12

$0$ または $1$ からなる2つの数 $x$、$y$ に対する排他的論理和とは、$x$ と $y$ が同じであるとき $0$、異なるとき$1$ となる演算である。この演算を$\oplus$で表現する。定義から、$0 \oplus 0 = 0$, $0 \oplus 1 = 1$, $1 \oplus 0 = 1$, $1 \oplus 1 = 0$ である。

2つの非負整数 $X$、$Y$ に対するビットごとの排他的論理和とは、$X$ と $Y$ を2進数で表現したとき、各桁について排他的論理和をとりそれを数とする演算のことである。この演算も$\oplus$で表現する。たとえば、10進数で $3 \oplus 5$ は、2進数で $011 \oplus 101$ なので、ビットごとの排他的論理和をとると2進数で $110$ となり、10進数では $6$ になる。

非負整数である要素 $z_1, z_2, ..., z_M$からなる要素数 $M$ の数列 $Z$ に対する、ビットごとの排他的論理和を以下のように定義する。

  • $v_0 = 0, v_i = v_{i-1} \oplus z_i$ ($1 \leq i \leq M$) とする。
  • 数列 $Z$ に対するビットごとの排他的論理和を $v_M$と定める。

あなたは $N$ 個の非負整数からなる数列 $A$ と、たくさんの紙、ひとつの空箱を持っている。あなたは、$1 \leq L \leq R \leq N$ を満たす全ての整数の組($L, R$)について、以下の操作を1度ずつ行った。

  1. $A$ の $L$ 番目から $R$ 番目の要素からなる数列に対し、ビットごとの排他的論理和を求める。その数を$B$ とする。
  2. まだ箱に入れていない紙を1枚選び、その紙に $B$ を書き、箱に入れる。

紙は十分にあるので、操作の途中で足りなくなることはないものとする。あなたは、正の整数 $K$ を選び、箱の中の紙に書かれた数を降順に並べたときの $K$ 番目の数を求めることにした。

数列が与えられたとき、すべての操作の終了後、箱の中の紙に書かれた数を降順に並べたときの $K$ 番目の数を計算するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$ $K$
$a_1$ $a_2$ ... $a_N$

1行目に、数列の要素数$N$ ($1 \leq N \leq 10^5$)、選んだ数$K$ ($1 \leq K \leq N(N+1)/2$)が整数で与えられる。2行目に、数列の要素$a_i$ ($0 \leq a_i \leq 10^6$)が与えられる。

入出力例

入力例1

3 3
1 2 3

出力例1

2

操作の後、箱の中の紙に書かれた数を降順に並べると以下のようになる。

  • $3,3,2,1,1,0$

3番目の数は2であるため、2を出力する。

入力例2

7 1
1 0 1 0 1 0 1

出力例2

1

入力例 3

5 10
1 2 4 8 16

出力例3

7