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.math.*;

// **** D. Cute Sequences ****

public class D {
	static char [] in = new char [1000000];
	public static void main (String [] arg) throws Throwable {
		int q = nextInt();
		StringBuilder ans = new StringBuilder(q*50*3);
		for (int ii = 0; ii<q; ++ii) {
			long a = nextLong();
			long b = nextLong();
			long m = nextLong();
			if (a == b) {
				ans = ans.append("1 " + a);
			} else {
				boolean solfound = false;
				for (int len = 2; len<=50; ++len) {
					long [] seq = solve(len, a, b, m);
					if (seq != null) {
						if (seq[0] == -1) break;
						ans=ans.append(seq.length);
						for (int i = 0; i<seq.length; ++i) {
							ans = ans.append(' ');
							ans = ans.append(seq[i]);
						}
						solfound = true;
						break;
					}
				}
				if (!solfound) ans=ans.append("-1");
			}
			ans = ans.append("\n");
		}
		System.out.print(ans);
	}
	public static long[] solve(int len, long a, long b, long m) {
		long pow = (1L<<len)>>2;
		b -= pow * a;
		long [] tmp_badans = new long [1];
		tmp_badans[0] = -1;
		//System.err.println("Trying length " + len + " with pow " + pow + " b is now " + b);
		if (b < 0) return tmp_badans;
		
		
		long [] ans = new long [len];
		long [] r = new long [len-1];
		ans[0] = a;
		long pow2 = pow;
		for (int i = 0; i<r.length; ++i) {
			if (pow2 != 1) pow2 = pow2>>1;
			b -= pow2;
			if ( b < 0) return tmp_badans;
		}
	
		for (int i = 0; i < r.length; ++i) {
			if (pow != 1) pow = pow >> 1;
			long fac = b/pow;
			if (fac > m-1) fac = m-1;
			b -= fac * pow;
			r[i] = fac + 1;
		}
		if (b != 0) return null;
		
		for (int i = 1; i<ans.length; ++i) {
			ans[i] = r[i-1];
			for (int j = 0; j<i; ++j) ans[i] += ans[j];
		}
		return ans;
	}

	
	
	
	
	
	
	
	
	
	
	
	
	
	/************** HELPER CLASSES ***************/
    static class HS extends HashSet<Integer>{public HS(){super();}public HS(int a){super(a);}};
	static class AL extends ArrayList<Integer>{public AL(){super();}public AL(int a){super (a);}};
	static class Pair implements Comparable<Pair>{int x,y,L; public Pair(int xx, int yy, int LL){x=xx;y=yy;L=LL;} public int compareTo(Pair p) {return this.L-L;}}	
	
	/************** FAST IO CODE FOLLOWS *****************/
	public static long nextLong() throws Throwable {
		long i = System.in.read();boolean neg = false;while (i < 33) i = System.in.read();if (i == 45) {neg=true;i=48;}i = i - 48;
		int j = System.in.read();while (j > 32) {i*=10;i+=j-48;j = System.in.read();}return (neg) ? -i : i;
	}
	public static int nextInt() throws Throwable {return (int)nextLong();}
	public static String next() throws Throwable {
		int i = 0; while (i < 33 && i != -1) i = System.in.read(); int cptr = 0; while (i >= 33) { in[cptr++] = (char)i; i = System.in.read();}
		return new String(in, 0,cptr);
	}
	/**** LIBRARIES ****/
	public static long gcdL(long a, long b) {while (b != 0) {long tmp = b;b = (a % b);a = tmp;}return a;}
	public static int gcd(int a, int b) {while (b != 0) {int tmp = b;b = (a % b);a = tmp;}return a;}
	public static int[] sieve(int LIM) {
		int i,count = 0;
		boolean [] b = new boolean [LIM];
		for (i = 2;i<LIM; ++i) if (!b[i]) {count++; for (int j = i<<1; j<LIM; j+=i) b[j] = true;}
		int [] primes = new int[count];
		for (i = 2,count=0;i<LIM;++i) if (!b[i]) primes[count++] = i;
		return primes;
	}
	public static int[] numPrimeFactors(int LIM) {
		int i,count = 0;
		int [] b = new int [LIM];
		for (i = 2;i<LIM; ++i) if (b[i] == 0) {count++; for (int j = i; j<LIM; j+=i) b[j]++;}
		return b;
	}
}

/* Full Problem Text:
  
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 < i < 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 < 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.

 */