Bit thứ k trong tín hiệu phản chiếu

Bối cảnh và bài toán

Một thiết bị tạo tín hiệu nhị phân theo quy tắc: S1 = "0"; với n>1, Sn = S(n-1) + "1" + invert(reverse(S(n-1))). Chuỗi có thể dài tới hơn 10^18 ký tự nên không thể dựng trực tiếp. Thiết bị chỉ cần biết ký tự thứ k (đánh số từ 1).

Yêu cầu

Xác định bit thứ k của Sn mà không dựng toàn bộ chuỗi.

Input

• Một dòng chứa n k.

Output

In 0 hoặc 1.

Ràng buộc

• 1 <= n <= 60
• 1 <= k <= 2^n - 1

Chấm điểm

Ví dụ 1

Input

3 5

Output

0

Giải thích. S3 = 0111001, ký tự thứ 5 là 0.

Ví dụ 2

Input

4 8

Output

1

Giải thích. Vị trí giữa của S4 là ký tự 1 được chèn ở bước xây dựng.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.