Trust the smaller call

Why it matters

Generated grammars and recursively encoded sequences can represent enormous outputs while a query asks for one position. Expanding all earlier data wastes memory and can make a single lookup impossible; row 30 here already contains more than 500 million symbols. The requested kth symbol must be found without constructing any complete row.

Row 1 is 0. Each 0 becomes 01 and each 1 becomes 10 to form the next row. Return the kth symbol (1-based) in row n. Do not build the whole row.

Input

n = 4, k = 5

Output

1

For n = 4 and k = 5, brute construction writes 1 + 2 + 4 + 8 symbols to read one of them. Follow position 5's single parent in each earlier row instead, then copy or flip while returning.

For n = 4 and k = 5, position 5 came from position (5 + 1) // 2 = 3 in row 3. That position came from 2 in row 2, then from 1 in row 1, whose value is the base symbol 0.

Unwind the chain using each child's position. k = 2 is even, so row 2 flips 0 to 1. k = 3 is odd, so row 3 copies 1; k = 5 is odd, so row 4 also copies 1. Only one position from each of the four rows is examined.