Codeforces Round 941 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

constructive algorithms

greedy

number theory

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Missing Subsequence Sum

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given two integers $$$n$$$ and $$$k$$$. Find a sequence $$$a$$$ of non-negative integers of size at most $$$25$$$ such that the following conditions hold.

- There is no subsequence of $$$a$$$ with a sum of $$$k$$$.
- For all $$$1 \le v \le n$$$ where $$$v \ne k$$$, there is a subsequence of $$$a$$$ with a sum of $$$v$$$.

A sequence $$$b$$$ is a subsequence of $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) elements, without changing the order of the remaining elements. For example, $$$[5, 2, 3]$$$ is a subsequence of $$$[1, 5, 7, 8, 2, 4, 3]$$$.

It can be shown that under the given constraints, a solution always exists.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.

Each test case consists of a single line containing two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le k \le n$$$) — the parameters described above.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^7$$$.

Output

The first line of output for each test case should contain a single integer $$$m$$$ ($$$1 \le m \le 25$$$) — the size of your chosen sequence.

The second line of output for each test case should contain $$$m$$$ integers $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of your chosen sequence.

If there are multiple solutions, print any.

Example

Input

52 26 18 89 310 7

Output

1 1 5 2 3 4 5 6 7 1 1 1 1 1 1 1 4 7 1 4 1 4 1 2 8 3

Note

In the first example, we just need a subsequence that adds up to $$$1$$$, but not one that adds up to $$$2$$$. So the array $$$a=[1]$$$ suffices.

In the second example, all elements are greater than $$$k=1$$$, so no subsequence adds up to $$$1$$$. Every other integer between $$$1$$$ and $$$n$$$ is present in the array, so there is a subsequence of size $$$1$$$ adding up to each of those numbers.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2024 12:10:06 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|