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: HARD
Tags: Complete search

Sorting

Mathematics

Greedy algorithms
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
q = int(input())
for _ in range(q):
	(a, b, m) = map(int, input().split())
	mn = [a]
	mx = [a]
	sum_mn = a
	sum_mx = a
	ok = False
	for n in range(51):
		if mn[-1] <= b <= mx[-1]:
			ok = True
			break
		mn.append(sum_mn + 1)
		mx.append(sum_mx + m)
		sum_mn += mn[-1]
		sum_mx += mx[-1]
		if mn[-1] > b:
			break
	if not ok:
		print(-1)
		continue
	s = b - mn[-1]
	r = [0] * n
	for i in range(n):
		x = s // max(1, 2 ** (n - i - 2))
		if x > m - 1:
			x = m - 1
		r[i] = x + 1
		s -= x * max(1, 2 ** (n - i - 2))
	res = [a]
	s = a
	for i in range(n):
		res.append(s + r[i])
		s += res[-1]
	print(len(res), *res)


q = int(input())

def prepare_sequence(a, b, curr_two_pow, m):
	sequence = [a]
	curr_pow = 1
	diff = b - curr_two_pow * a
	while curr_two_pow > 1:
		m_candidate = 1
		diff -= m_candidate
		while diff > curr_two_pow // 2:
			m_candidate *= 2
			diff = diff - (m_candidate - m_candidate // 2)
		if diff < curr_two_pow // 2:
			m_candidate //= 2
			diff = diff + m_candidate
		curr_candidate = m_candidate // (curr_two_pow // 2)
		if curr_candidate > m:
			diff = diff + (curr_candidate - m) * (curr_two_pow // 2)
			curr_candidate = m
		sequence.append(sum(sequence) + curr_candidate)
		curr_pow *= 2
		curr_two_pow //= 2
	sequence.append(b)
	return sequence

def satisfies(a, b, m):
	if a == b:
		return [a]
	curr_two_pow = 1
	while curr_two_pow * a < b:
		diff = b - curr_two_pow * a
		if diff >= curr_two_pow and diff <= curr_two_pow * m:
			return prepare_sequence(a, b, curr_two_pow, m)
		curr_two_pow *= 2
	return None
for i in range(q):
	(a, b, m) = map(int, input().split())
	res = satisfies(a, b, m)
	if res:
		print('%s %s' % (len(res), ' '.join(map(str, res))))
	else:
		print(-1)


q = int(input())
for _ in range(q):
	(a, b, m) = [int(x) for x in input().split()]
	if a == b:
		print('1 ', a)
		continue
	found = 0
	for n in range(2, 51):
		lo = 2 ** (n - 2) * (a + 1)
		hi = 2 ** (n - 2) * (a + m)
		if lo <= b and b <= hi:
			b -= lo
			print(n, a, '', end='')
			acc = a
			for i in range(2, n + 1):
				p = 1 if i + 1 >= n else 2 ** (n - i - 1)
				left = 1
				right = m
				res = 1
				while left <= right:
					mid = (left + right) // 2
					if p * mid - p <= b:
						res = max(res, mid)
						left = mid + 1
					else:
						right = mid - 1
				b += p
				b -= p * res
				print(acc + res, '', end='')
				acc += acc + res
			print('')
			found = 1
			break
	if not found:
		print(-1)


def get_r_list(a, b, m):
	k = 2
	two_power_k = 1
	isMatch = False
	if a == b:
		return (1, [])
	while True:
		if b <= two_power_k * (a + 1):
			isMatch = True
			break
		if k == 50:
			break
		k += 1
		two_power_k *= 2
	isDone = False
	if isMatch and b < two_power_k * (a + 1):
		k -= 1
		two_power_k = int(two_power_k / 2)
	gap = b - two_power_k * (a + 1)
	two_power_k = int(two_power_k / 2)
	r_list = []
	if b == two_power_k * (a + 1) * 2:
		isDone = True
		for i in range(1, k - 1):
			r_list.append(0)
	while two_power_k != 0:
		if gap >= two_power_k:
			index_r = 0
			gap_divide = int(gap / two_power_k)
			if gap_divide > m - 1:
				index_r = m - 1
			else:
				index_r = gap_divide
			gap = gap - two_power_k * index_r
			r_list.append(index_r)
			two_power_k = int(two_power_k / 2)
		else:
			two_power_k = int(two_power_k / 2)
			r_list.append(0)
	if gap == 0:
		isDone = True
		r_list.append(0)
	elif gap <= m - 1:
		isDone = True
		r_list.append(gap)
	else:
		isDone = False
	if isDone:
		return (k, r_list)
	else:
		return (-1, r_list)

def cute_sequence(a, b, m):
	(k, r_list) = get_r_list(a, b, m)
	if k == -1:
		print(k)
		return
	if k == 1:
		print(1, end=' ')
		print(b)
		return
	sequence_list = []
	sequence_list.append(a)
	sequence_list.append(a + r_list[0] + 1)
	for i in range(2, k):
		next_a = 2 * sequence_list[i - 1] + r_list[i - 1] - r_list[i - 2]
		sequence_list.append(next_a)
	print(k, end=' ')
	for ele in sequence_list:
		print(ele, end=' ')
	print()
	return
N = int(input())
for _ in range(N):
	(a, b, m) = input().split()
	a = int(a)
	b = int(b)
	m = int(m)
	cute_sequence(a, b, m)


for _ in range(int(input())):
	(a, b, m) = map(int, input().split())
	if a == b:
		print(1, a)
		continue
	for k in range(2, 51):
		pw = 1 << k - 2
		mn = pw * (a + 1)
		mx = pw * (a + m)
		if mn <= b <= mx:
			r = [0] * (k + 1)
			add = b - mn
			r[1] = a
			for i in range(2, k):
				r[i] = min(m - 1, add // (1 << k - i - 1))
				add -= r[i] * (1 << k - i - 1)
				r[i] += 1
			r[k] = add + 1
			x = [0] * (k + 1)
			s = 0
			for i in range(1, k + 1):
				x[i] = s + r[i]
				s += x[i]
			print(k, *x[1:], sep=' ')
			break
	else:
		print(-1)


q = int(input())
po = [1, 1, 2]
l = 4
for i in range(55):
	po.append(l)
	l *= 2
while q > 0:
	q -= 1
	(a, b, m) = map(int, input().split())
	se = 0
	for ub in range(1, 51):
		s = sum(po[:ub - 1])
		if b < s + po[ub - 1] * a:
			print(-1)
			se = 2
			break
		if b <= s * m + po[ub - 1] * a:
			k = b - po[ub - 1] * a - po[ub - 1]
			arr = []
			for j in range(1, ub):
				i = k // po[ub - 1 - j]
				i = min(m - 1, i)
				k -= i * po[ub - 1 - j]
				arr.append(i + 1)
			print(ub, a, end=' ')
			s = a
			k = []
			for i in arr:
				k.append(s + i)
				s += s + i
			print(' '.join([str(i) for i in k]))
			se = 2
			break
	if se != 2:
		print(-1)


N = int(input())
for _ in range(N):
	(a, b, m) = list(map(int, input().split()))
	m -= 1
	if a == b:
		print('1 ' + str(a))
		continue
	c = a
	d = 1
	f = False
	r = []
	while b - (1 << d - 1) - c >= 0:
		if b - (1 << d - 1) - c <= m << d - 1:
			rem = b - (1 << d - 1) - c
			for i in range(d - 2, -1, -1):
				r.append(min(rem >> i, m))
				rem -= min(rem >> i, m) * (1 << i)
			r.append(rem)
			assert 0 <= rem <= m
			f = True
			break
		else:
			d += 1
			c *= 2
	if f:
		cs = a
		tr = [str(d + 1), str(a)]
		for i in range(d):
			tr.append(str(cs + r[i] + 1))
			cs = cs + cs + r[i] + 1
		print(' '.join(tr))
	else:
		print(-1)


from sys import stdin, stdout
n = int(stdin.readline())
for nn in range(n):
	(a, b, m) = map(int, stdin.readline().split())
	if a == b:
		stdout.write('{} {}\n'.format(1, a))
	else:
		for j in range(2, 51):
			if a + 1 << j - 2 <= b and b <= a + m << j - 2:
				B = b
				b -= a << j - 2
				stdout.write('{} {}'.format(j, a))
				s = a
				for i in range(j - 2):
					left = 1
					right = m
					while left < right:
						k = (left + right + 1) // 2
						if b - (k << j - 3 - i) >= 1 << j - 3 - i:
							left = k
						else:
							right = k - 1
					a = s + left
					stdout.write(' {}'.format(a))
					s += a
					b -= left << j - 3 - i
				stdout.write(' {}\n'.format(B))
				break
		else:
			stdout.write('-1\n')


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)


import sys
input = sys.stdin.readline
q = int(input())
Q = [list(map(int, input().split())) for i in range(q)]
for (a, b, m) in Q:
	MIN = [a]
	MAX = [a]
	SUMMIN = a
	SUMMAX = a
	flag = 1
	for k in range(51):
		if MIN[-1] <= b <= MAX[-1]:
			break
		MIN.append(SUMMIN + 1)
		MAX.append(SUMMAX + m)
		SUMMIN += MIN[-1]
		SUMMAX += MAX[-1]
		if MIN[-1] > 10 ** 14 or MIN[-1] > b:
			flag = 0
			break
	if flag == 0:
		print(-1)
		continue
	SA = b - MIN[-1]
	PLUS = [0] * k
	for j in range(k):
		x = SA // max(1, 2 ** (k - j - 2))
		if x > m - 1:
			x = m - 1
		PLUS[j] = x + 1
		SA -= x * max(1, 2 ** (k - j - 2))
	ANS = [a]
	SUM = a
	for j in range(k):
		ANS.append(SUM + PLUS[j])
		SUM += ANS[-1]
	print(len(ANS), *ANS)


q = int(input())
for i in range(q):
	(a, b, m) = list(map(int, input().split()))
	l = a + 1
	r = a + m
	c = 0
	poziom = 0
	if a == b:
		print(1, a, end='\n')
		continue
	while True:
		if l > b:
			print(-1)
			break
		if b <= r and b >= l:
			c = 1
			last = [l, r]
			break
		poziom += 1
		l *= 2
		r *= 2
	if c == 1:
		mat = [(a + 1) * 2 ** i for i in range(poziom + 1)]
		sumka = a
		for i in range(poziom + 1):
			if mat[-1] == b:
				break
			elif i == poziom:
				mat[-1] = b
				break
			else:
				pom = min(sumka + m - mat[i], (b - mat[-1]) // 2 ** (poziom - i - 1))
				mat[i] += pom
				for j in range(i + 1, poziom + 1):
					mat[j] += pom * 2 ** (j - i - 1)
				sumka += mat[i]
		print(len(mat) + 1, end=' ')
		print(a, end=' ')
		for i in range(len(mat)):
			if i < len(mat) - 1:
				print(mat[i], end=' ')
			else:
				print(mat[i], end='\n')


import math
import re
import sys
from collections import defaultdict
from heapq import heappush, heappop
from fractions import gcd

def read(type=int):
	return type(input())

def read_list(type=int, split=' ', F=None):
	if F:
		return map(lambda x: F(type(x)), raw_input().split(split))
	return map(type, input().split(split))

def read_list_of_list(N, type=int, split=' ', F=None):
	return [read_list(type, F=F) for _ in range(N)]

def solve():
	(a, b, m) = read_list()
	if a == b:
		return '1 %d' % a
	e = 0
	while a * 2 ** e + m * 2 ** e < b:
		e += 1
	if a * 2 ** e >= b:
		return -1
	z = b - a * 2 ** e - 2 ** e
	if z < 0:
		return -1
	X = [1] * (e + 1)
	i = 0
	while z:
		if e > 0:
			e -= 1
		k = min(z // 2 ** e, m - 1)
		X[i] += k
		i += 1
		z -= k * 2 ** e
	R = [a]
	i = 0
	while a < b:
		a = sum(R) + X[i]
		R += [a]
		i += 1
	return ' '.join(map(str, [len(R)] + R))
q = read()
for _ in range(q):
	print(solve())


t = int(input())

def r(i, m):
	return (1 << i, m * (1 << i))

def bis(i, e, m):
	if i == 0:
		return e
	mn = 1 << i - 1
	e -= mn
	mlt = 1 << i - 1
	(l, r) = (1, m)
	if r * mlt <= e:
		return r
	while r - l > 1:
		m = (r + l) // 2
		if m * mlt <= e:
			l = m
		else:
			r = m
	return l
for _ in range(t):
	(s, e, m) = list(map(int, input().split()))
	ee = e
	if e == s:
		print('1 {}'.format(s))
		continue
	for i in range(100):
		if s * (1 << i) + (1 << i) * m >= e:
			ii = i
			break
	if s * (1 << i) + (1 << i) > e:
		print(-1)
		continue
	print(i + 2, end=' ')
	e -= s * (1 << i)
	ans = [s]
	while i >= 0:
		x = bis(i, e, m)
		if i > 0:
			e -= x * (1 << i - 1)
		ans.append(x)
		i -= 1
	cur = s
	for j in range(ii + 1):
		print(cur, end=' ')
		cur = cur * 2 - ans[j] + ans[j + 1]
	print(cur)


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)


from itertools import count

def debug(*args, **kwargs):
	import sys

def solve(a, b, m):
	if a == b:
		return [a]
	debug(a=a, b=b, m=m)
	for k in count(2):
		lo = 2 ** (k - 2) * a + 2 ** (k - 2)
		hi = 2 ** (k - 2) * a + 2 ** (k - 2) * m
		debug(k=k, lo=lo, hi=hi)
		if lo > b:
			break
		if b <= hi:
			ans = [a] + [2 ** (i - 1) * a + 2 ** (i - 1) for i in range(1, k)]
			debug('got one', start=ans)
			if m == 1:
				return ans
			for i in range(1, k - 1):
				deficit = b - ans[-1]
				quot = min(deficit // 2 ** (k - 2 - i), m - 1)
				ans[i] += quot
				for j in range(i + 1, k):
					ans[j] += 2 ** (j - i - 1) * quot
			ans[-1] = b
			return ans
	return None

def check(a, b, m, ans):
	assert ans[-1] == b
	for i in range(1, len(ans)):
		assert 1 <= ans[i] - sum(ans[:i]) <= m

def test_solve(a, b, m):
	if a > b:
		(a, b) = (b, a)
	ans = solve(a, b, m)
	if ans is None:
		return
	check(a, b, m, ans)

def main():
	q = int(input())
	for _ in range(q):
		(a, b, m) = map(int, input().split())
		ans = solve(a, b, m)
		debug(a=a, b=b, m=m, ans=ans)
		if ans:
			check(a, b, m, ans)
			print(len(ans), *ans)
		else:
			print(-1)
main()


def solve():
	(a, b, m) = (int(x) for x in input().split())
	if a == b:
		print(1, a)
		return
	curr = a
	curr_const = 1
	steps_nr = 0
	while b - curr > curr_const * m:
		curr *= 2
		curr_const *= 2
		steps_nr += 1
	if b - curr < curr_const:
		print(-1)
		return
	left = b - curr - curr_const
	ans = [a]
	sum = a
	curr_const //= 2
	while curr_const > 0:
		curr_try = left // curr_const
		curr_try = min(m - 1, curr_try)
		left -= curr_try * curr_const
		ans.append(sum + curr_try + 1)
		sum += ans[-1]
		curr_const //= 2
	curr_const = 1
	curr_try = left // curr_const
	curr_try = min(m - 1, curr_try)
	left -= curr_try * curr_const
	ans.append(sum + curr_try + 1)
	sum += ans[-1]
	curr_const //= 2
	print(len(ans), *ans)
q = int(input())
for _ in range(q):
	solve()


def find_k(A, B, M):
	for k in range(2, 51):
		s = 2 ** (k - 2)
		if (A + 1) * s <= B and (A + M) * s >= B:
			return k
	return -1

def solve(A, B, M):
	if A == B:
		print('1', A)
		return
	k = find_k(A, B, M)
	if k == -1:
		print(-1)
		return
	print(k, end=' ')
	a = A
	print(A, end=' ')
	R = B - 2 ** (k - 2) * A
	for i in range(k - 3, -1, -1):
		s = 2 ** i
		r = min(R // s - 1, M)
		print(a + r, end=' ')
		a += a + r
		R -= r * s
	assert 0 < R <= M
	print(B)
Q = int(input())
for case in range(Q):
	(A, B, M) = [int(x) for x in input().split()]
	solve(A, B, M)


def solve(a, b, m):
	if a == b:
		return [a]
	for _len in range(2, 51):
		l = (a + 1) * 2 ** (_len - 2)
		r = (a + m) * 2 ** (_len - 2)
		if b < l or b > r:
			continue
		res = []
		res += [a]
		s = a
		for i in range(1, _len - 1):
			L = 0
			R = m + 1
			while R - L > 1:
				M = int((L + R) // 2)
				l = (s + s + M + 1) * 2 ** (_len - i - 2)
				r = (s + s + M + m) * 2 ** (_len - i - 2)
				if r < b:
					L = M
				else:
					R = M
			x = s + R
			res += [x]
			s += x
		res += [b]
		return res
tc = int(input())
for _ in range(tc):
	(a, b, m) = map(int, input().split())
	res = solve(a, b, m)
	if res:
		print(len(res), end=' ')
		for i in res:
			print(i, end=' ')
		print()
	else:
		print(-1)


q = int(input())
powers = [1]
for i in range(50):
	powers.append(powers[-1] * 2)
for _ in range(q):
	(a, b, m) = [int(x) for x in input().split()]
	if a == b:
		print(1, a)
	elif m == 1:
		good = False
		for r in range(50):
			if powers[r] * (a + 1) > b:
				break
			elif powers[r] * (a + 1) == b:
				good = True
				power = r
				break
		if good:
			print(power + 2, end=' ')
			print(a, end=' ')
			for j in range(r):
				print((a + 1) * powers[j], end=' ')
			print((a + 1) * powers[r])
		else:
			print(-1)
	else:
		terms = 0
		for r in range(50):
			if powers[r] * (a + 1) > b:
				break
			elif powers[r] * (a + m) >= b:
				terms = r + 2
				break
		if terms == 0:
			print(-1)
		else:
			components = terms - 1
			p = components - 1
			X = b - powers[p] * a
			C = [0]
			for q in range(components):
				if q != components - 1:
					C.append(min(X // powers[p - q - 1], m))
					X -= powers[p - q - 1] * C[-1]
					if q < components - 1 and X < powers[p - q - 1]:
						X += powers[p - q - 1]
						C[-1] -= 1
				else:
					C.append(X)
			T = [a, a + C[1]]
			for l in range(1, components):
				T.append(T[-1] * 2 + C[l + 1] - C[l])
			print(terms, end=' ')
			for e in T:
				if e != T[-1]:
					print(e, end=' ')
				else:
					print(e)


import math
n = int(input())

def solve(a, b, m):
	if 1 <= b - a <= m:
		return [2, a, b]
	if a == b:
		return [1, a]
	x = math.log2(b / (a + m))
	y = math.log2(b / (a + 1))
	if math.ceil(x) > math.floor(y):
		return [-1]
	mi = math.floor(y)
	w = mi
	k = b - 2 ** mi * (a + 1)
	r = [w + 2, a]
	s = a
	while True:
		inc = 1
		if k > 0:
			if w > 0:
				_inc = int(min(m - 1, k // 2 ** (w - 1)))
				k -= _inc * 2 ** (w - 1)
				inc += _inc
			else:
				inc += k
		r.append(s + inc)
		s += r[-1]
		if r[-1] == b:
			break
		w -= 1
		if w == -2:
			break
	return r
for _ in range(n):
	(a, b, m) = list(map(int, input().split()))
	r = solve(a, b, m)
	s = ' '.join(map(str, r))
	print(s)


for _ in range(int(input())):
	(a, b, m) = [int(i) for i in input().split()]
	if a == b:
		print('1 ' + str(a))
		continue
	l = a + 1
	r = a + m
	cnt = 1
	while r < b:
		l += l
		r += r
		cnt += 1
	if l > b:
		print(-1)
		continue
	ls = [1] * cnt
	p2 = [2 ** (cnt - 2 - i) for i in range(cnt - 1)] + [1]
	for i in range(cnt):
		tmp = min((b - l) // p2[i], m - 1)
		ls[i] += tmp
		l += tmp * p2[i]
	ans = [a]
	ps = a
	for i in ls:
		a = ps + i
		ps += a
		ans += [a]
	print(str(cnt + 1) + ' ' + ' '.join((str(i) for i in ans)))


q = int(input())
for _ in range(q):
	(a, b, m) = map(int, input().split())
	if a == b:
		print(1, a)
		continue
	a1 = a + 1
	am = a + m
	for i in range(49):
		if a1 <= b <= am:
			n = i + 2
			s = 0
			ans = [a, *[0] * (n - 1)]
			for j in range(1, n):
				s += ans[j - 1]
				ans[j] = s + 1
			diff = b - ans[-1]
			sr = 0
			ss = 0
			for j in range(1, n):
				p = int(max(1, 2 ** (n - 2 - j)))
				r = min(diff // p, m - 1)
				ss = sr + r
				sr += ss
				ans[j] += ss
				diff -= r * p
			print(n, ' '.join(map(str, ans)))
			break
		a1 *= 2
		am *= 2
	else:
		print(-1)


q = int(input().strip())
for i in range(q):
	(a, b, m) = map(int, input().strip().split())
	p = a + 1
	q = a + m
	c = 1
	pos = 0
	q = 0
	if b == a:
		print(1, a)
	else:
		while b / c > a + m:
			c = c << 1
			q += 1
		if b / c >= a + 1:
			pos = 1
		if pos:
			d = c * a
			l = [1 for i in range(q + 1)]
			ll = [ii - 1 for ii in range(q + 1)]
			ll[0] += 1
			s = b - d - c
			pp = q
			while s > 0:
				l[pp] += min(s // pow(2, ll[pp]), m - 1)
				s = s - (l[pp] - 1) * pow(2, ll[pp])
				pp -= 1
			ss = a
			po = a
			print(q + 2, end=' ')
			print(ss, end=' ')
			for i in range(q + 1):
				ss = po + l[q - i]
				print(ss, end=' ')
				po = po + ss
			print()
		else:
			print(-1)


from sys import stdin, stdout
for q in range(int(input())):
	(a, b, m) = map(int, input().split())
	if a == b:
		print(1, a)
		continue
	k = 2
	while k <= 50 and (not (1 << k - 2) * (a + 1) <= b <= (1 << k - 2) * (a + m)):
		k += 1
	if k > 50:
		print(-1)
		continue
	t = b - (1 << k - 2) * (a + 1)
	add = [1] * (k - 1)
	add[0] = a
	for i in range(1, k - 1):
		l = 1
		r = m
		while r - l > 1:
			x = l + r >> 1
			if t >= (1 << k - 2 - i) * (x - 1):
				l = x
			else:
				r = x - 1
		add[i] = r if t >= (1 << k - 2 - i) * (r - 1) else l
		t -= (1 << k - 2 - i) * (add[i] - 1)
	ans = [a] * (k - 1)
	for i in range(1, k - 1):
		ans[i] = ans[i - 1] * 2 - add[i - 1] + add[i]
	print(k, ' '.join((str(i) for i in ans)), b)


q = int(input())
for u in range(q):
	(a, b, m) = map(int, input().split())
	ranges = [(a, a)]
	bigsum = a
	smlsum = a
	while ranges[-1][1] < b:
		ranges.append((smlsum + 1, bigsum + m))
		smlsum = 2 * smlsum + 1
		bigsum = 2 * bigsum + m
	if b < ranges[-1][0]:
		print(-1)
	else:
		seq = [a]
		leng = len(ranges)
		power = 2 ** (leng - 3)
		curr = (a + 1) * 2 ** (leng - 2)
		sumi = a
		for i in range(leng - 2):
			seq.append(sumi + max(min((b - curr) // power + 1, m), 1))
			power //= 2
			sumi += seq[-1]
			curr = (sumi + 1) * 2 ** (leng - i - 3)
		if b != seq[-1]:
			seq.append(b)
		out = [leng] + seq
		out = [str(guy) for guy in out]
		print(' '.join(out))