F. Где диск после k ходов

Пирамидку из $n$ дисков перекладывают со стержня 1 на стержень 3 наименьшим числом ходов — тем самым способом, что в классной задаче.

Определите, на каком стержне окажется диск номер $d$ после первых $k$ перекладываний.

Строить последовательность ходов нельзя: их до $2^{60} - 1$. Зато можно рассуждать рекурсивно: первые $2^{n-1} - 1$ ходов переносят верхние $n-1$ дисков со стержня 1 на стержень 2, затем один ход самого большого диска, затем ещё столько же ходов переносят $n-1$ дисков со стержня 2 на стержень 3.

Одна строка содержит числа $n$, $d$ и $k$ ($1 \le n \le 60$, $1 \le d \le n$, $0 \le k \le 2^n - 1$).

Одно число — номер стержня, на котором окажется диск $d$.