공국

레스트비차 법(고대 슬라브어 '레스트비차'는 사다리를 뜻한다)은 키예프 루스에서 대공 자리를 잇는 관습이다.

위대한 나라 엔에는 현명한 통치자 엠이 있었다. 엠에게는 아들이 여러 명 있었다. 아들 하나하나가 훌륭한 통치자로 자라도록 엠은 아들마다 대공국 하나씩을 맡기기로 했다. 그런데 공국이 모두 같지는 않았다. 어떤 곳은 기름진 흑토 지대였고, 어떤 곳은 어두운 숲, 어떤 곳은 거친 초원이었다. 크기도 저마다 달랐다. 엠은 모든 공국에 서열 순으로 번호를 매겼다. 가장 중요한 공국을 1번, 그다음을 2번이라 부르는 식이었다. 엔 나라에는 공국이 셀 수 없이 많았고, 공국마다 고유한 번호가 있었다. 엠은 장남에게 1번 공국을, 둘째 아들에게 2번 공국을 주었다.

그런데 엠에게 손자들이 태어났다. 현명한 통치자는 다시 고민에 빠졌다. 손자들도 훌륭한 통치자가 되어야 했으므로 그들에게도 공국을 나눠 주어야 했다. 엠은 손자들에게 서열 순으로 주지 않고 다른 방식을 택했다. 먼저 아들들 가운데 가장 좋은 공국을 아들들의 연장자 순으로 나눠 준다. 그다음 남은 공국을 장남의 아들들에게 연장자 순으로 준다. 이어서 둘째 아들의 아들들에게, 같은 방식으로 계속 준다. 엠은 이 체계라면 증손자와 그 밖의 모든 남자 후손에게도 공국을 줄 수 있고, 모든 공국이 서열에 맞게 배분된다는 점을 마음에 들어 했다. 엠에게 아들이 한 명 더 태어나면, 모든 손자, 증손자, 그 밖의 남자 후손은 번호가 1 큰 공국을 다스리게 된다. 새로 태어난 아들은 둘째로 어린 아들보다 번호가 1 큰 공국을 다스리게 된다. 손자가 아들보다 더 중요한 공국을 다스리는 일은 없다. 아들들 사이의 서열은 연장자 순으로 정해지기 때문이다.

그런데 엠의 아들이 죽었고 대공국에는 통치자가 없게 되었다. 엠은 생각하다가, 후손이 죽으면 빈 공국은 다음 공국의 통치자가 다스리도록 하기로 했다. 그러면 이후의 남자 후손은 모두 번호가 1 작은 공국을 다스리게 되고, 모든 공국이 서열대로 올바르게 유지된다.

지금 엔 나라에서는 언제나 다음과 같은 군주의 순서가 있다. 먼저 통치자 엠, 그다음이 엠의 아들들을 연장자 순으로, 그다음이 장남의 아들들을 연장자 순으로, 그다음이 둘째 아들의 아들들을 연장자 순으로, 이런 식으로 가장 어린 아들까지 이어진다.

따라서 더 늦은 세대의 군주는 더 이른 세대의 어떤 군주보다도 뒤에 온다. 설령 앞선 군주가 나이가 많더라도 그렇다. 예를 들어 어떤 증손자든 어떤 손자보다 뒤에 온다.

엔 나라의 기록자는 모든 사건과 모든 죽음과 출생을 연대순으로 꼼꼼히 기록했다. 여러분은 이 값진 연대기를 얻었다. 이 연대기를 처리하여, 주어진 시점에 k번째 공국을 누가 다스리는지 알아내는 프로그램을 작성하라.