题目描述

给定两个整数 $a$ 与 $b$，将 $a$ 与 $b$ 之间所有的整数表示成二进制并进行排序。比较次序时，规定二进制表示中 $1$ 出现次数比较少的数字排在前面，若一样多，数字本身比较小的排在前面。

给定一个 $k$，请输出排在第 $k$ 名的数字的二进制表示。

输入格式

• 第一行：两个整数 $a$ 与 $b$
• 第二行：单个整数 $k$，$1\leq k<b-a$

输出格式

单个整数：表示所求数字的二进制表示

4 15
5

1001

数据范围

• 对 $30\%$ 的数据，$b\leq 1000$
• 对 $100\%$ 的数据，$0\leq a\leq b\leq 10^{18}$