해시 함수

해시 함수 $h\_n$은 $2n$비트로 이루어진 수 $A$를 다음과 같이 암호화한다.

$A = (a\_{2n-1}a\_{2n-2} \cdots a\_1a\_0)\_2$라고 하자. $a\_i$는 $A$의 $i$번째 비트이다.

$2n$비트로 이루어진 수 $B = (b\_{2n-1}b\_{2n-2} \cdots b\_1b\_0)\_2$는 다음과 같이 구한다.

$b\_i = a\_i \oplus a\_{2i+1},\text{ for } 0 \le i < n,$ $b\_i = a\_i \oplus a\_{4n-2i-2},\text{ for } n \le i < 2n,$

여기서 $\oplus$는 비트별 배타적 논리합(XOR)이다. 달리 말해 $B = A \oplus (a\_0a\_2 \cdots a\_{2n-4}a\_{2n-2}a\_{2n-1}a\_{2n-3} \cdots a\_3a\_1)\_2$이다.

다음으로 $2n$비트로 이루어진 수 $C = B \oplus \text{RSH}(B)$를 구한다. 여기서 $\text{RSH}(B)$는 $B$를 1비트 순환 오른쪽 시프트한 값이다. 달리 말해 $C = B \oplus (b\_0b\_{2n-1}b\_{2n-2} \cdots b\_2b\_1)\_2$이다.

마지막으로 해시 값은 $h\_n(A) = 239A + 153C \bmod (2^{2n-1}-1)$이다.

예를 들어 $n=4$이고 $A = 00001101\_2 = 13$이라고 하자. 그러면 $B = 00001101\_2 \oplus 11000010\_2 = 11001111\_2 = 207$이다. 이어서 $C = 11001111\_2 \oplus 11100111\_2 = 00101000\_2 = 40$이다. 마지막으로 $h\_4(A) = 239 \times 13 + 153 \times 40 \bmod (2^7-1) = 9227 \bmod 127 = 83$이다.

이 해시 함수의 역함수를 구하는 것이 목표이다. 주어진 $n$과 $H$에 대해 $h\_n(A)=H$를 만족하는 $A$를 찾아라.

두 정수 $n$과 $H$가 주어진다 ($2 \le n \le 16$, $0 \le H < 2^{2n-1}-1$).

$h\_n(A)=H$를 만족하는 $A$ ($0 \le A < 2^{2n}$)가 존재함이 보장된다.

$h\_n(A)=H$를 만족하는 정수 $A$ ($0 \le A < 2^{2n}$) 하나를 출력한다.

조건을 만족하는 $A$가 여러 개라면 그중 아무것이나 출력해도 된다.