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 CPP):

Solution:
#include <bits/stdc++.h>
template <class T>
void UPRT(const T _) {
  if (_ >= 10) UPRT(_ / 10);
  putchar(_ % 10 + 48);
}
template <class T>
void PRT(const T _) {
  if (_ < 0) {
    putchar(45), UPRT<unsigned long long>(-(unsigned long long)_);
    return;
  }
  if (_ >= 10) PRT(_ / 10);
  putchar(_ % 10 + 48);
}
using std::bitset;
using std::cin;
using std::cout;
using std::deque;
using std::map;
using std::pair;
using std::priority_queue;
using std::set;
using std::sort;
using std::string;
using std::unordered_map;
using std::unordered_set;
using std::vector;
constexpr int MN(1e3 + 7);
long long ddd[MN];
int main() {
  int q;
  {
    char _c = getchar(), _v = 1;
    for (q = 0; _c < 48 || _c > 57; _c = getchar())
      if (_c == 45) _v = -1;
    for (; _c >= 48 && _c <= 57;
         q = (q << 1) + (q << 3) + _c - 48, _c = getchar())
      ;
    if (_v == -1) q = -q;
  }
  while (q--) {
    long long a, b, m;
    {
      char _c = getchar(), _v = 1;
      for (a = 0; _c < 48 || _c > 57; _c = getchar())
        if (_c == 45) _v = -1;
      for (; _c >= 48 && _c <= 57;
           a = (a << 1) + (a << 3) + _c - 48, _c = getchar())
        ;
      if (_v == -1) a = -a;
    }
    {
      char _c = getchar(), _v = 1;
      for (b = 0; _c < 48 || _c > 57; _c = getchar())
        if (_c == 45) _v = -1;
      for (; _c >= 48 && _c <= 57;
           b = (b << 1) + (b << 3) + _c - 48, _c = getchar())
        ;
      if (_v == -1) b = -b;
    }
    {
      char _c = getchar(), _v = 1;
      for (m = 0; _c < 48 || _c > 57; _c = getchar())
        if (_c == 45) _v = -1;
      for (; _c >= 48 && _c <= 57;
           m = (m << 1) + (m << 3) + _c - 48, _c = getchar())
        ;
      if (_v == -1) m = -m;
    }
    if (a + m >= b) {
      if (a == b)
        printf("1 %lld\n", a);
      else
        printf("2 %lld %lld\n", a, b);
    } else {
      long long x = a;
      bool found = false;
      for (int len = 2; len <= 50; ++len) {
        long long p2 = 1LL << (len - 2);
        long long lb = p2 * (x + 1), ub = p2 * (x + m);
        if (lb > b) break;
        if (ub < b) continue;
        if (lb == b) {
          found = true;
          long long sum = x, now, dd = 1;
          PRT(len), putchar(32);
          PRT(x), putchar(32);
          for (int i = 1; i < len; ++i) {
            PRT(now = sum + dd), putchar(32);
            sum += now;
          }
          break;
        }
        if (ub == b) {
          found = true;
          long long sum = x, now, dd = m;
          PRT(len), putchar(32);
          PRT(x), putchar(32);
          for (int i = 1; i < len; ++i) {
            PRT(now = sum + dd), putchar(32);
            sum += now;
          }
          break;
        }
        found = true;
        long long dis = b - lb;
        long long dis_2 = dis / (m - 1);
        long long res = dis % (m - 1);
        for (int ii = 0; ii < 58; ++ii) ddd[ii] = 1;
        while (dis_2) {
          long long lbit = dis_2 & -dis_2;
          dis_2 -= lbit;
          int pos = 63 - __builtin_clzll(lbit);
          pos = len - 2 - pos;
          ddd[pos] += m - 1;
        }
        ddd[len - 1] += res;
        long long sum = x, now;
        PRT(len), putchar(32);
        PRT(x), putchar(32);
        for (int i = 1; i < len; ++i) {
          PRT(now = sum + ddd[i]), putchar(32);
          sum += now;
        }
        break;
      }
      if (not found)
        puts("-1");
      else
        puts("");
    }
  }
  return 0;
}