18137번 - 나이트의 경로

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

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

여기서 나이트(체스의 기물 중 하나)는 격자판을 이동하려고 한다. 나이트는 두 칸 전진 후, 전진한 방향에서 오른쪽 혹은 왼쪽 중 한 방향으로 한 칸을 이동한다. 전진하는 방향은 위쪽, 아래쪽, 오른쪽 혹은 왼쪽 중 아무 방향이어도 상관없다. 하지만 격자판을 나가서는 안 된다. 즉, 나이트가 격자판 바깥으로 나가는 경우가 없다고 할 때 8칸 중 하나로 이동할 수 있다. 하지만 가장 왼쪽 아래에 있는 칸인 1번 칸에서는 8번 칸이나 9번 칸 중 하나로밖에 이동할 수 없다.

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

나이트가 k번 이동한 후에 위치한 칸의 번호를 찾는 프로그램을 작성하여라.

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

나이트가 k번 이동하는 동안 멈추지 않으며, 그동안 방문한 칸에는 모두 2³¹ 미만의 정수가 쓰여 있는 k만 입력으로 주어짐이 보장된다.

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