특별한 큰 분수

이 문제는 $x\_0$와 $N$의 제한을 제외하고 특별한 작은 분수와 같은 문제이다.

NLCS에는 분수가 많다.

분수에서 나오는 물의 높이는 특정한 규칙에 따라 변화하는데, 어떤 정수 시각 $t$에서의 분수의 높이가 정수 $x\_t$일 때, $x\_{t+1}$는 $x\_t$가 짝수라면 $\lfloor \frac{x\_t}{2} \rfloor \oplus 6$, $x\_t$가 홀수라면 $(2 \cdot x\_t) \oplus 6$과 같다.

$0$초에서의 분수의 높이가 주어졌을 때, $N$초에서의 분수의 높이를 구하는 프로그램을 작성하시오.

첫 번째 줄에 $0$초에서의 분수의 높이 $x\_0$와 $N$이 주어진다. $x\_0$와 $N$은 모두 정수이다.

첫 번째 줄에 $N$초에서의 분수의 높이를 출력한다.

• $0 \le x\_0, N \le 10^{18}$

• $\lfloor x \rfloor$는 $x$보다 작거나 같은 가장 큰 정수를 의미한다.
• $\oplus$는 비트 XOR 연산을 수행하는 연산자이다. 비트 XOR 연산자에 대한 자세한 정보는 위키백과 (영어)에서 읽을 수 있다. 대부분의 프로그래밍 언어에서 비트 XOR 연산은 ^로 구현되어 있다.