Problem: Given a positive integer m, we say that a sequence x_1, x_2, ..., x_n of positive integers is m-cute if for every index i such that 2 ≤ i ≤ n it holds that x_i = x_{i - 1} + x_{i - 2} + ... + x_1 + r_i for some positive integer r_i satisfying 1 ≤ r_i ≤ 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.

Input

The first line contains an integer number q (1 ≤ q ≤ 10^3) — the number of queries.

Each of the following q lines contains three integers a, b, and m (1 ≤ a, b, m ≤ 10^{14}, a ≤ b), describing a single query.

Output

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 ≤ k ≤ 50), followed by k integers x_1, x_2, ..., x_k (1 ≤ x_i ≤ 10^{14}). These integers must satisfy x_1 = a, x_k = b, and that the sequence x_1, x_2, ..., 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.

Example

Input


2
5 26 2
3 9 1


Output


4 5 6 13 26
-1

Note

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, ..., which does not contain 9.

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
public class D1166 
{
	static long r[];
	static long f[];
	public static void fill(int i , long d , long m)
	{
		r = new long [i];
		f = new long [i];
		for(int j=1;j<i;j++)
		{
			int p=i-j-2;
			f[j]=(long)Math.pow(2, p);
		}
		f[i-1]=1;
		for(int j =1; j<i ;j++)
		{
			r[j]++;
			d-= r[j]*f[j];
		}
		if(d==0)return;
		for(int j =1 ;j<i && d>0;j++)
		{
			r[j]+=Math.min(m-1, d/f[j]);
			d-=Math.min(m-1, d/f[j])*f[j];
		}
		
	}
	public static long x(long i ,long a)
	{
		if(i==1)return a;
		return (long)Math.pow(2, i-2) * a;
	}
	public static boolean isValid(long m , long i , long d)
	{
		if(i>50) return false;
		if(i==1)
		{
			if(d==0)return true;
			return false;
		}
		long min = (long)Math.pow(2, i-2);
		long max =min*m;
		//System.out.printf("Max %d Min %d i %d d %d%n",max,min,i,d);
		if(d >= min && d<=max) return true;
		return false;
	}
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		int q = Integer.parseInt(br.readLine());
		while(q-->0)
		{
			StringTokenizer st = new StringTokenizer (br.readLine());
			long a =Long.parseLong(st.nextToken());
			long b =Long.parseLong(st.nextToken());
			long m =Long.parseLong(st.nextToken());
			int i = 1;
			int answer = -1;
			long d =b-a;
			long x = x(i,a);
			while(d>=0)
			{
				if(isValid(m,i,d)) 
				{	
					answer = i;
					break;
				}
				i++;
				x=x(i,a);
				d=b-x;
			}
			if(answer == -1) System.out.println(-1);
			else
			{
				fill(answer , d ,m);
				long []xx = new long[answer];
				xx[0]=a;
				
				for(int k =1 ;k<answer ;k++)
				{
					for(int j =0 ;j<k ;j++)
						xx[k] += xx[j];
					xx[k]+=r[k];
				}
				System.out.print(answer +" ");
				for(int j=0;j<answer ;j++)
				{
					System.out.print(xx[j]+" ");
				}
			}
			System.out.println();
		}
	}

}