#4729. 舞!舞!舞!

内存限制:256 MiB 时间限制:20 Sec

题目描述

"如何是好呢,我?"我重复刚才的问话。 
"刚才我已说了,尽力而为就是,争取把你连接妥当。"羊男说,"但只这样还不够,你自己也必须全力以赴,不能光是静坐空想,那样你永远走投无路,明白吗?" 
"明白。"我说,"那么我到底如何是好呢?" 
"跳舞,"羊男说,"只要音乐在响,就尽管跳下去。明白我的话?跳舞!不停地跳舞!不要考虑为什么跳,不要考
虑意义不意义,意义那玩艺儿本来就没有的。"
现在,你要做的是在数论中舞!舞!舞!--已知f(N)求第K小的N。
这里的f可以是莫比乌斯函数、欧拉函数和除数个数函数σ0。

输入格式

三个正整数type,f(N),K,分别表示函数类型、函数值和K。
莫比乌斯函数为1,欧拉函数为2,除数个数函数为3。

输出格式

一个整数,表示满足条件的第K小的N。
I.|μ(N)|<=1,K<=10^8
II.Φ(N)<=10^10,K<=1000 满足答案不超过10^12
III. d(N)<=10^7,K<=50 满足答案不超过10^100
共五组数据。所有输入保证合法。

样例

样例输入


			
注意以下每行都是独立的数据。
1 1 1
2 1 1
3 1 1
1 1 70926127
2 219104256 14
3 123 4

样例输出


			
1
1
1
233333333
233333333
133040906960896

数据范围与提示