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:
//package sept;

import java.io.*;
import java.util.*;



public class TimePass implements Runnable {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    //boolean debug=false;
    boolean debug=true;
    static long mod=998244353;
    static long mod2=1000000007;
    
    /*
     * 1
1960018268 83034021522462 1
     */
    void solve() throws IOException
    {
    	int q=ni();
    	while(q-->0)
    	{
    		long a=nl(),b=nl(),m=nl();
    		if(a==b)
    		{
    			out.println(1+" "+a);
    			continue;
    		}
    		int sz=52;
    		for(int i=1;i<=50;i++)
    		{
    			if(b<=(((long)1<<(i-1))*((double)a+m)))
    			{
    				sz=i;
    				break;
    			}
    		}
    		int szr=0;
    		for(int r=50;r>=1;r--)
    		{
    			if(b>=(((long)1<<(r-1))*((double)a+1)))
    			{
    				szr=r;
    				break;
    			}
    		}
    		//out.println(sz+" "+szr);
    		if(sz+1>50 || sz>szr)
    		{
    			out.println(-1);
    			continue;
    		}
    		long[] arr=new long[(int) sz];
    		Arrays.fill(arr, 1);
    		long req=(b-((long)1<<(sz-1))*(a+1));
    		for(int i=0;i<sz;i++)
    		{
    			long tmp=((long)1<<(sz-2-i));
    			if((sz-1)==i)tmp=1;
    			if(req>=(m-1)*tmp)
    			{
    				arr[i]+=m-1;
    				req-=(m-1)*tmp;
    			}
    			else
    			{
    				long cur=req/tmp;
    				arr[i]+=cur;
    				req-=cur*tmp;
    				
    				//break;
    			}
    			if(req<=0)break;
    			//if(i>0)arr[i]+=arr[i-1];
    		}
    		//out.println(Arrays.toString(arr));
    		long prevsum=0,currsum=0;
    		//long sum=a;
    		out.print((sz+1)+" "+a+" ");
    		for(int i=0;i<sz;i++)
    		{
    			//sum+=arr[i];
    			currsum=arr[i]+prevsum;
    			prevsum+=currsum;
    			out.print((((long)1<<(i))*a+currsum)+" ");
    		}
    		out.println();
    	}
	}
    
	static Pair[][] packU(int n,int[] from,Pair[] to)
	{
		Pair[][] g=new Pair[n][];
		int[] p=new int[n];
		for(int f:from)
		{
			p[f]++;
		}
		int m=from.length;
		for(int i=0;i<n;i++)
		{
			g[i]=new Pair[p[i]];
		}
		for(int i=0;i<m;i++)
		{
			g[from[i]][--p[from[i]]]=to[i];
		}
		return g;
	}
    
	static int[][] packD(int n,int[] from,int[] to)
	{
		int[][] g=new int[n][];
		int[] p=new int[n];
		for(int f:from)
		{
			p[f]++;
		}
		int m=from.length;
		for(int i=0;i<n;i++)
		{
			g[i]=new int[p[i]];
		}
		for(int i=0;i<m;i++)
		{
			g[from[i]][--p[from[i]]]=to[i];
		}
		return g;
	}
	    
    static class Pair
    {
    	long a,b,c;
    	//int a,b,c;
        public Pair(long a,long b)
        {
            this.a=a;
            this.b=b;
            //this.ind=ind;
        }
    }
    
    static long lcm(int a,int b)
    {
        long val=a;
        val*=b;
        return (val/gcd(a,b));
    }
    
    static long gcd(long a,long b)
    {
        if(a==0)return b;
        return gcd(b%a,a);
    }
    
    static int pow(int a, int b, int p)
    {
        long ans = 1, base = a;
        while (b!=0)
        {
            if ((b & 1)!=0)
            {
                ans *= base;
                ans%= p;
            }
            base *= base;
            base%= p;
            b >>= 1;
        }
        return (int)ans;
    }

    static int inv(int x, int p)
    {
        return pow(x, p - 2, p);
    }
    
