📖 문제 개요

문제

음이 아닌 정수 $N$개로 이루어진 배열 $A=[A_{1}, \dots, A_{N}]$이 주어진다. 배열 $A$에 다음 연산을 $K$번 진행한다.

• 배열에 남아 있는 원소 중에서 인접한 두 원소를 선택해, 해당 원소들에 대해 bitwise $\textrm{OR}$ 연산을 적용하고 그 결괏값으로 두 원소를 대체한다. 다시 말해 현재 배열의 길이를 $L$이라 하면, 정수 $i(1 \leq i < L)$를 선택해 $[A_1, A_2, \dots, A_i, A_{i+1}, \dots, A_{L}]$을 $[A_1, A_2, \dots, A_i | A_{i+1}, \dots, A_{L}]$로 변경한다. 이 연산을 진행한 뒤 배열의 길이는 $1$만큼 줄어든다.

$K$번의 연산을 진행한 이후 배열에 남은 $N-K$개의 원소를 모두 bitwise $\textrm{AND}$ 연산한 값의 최댓값을 구해보자.

bitwise $\textrm{AND}$와 bitwise $\textrm{OR}$ 연산에 대한 설명은 노트를 참고하라.

입력

첫 번째 줄에 $N$과 $K$가 공백으로 구분되어 주어진다. $(2 \leq N \leq 500\, 000;1 \leq K \leq N-1)$

두 번째 줄에 배열 $A$의 원소 $A_1, A_2, \dots, A_{N}$이 공백으로 구분되어 주어진다. $\left( 0 \leq A_{i} \leq 10^{9}\right)$

출력

총 $K$번의 연산을 진행한 후 배열에 남은 $N-K$개의 원소를 모두 bitwise $\textrm{AND}$ 연산한 값의 최댓값을 출력한다.

예제 입력 1

5 3
1 4 2 5 1

예제 출력 1

5

위 예제의 최댓값을 구하기 위한 총 $3$번의 연산 순서의 예시는 다음과 같다.

• $[1,4,2,5,1]$ $\Rightarrow$ $[1,\color{red}{4|2},5,1]$ $=[1,\color{red}{6},5,1]$
• $[1,6,5,1]$ $\Rightarrow$ $[\color{red}{1|6},5,1]$ $=[\color{red}{7},5,1]$
• $[7,5,1]$ $\Rightarrow$ $[7,\color{red}{5|1}]$ $=[7,\color{red}{5}]$

노트

bitwise 연산자들은 비트 단위로 연산을 시행한다.

• bitwise $\textrm{AND}$ 연산($\&$)은 두 수의 각 비트마다 다음과 같은 연산을 진행한다.

  • 같은 자릿수의 비트를 비교해 두 비트 다 $1$일 때만 $1$, 나머지의 경우는 $0$이다.
  • 다음은 예시이다.

  $$ \ \begin{array}{rcl} 0101_2 & = & 5 \\ \& \ 0011_2 & = & 3 \\ \hline 0001_2 & = & 1 \end{array} $$