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 \le i \le 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 \le r_i \le 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 \le q \le 10^3$) — the number of queries.

Each of the following $q$ lines contains three integers $a$, $b$, and $m$ ($1 \le a, b, m \le 10^{14}$, $a \leq 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 \le k \leq 50$), followed by $k$ integers $x_1, x_2, \dots, x_k$ ($1 \le x_i \le 10^{14}$). These integers must satisfy $x_1 = a$, $x_k = b$, and that the sequence $x_1, x_2, \dots, 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, \dots$, which does not contain $9$.

Difficulty: interview

Starter code:

Solutions:
from math import ceil, floor
Q = int(input())
for _ in range(Q):
    a, b, m = map(int, input().split())
    if b - a == 0:
        print(1, a)
        continue
    if b - a <= m:
        print(2, a, b)
        continue
    x = max(0, ceil(b/(a+m)) - 1)
    y = max(0, floor(b/(a+1)))
    if x.bit_length() < y.bit_length():
        h = y.bit_length()
        t = b - a*2**(h-1)
        M = [t//(2**(h-1))]*h
        t %= 2**(h-1)
        for i in range(h-1):
            j = h - 2 - i
            if 2**j & t:
                M[i] += 1
        sumi = a
        ans = [a] + [0]*h
        assert all(m > 0 for m in M), ''
        for i in range(1, h+1):
            ans[i] = sumi + M[i-1]
            sumi += ans[i]
        if len(ans) > 50:
            print(-1)
        else:
            print(len(ans), *ans)
    else:
        print(-1)

# https://codeforces.com/contest/1166/problem/D
def creat_r(X, k, m, p):
    q = X // p[k]
    r = X %  p[k]
    
    R = []
    for _ in range(k+1):
        R.append(q)
        
    s = bin(r)[2:]
    for i in range(1, len(s)+1):
        if s[-i] == '1':
            R[-(i+1)] += 1
       
    return R

i = 1
p = [1]
for _ in range(50):
    i*=2
    p.append(i)
    
T   = int(input())
ans = []
for _ in range(T):
    a, b, m = map(int, input().split())
    if a == b:
        print(1, a)
        continue
    
    flg = False
    for i in range(50):
        if p[i] * a  >= b: break
    
        k = i
        X = b - (p[i] * a)
    
        if X >= p[k] and X <= p[k]*m:
            flg = True
            R   = creat_r(X, k, m, p)
            sR  = 0 
            A   = [a]
        
            for _ in range(k+1):
                A.append(p[_]*a+sR+R[_])
                sR += sR + R[_] 
            
            print(len(A), end=' ')
            for x in A:
                print(x, end=' ')
            print()
            break
        
        
    if flg == False:
        print(-1)