    public static long[] radixSort(long[] f){ return radixSort(f, f.length); }
	public static long[] radixSort(long[] f, int n)
	{
		long[] to = new long[n];
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>16&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>16&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>32&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>32&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>48&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>48&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		return f;
	}
    
    public void run()
    {
        if(debug)oj=true;
        is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        try {
			solve();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
        out.flush();
        tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception {new Thread(null,new TimePass(),"Main",1<<26).start();}
    
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
    private void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }
}

/*
int N=ni(),M=ni(),P=ni();
Pair[] songs=new Pair[N];
//songs Pair:a-albumType,b-price,c-greatness
int[] albPrice=new int[M];
ArrayList<Pair>[] albSongs=new ArrayList[M];
//albSongs Pair:a-price,b=index,c-greatness
for(int i=0;i<M;i++)
{
	albSongs[i]=new ArrayList<>();
}
for(int i=0;i<N;i++)
{
	songs[i]=new Pair(ni(),ni());
	songs[i].c=ni();
	Pair pr=new Pair(songs[i].b,i);
	pr.c=songs[i].c;
	albSongs[songs[i].a-1].add(pr);
}
int ind=0;
for(int i=0;i<M;i++)
{
	albPrice[i]=ni();
	for(Pair j:albSongs[i])
	{
		j.b=ind++;
	}
}
long[][] dp=new long[N][P+1];
for(int i=albSongs[0].get(0).a;i<=P;i++)
{
	dp[0][i]=albSongs[0].get(0).c;
}
//out.println(Arrays.toString(dp[0]));
long sumPrices=0,sumGreatness=0;
for(int i=1;i<=P;i++)
{
	
	//out.println("price:"+i);
	for(int j=1;j<albSongs[0].size();j++)
	{
		if(i==1)
		{
			sumPrices+=albSongs[0].get(j).a;
			sumGreatness+=albSongs[0].get(j).c;
		}
		int index=albSongs[0].get(j).b;
		
		if(i>=albSongs[0].get(j).a)
		{
			dp[index][i]=Math.max(dp[index-1][i-albSongs[0].get(j).a]+albSongs[0].get(j).c, dp[index][i]);
			if(index>0)dp[index][i]=Math.max(dp[index][i], dp[index-1][i]);
		}
		else if(index>0)dp[index][i]=Math.max(dp[index][i], dp[index-1][i]);
		
		//out.println(dp[index][i]);
	}
	
	//out.println();
}
int lastInd=albSongs[0].get(albSongs[0].size()-1).b;
for(int i=1;i<=P;i++)
{
	if(i>=sumPrices)
	{
		dp[lastInd][i]=Math.max(sumGreatness, dp[lastInd][i]);
	}
	if(i>=albPrice[0])
	{
		dp[lastInd][i]=Math.max(sumGreatness, dp[lastInd][i]);
	}
}
for(int i=1;i<=P;i++)
{
	for(int j=1;j<M;j++)
	{
		sumPrices=0;sumGreatness=0;
		for(int k=0;k<albSongs[j].size();k++)
		{
			sumPrices+=albSongs[j].get(k).a;
			sumGreatness+=albSongs[j].get(k).c;
			if(i>=albSongs[j].get(k).a)
			{
				dp[j][i]=Math.max(dp[j][i-albSongs[j].get(k).a]+albSongs[j].get(k).c, dp[j][i]);
				dp[j][i]=Math.max(dp[j][i], dp[j-1][i]);
				dp[j][i]=Math.max(dp[j][i], dp[j][i-1]);
			}
			else
			{
				dp[j][i]=Math.max(dp[j][i], dp[j][i-1]);
				dp[j][i]=Math.max(dp[j][i], dp[j-1][i]);
			}
		}
		
		if(i>=sumPrices)
		{
			dp[j][i]=Math.max(dp[j][(int) (i-sumPrices)]+sumGreatness, dp[j][i]);
		}
		if(i>=albPrice[j])
		{
			dp[j][i]=Math.max(dp[j][(int)(i-albPrice[j])]+sumGreatness, dp[j][i]);
		}
	}
}
out.println(dp[M-1][P]);

*/