Cute Sequences

题意翻译

给你一个正数m，如果正数序列（x1，x2，...，xn）满足以下条件的就是m-cute序列：对于任意的i（2<=i<=n）,xi=xi-1+xi-2+...x1+ri，ri是满足1<=ri<=m. 给你q（1<=q<=10^3）组询问，每组包含三个正数a，b和m(1≤a,b,m≤10^14, a≤b)。对于每组询问你必须确定是否存在一个m-cute序列，开始是a，结束是b，如果存在输出这个序列，如果不存在输出-1. 如果存在，输出时，先输出序列的长度k（1<=k<=50）,然后依次输出m-cute序列：x1,x2,...xk,其中满足x1=a,xk=b。注意序列长度不超过50，如果有多组数据，输出任意一组就可以。

题目描述

Given a positive integer $ m $ , we say that a sequence $ x_1, x_2, \dots, x_n $ of positive integers is $ m $ -cute if for every index $ i $ such that $ 2 \le i \le n $ it holds that $ x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i $ for some positive integer $ r_i $ satisfying $ 1 \le r_i \le m $ . You will be given $ q $ queries consisting of three positive integers $ a $ , $ b $ and $ m $ . For each query you must determine whether or not there exists an $ m $ -cute sequence whose first term is $ a $ and whose last term is $ b $ . If such a sequence exists, you must additionally find an example of it.

输入输出格式

输入格式

The first line contains an integer number $ q $ ( $ 1 \le q \le 10^3 $ ) — the number of queries. Each of the following $ q $ lines contains three integers $ a $ , $ b $ , and $ m $ ( $ 1 \le a, b, m \le 10^{14} $ , $ a \leq b $ ), describing a single query.

输出格式

For each query, if no $ m $ -cute sequence whose first term is $ a $ and whose last term is $ b $ exists, print $ -1 $ . Otherwise print an integer $ k $ ( $ 1 \le k \leq 50 $ ), followed by $ k $ integers $ x_1, x_2, \dots, x_k $ ( $ 1 \le x_i \le 10^{14} $ ). These integers must satisfy $ x_1 = a $ , $ x_k = b $ , and that the sequence $ x_1, x_2, \dots, x_k $ is $ m $ -cute. It can be shown that under the problem constraints, for each query either no $ m $ -cute sequence exists, or there exists one with at most $ 50 $ terms. If there are multiple possible sequences, you may print any of them.

输入输出样例

输入样例 #1

2
5 26 2
3 9 1

输出样例 #1

4 5 6 13 26
-1

说明

Consider the sample. In the first query, the sequence $ 5, 6, 13, 26 $ is valid since $ 6 = 5 + \bf{\color{blue} 1} $ , $ 13 = 6 + 5 + {\bf\color{blue} 2} $ and $ 26 = 13 + 6 + 5 + {\bf\color{blue} 2} $ have the bold values all between $ 1 $ and $ 2 $ , so the sequence is $ 2 $ -cute. Other valid sequences, such as $ 5, 7, 13, 26 $ are also accepted. In the second query, the only possible $ 1 $ -cute sequence starting at $ 3 $ is $ 3, 4, 8, 16, \dots $ , which does not contain $ 9 $ .