1201 - Ｋ番目の排他的論理和

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

２つの非負整数 $X$、$Y$ に対するビットごとの排他的論理和とは、$X$ と $Y$ を２進数で表現したとき、各桁について排他的論理和をとりそれを数とする演算のことである。この演算も$\oplus$で表現する。たとえば、１０進数で $3 \oplus 5$ は、２進数で $011 \oplus 101$ なので、ビットごとの排他的論理和をとると２進数で $110$ となり、１０進数では $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. $A$ の $L$ 番目から $R$ 番目の要素からなる数列に対し、ビットごとの排他的論理和を求める。その数を$B$ とする。
2. まだ箱に入れていない紙を１枚選び、その紙に $B$ を書き、箱に入れる。

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

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

入力

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

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

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

入出力例

入力例１

3 3
1 2 3

出力例１

2

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

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

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

入力例２

7 1
1 0 1 0 1 0 1

出力例２

1

入力例 3

5 10
1 2 4 8 16

出力例３

7