Recursive Pattern (Szlaczek)

Kornelia likes to draw “recursive patterns” (szlaczki) made of natural numbers. A pattern starts from an arbitrary sequence of natural numbers, for example:

1 2 1 1 1

She then appends, right after the pattern written so far, a copy of that whole pattern written backwards. Each such step doubles the length of the pattern. For the example above, after one step the pattern becomes (the appended part is the original pattern reversed):

1 2 1 1 1 1 1 1 2 1

After one more step it becomes:

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

The pattern can be extended forever in this way.

Given the sequence Kornelia started from, determine which number ends up at a given position of the pattern.

The first line contains the number of test cases $Z$ ($1 \le Z \le 10$). The test cases follow.

The first line of each test case contains two natural numbers $N$ and $M$ ($1 \le N \le 10^6$, $0 \le M \le 10^9$): the length of the starting sequence and the position in the resulting pattern.

The second line contains the $N$ natural numbers $c_1, c_2, \dots, c_N$ ($1 \le c_i \le 10^6$) of the starting sequence, separated by spaces.

For each test case, print on its own line the number located at position $M$ of the pattern. Positions are numbered starting from $0$.