Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem E: 三队-杭州-求第k个数

Problem E: 三队-杭州-求第k个数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 1
[Submit][Status][Web Board]

Description

现有[A,B]闭区间内的无限个整数,构造数字如下:

选取X个整数满足G[1]<=G[2]<=...<=G[X]。则数字S为这X个数字的乘积。若当前有构造完成的数字Sa,Sb,则当数字Sa<Sb满足如下规则之一:

1.Sa使用的数字个数小于Sb使用的数字个数。

2.存在整数j使得对所有的i<j有Sa_G[i] 等于 Sb_G[i],Sa_G[j]<Sb_G[j]。

问处在[L,R]闭区间内的第K个数字是多少。如果没有,输出-1;如果有,输出数字并从小到大输出构造的数字G[1]~G[X]分别是多少。

Input

第一行包含一个整数T,代表测试组数。

每组测试数据为一行的五个整数,A,B,L,R,K。

限制:2<=A<=B<=10^6,1<=L<=R<=10^9,1<=K<=10^6

Output

对于每组数据,你需要输出’Case #x: y’,x代表从一开始的测试数据组号,y就是答案。

若y不为-1,则还需要另起一行,从小到大输出构造使用的每个整数,按空格分开。

Sample Input

4
2 2 1 4 1
2 5 1 4 4
73 23642 12 20903
29401 2 50 1 1000000000 815180

Sample Output

Case #1: 2
2
Case #2: 4
2 2
Case #3: -1
Case #4: 59200
4 4 5 20 37

HINT



第二个样例我们有4种整数2,3,4,5。



在[L,R]区间内的第一个数是2,由(2)构成;



第二个数是3,由(3)构成;



第三个数是4,由(4)构成;



第四个数是5,由(5)构成;



第五个数是4,由(2 2)构成。


[Submit][Status][Web Board]