나이트의 경로

<그림> 무한 격자에서의 나이트의 경로

격자판은 오른쪽과 위쪽으로 무한히 뻗어 있다. 이 격자에서 왼쪽에서 x번째, 아래에서 y번째 칸에는 수 $\frac{(x+y-1)(x+y-2)}{2}+y$가 쓰여 있다. 이 방법으로 각 칸을 하나의 양의 정수에 일대일로 대응시킬 수 있다.

나이트는 체스의 기물 중 하나로, 격자판 위를 움직인다. 나이트는 두 칸 전진한 뒤, 전진한 방향에서 오른쪽 또는 왼쪽으로 한 칸 이동한다. 전진 방향은 위, 아래, 오른쪽, 왼쪽 중 무엇이든 될 수 있다. 다만 격자판 밖으로 나가서는 안 된다. 나이트가 격자판 밖으로 나가지 않는다고 할 때, 8칸 중 하나로 이동할 수 있다. 그러나 가장 왼쪽 아래에 있는 1번 칸에서는 8번 칸이나 9번 칸 중 하나로만 이동할 수 있다.

나이트는 1번 칸에서 출발하여 k번 이동하려고 한다. 이동하는 과정에서 이동할 수 있는 칸이 여럿 있을 수 있다. 그러면 나이트는 한 번도 방문하지 않은 칸으로 이동한다. 방문하지 않은 칸이 여러 개이면 그중 쓰인 수가 가장 작은 칸으로 이동하고, 방문하지 않은 칸이 없으면 더 이동하지 않고 멈춘다.

나이트가 이동하는 횟수인 음이 아닌 정수 k가 첫째 줄에 주어진다. k는 0일 수도 있다.

나이트가 k번 이동하는 동안 멈추지 않고, 그동안 방문한 칸에 쓰인 수가 모두 $2^{31}$ 미만인 k만 입력으로 주어진다.

나이트가 k번 이동한 후에 위치한 칸의 번호를 출력한다.