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.*;
public class Main {
    public static void merge(long[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    long[] L = new long[n1];
    long[] R = new long[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[m + 1 + j];
    }
    int i = 0, j = 0;
    int k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
    public static void sort(long[] arr, int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(arr, l, m);
            sort(arr , m + 1, r);
            merge(arr, l, m, r);
        }
    }
    public static int res(long curr, long sum, long m, long steps, long target) {
        long minSum = sum;
        long maxSum = sum;
        long min = curr;
        long max = curr;
        for (int i = 0; i < steps; i++) {
            min = minSum + 1;
            minSum += min;
            max = maxSum + m;
            maxSum += max;
            if (min >= 1_000_000_000_000_000L || max >= 1_000_000_000_000_000L) break;
        }
        if (min <= target && target <= max) {
            return 0;
        }
        if (max < target) {
            return -1;
        }
        return 1;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            long a = in.nextLong();
            long b = in.nextLong();
            long m = in.nextLong();
            boolean flag = false;
            int k;
            for (k = 1; k <= 50; k++) {
                if (res(a, a, m, k - 1, b) == 0) {
                    flag = true;
                    System.out.print(k-- + " ");
                    break;
                }
            }
            if (!flag) {
                System.out.println(-1);
            } else {
                System.out.print(a + " ");
                long sum = a;
                while (k-- > 0) {
                    long l = 1;
                    long r = m;
                    while (r - l > 10) {
                        long mid = (l + r) / 2;
                        long result = res(sum + mid, sum + sum + mid, m, k, b);
                        if (result == 0) {
                            l = mid;
                            r = mid;
                            break;
                        }
                        if (result == -1) {
                            l = mid;
                        } else {
                            r = mid;
                        }
                    }
                    for (long x = l; x <= r; x++) {
                        if (res(sum + x, sum + sum + x, m, k, b) == 0) {
                            a = sum + x;
                            sum += a;
                            System.out.print(a + " ");
                            break;
                        }
                    }
                }
                System.out.println();
            }
        }
    }
}