第n小回文数

(palindromic.cpp)

大家对回文数都很熟悉了，例如：0、55、121、12344321等都是回文数。 回文数还有以下一些规律：

（1）所有一位数中是回文数的有1+9个，分别是0和1，2，...9 （2）所有二位数中是回文数的有9个，分别是11，22，33，...99

（3）所有三位数中是回文数的有90个，分别是101，111，121，...999

（4）所有四位数中是回文数的有90个，分别是1001，1111，1221，...9999

（5）所有五位数中是回文数的有900个

（6）所有六位数中是回文数的有900个

……

请试着求第N小的回文数。

输入格式(palindromic.in)： 输入一行，一个正整数 N。1≤N≤1018(50%的数 1≤N≤10000)

输出格式(palindromic.out)： 输出一行，第N小的回文数。

样例输入1： 46

样例输出1： 363

样例输入2： 1

样例输出2： 0

样例输入3： 1000000000000000000

样例输出3： 90000000000000000000000000000000009

求c++解