재귀 무늬 (Szlaczek)

코르넬리아는 자연수로 이루어진 “재귀 무늬(szlaczek)”를 그리며 논다. 무늬는 임의의 자연수 수열에서 시작한다. 예를 들면 다음과 같다.

1 2 1 1 1

그런 다음 지금까지 쓴 무늬 전체를 뒤집은 복사본을 그 뒤에 이어 붙인다. 이 과정을 한 번 거칠 때마다 무늬의 길이는 두 배가 된다. 위 예시에서 한 단계를 진행하면 다음과 같이 된다(뒤에 붙은 부분은 원래 무늬를 뒤집은 것이다).

1 2 1 1 1 1 1 1 2 1

여기서 한 단계를 더 진행하면 다음과 같다.

1 2 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 1 2 1

이렇게 무늬는 끝없이 늘려 나갈 수 있다.

코르넬리아가 처음에 적은 수열이 주어질 때, 완성된 무늬의 지정된 위치에 어떤 수가 오는지 구하여라.

첫째 줄에 테스트 케이스의 개수 $Z$ ($1 \le Z \le 10$)가 주어진다. 이어서 각 테스트 케이스가 차례로 주어진다.

각 테스트 케이스의 첫째 줄에는 두 자연수 $N$과 $M$ ($1 \le N \le 10^6$, $0 \le M \le 10^9$)이 주어진다. $N$은 처음 수열의 길이, $M$은 무늬에서의 위치를 뜻한다.

둘째 줄에는 처음 수열을 이루는 $N$개의 자연수 $c_1, c_2, \dots, c_N$ ($1 \le c_i \le 10^6$)이 공백으로 구분되어 주어진다.

각 테스트 케이스마다 무늬의 $M$번째 위치에 오는 수를 한 줄에 하나씩 출력한다. 위치는 $0$번부터 센다.