아기염소 줄 세우기

아기염소들은 저녁 식사를 위해 줄을 선다. 각 아기염소는 0과 1로만 이루어진 이진수 번호판을 달고 있으며, 번호의 길이는 31비트를 넘지 않는다.

아기염소들은 번호를 일반적인 이진수의 오름차순인 0, 1, 10, 11, 100, ... 순서로 서지 않는다. 대신 다음 우선순위를 따른다.

• 번호판에 들어 있는 1의 개수가 적을수록 앞에 선다.
• 1의 개수가 같으면, 번호를 이진수로 보았을 때 값이 작은 번호가 앞에 선다.

예를 들어 1000은 1이 1개이고 110은 1이 2개이므로 1000이 더 앞선다. 100부터 1111까지의 번호를 이 규칙으로 나열하면 다음과 같다.

100, 1000, 101, 110, 1001, 1010, 1100, 111, 1011, 1101, 1110, 1111

번호가 정확히 0인 경우를 제외하면, 번호는 0으로 시작하지 않는다.

번호 A부터 B까지의 아기염소가 있을 때, 위 우선순위로 정렬한 뒤 X번째에 서는 아기염소의 번호를 구하시오.

첫째 줄에 A가 주어진다.

둘째 줄에 B가 주어진다.

셋째 줄에 구하려는 아기염소의 위치 X가 주어진다. 맨 앞의 아기염소가 1번째이다.

해당 위치에 있는 아기염소의 번호를 출력한다.