Once again, Vicky is back in the Kingdom of ByteLand. The people of Byteland are very inquisitive about number sequences and Vicky is pondering over a sequence which they called as an X-Sequence .This sequence is described as follows:
The sequence is made of integers: a1, a2, a3, a4...aN where ,
1) |ak − a(k+1)| = X
2) a1 = 0
3) S = a1 + a2 + a3 + .... + aN
Here , X and N are positive integers, and S is the sum. Now, Vicky wants to investigate this X-Sequence, so he would be asking you queries which you have to answer.
The queries can be of two forms:
Type 1: 0 S N which asks you to calculate the number of X-Sequences with Sum = S and number of elements as N. (Two X-Sequences are considered to be different if and only if they have different X and 1 <= X <= 10^8 )
Type 2: 1 S N which asks you to output the X-sequence, with Sum = S and number of elements as N ,with minimum X.
Help Vicky answer the two kinds of queries correctly.
The first line of input consists of number of queries Q after which Q lines follow with each query on a line. There can be two types of queries as mentioned above.
The output should contain Q lines, one for each query.
For Type 1 query, print the query being answered followed by number of distinct X-Sequences possible for 1 <= X <= 10^8, as described above, all in the same line.
For Type 2 query, print the query being answered followed by the sequence as space separated integers. It is guaranteed that there will be at least one sequence for the same. In case there are multiple sequences possible print any one of them.
Q <= 5000 1 <= X <= 10^8 For Type 1 query, −(10^8) <= S <= 10^8, 1 <= N <= 10^6 For Type 2 query, −(10^8) <= S <= 10^8, 1 <= N <= 10^4
Input: 3 0 8 3 1 4 4 0 0 1 Output: 0 8 3 1 1 4 4 0 1 2 1 0 0 1 100000000
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, GO|
Fetching successful submissions