408521: GYM103181 B Convoluted Fraction

Memory Limit:1024 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Convoluted Fractiontime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

Wonderland is a territory which any AGM contestant (especially finalist!) would like to visit. However, at the border control, apart from a crazy guy yelling "Yeeeeeeeeeeeeeeeee" there is also another one who might yell "Uooooooooooh" at you and deny your entry. This tragic moment will happen unless you will be able to figure out the solution for the question below:

Given two integers $$$A$$$ and $$$B$$$, you have to find $$$N$$$ ($$$1 \leq N \leq 1000$$$) and a sequence of integers $$$x_1$$$, $$$x_2$$$, ... $$$x_N$$$ such that

$$$\cfrac{A}{B} = x_1 + \cfrac{1}{x_2 + \cfrac{1}{x_3 + \cfrac{1}{x_4 + \cfrac{1}{x_5 + \cfrac{1}{\ddots \cfrac{1}{x_N}}}}}}$$$

In order to fully deserve your "Yeeeeeeeeeeeeee", you will have to solve correctly $$$Q$$$ problems like this.

Input

The first line of input will contain an integer $$$Q$$$ ($$$1 \leq Q \leq 100$$$).

The next $$$Q$$$ lines will contain a pair of integers $$$A$$$ ($$$-10^{18} \leq A \leq 10^{18}$$$), $$$B$$$ ($$$-10^{18} \leq B \leq 10^{18}$$$, $$$B \neq 0$$$).

Output

The output will contain $$$Q$$$ lines. Each line will contain $$$N$$$ followed by the sequence $$$x_1$$$, $$$x_2$$$, ... $$$x_N$$$ ($$$-10^{18} \leq x_i \leq 10^{18}$$$, for $$$1 \leq i \leq N$$$) on the same line, all separated by spaces. In case there are multiple solutions, you could output any.

In order to protect the platform, an additional output limit of 5000 kB has been set to this problem.

Any sequence $$$x_1$$$, $$$x_2$$$, ... $$$x_N$$$ which would imply a division by zero will be awarded with a wrong-answer verdict and not with a runtime error.

ExampleInput
2
1 1
2 1
Output
1 1
2 1 1

加入题单

上一题 下一题 算法标签: