Tìm số theo chỉ mục.

Bối cảnh

Cho một số thập phân \(m\), chuyển nó thành một chuỗi nhị phân và áp dụng \(n\) lần lặp, trong mỗi lần lặp \(0\) trở thành \(01\) và \(1\) trở thành \(10\). Tìm ký tự chỉ mục thứ \(i\) (chỉ mục đánh số từ \(0\)) trong chuỗi sau lần lặp thứ \(n\). Ví dụ: \(m = 5, i = 5, n = 3\).

Yêu cầu

Ban đầu, chuỗi là \(101\) (tương đương số nhị phân \(5\)). Sau lần lặp đầu tiên: \(100110\). Sau lần lặp thứ \(2\): \(100101101001\). Sau lần lặp thứ \(3\): \(100101100110100110010110\). Ký tự ở chỉ số \(5\) là \(1\) nên \(1\) là đáp án.

Input

Dòng đầu tiên nhập vào số nguyên ba số nguyên dương \(m\), \(i\) và \(n\) \((1 \leq m,i,n \leq 50)\).

Output

In ra đáp án của bài toán.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

5 5 3

Output

1

Giải thích ví dụ

Ví dụ

Ví dụ 2

Input

5 5 3

Output

1

Giải thích ví dụ

Giải thích: Chuỗi nhị phân của 5 là "101", sau 3 lần lặp biến đổi, chuỗi trở thành "100101100110100110010110" và ký tự ở chỉ số 5 là "1".

Thông tin học tập

• Buổi: B14
• Concepts: recursion, divide-and-trace indexing, sequence transformations
• Giới hạn kiến thức: B01-B14
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 30