We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Constructive Algorithms
  4. Array Construction

Array Construction

Professor GukiZ has hobby — constructing different arrays. His best student, Nenad, gave him the following task that he just can't manage to solve:

Construct an -element array, , where the sum of all elements is equal to and the sum of absolute differences between each pair of elements is equal to . All elements in must be non-negative integers.

If there is more then one such array, you need to find the lexicographically smallest one. In the case no such array exists, print .

Note: An array, , is considered to be lexicographically smaller than another array, , if there is an index such that and, for any index , .

Input Format

The first line contains an integer, , denoting the number of queries.
Each of the subsequent lines contains three space-separated integers describing the respective values of (the number of elements in array ), (the sum of elements in ), and (the sum of absolute differences between each pair of elements).

Constraints

Subtasks

For of the maximum score:

For of the maximum score:

Output Format

For each query, print space-separated integers describing the respective elements of the lexicographically smallest array satisfying the conditions given above. If no such array exists, print instead.

Sample Input

 1
 3 3 4

Sample Output

 0 1 2

Explanation

We have query in which , , and . The lexicographically smallest array is .

  • The sum of array 's elements is

  • The absolute differences between each pair of elements are:


    The sum of these absolute differences is

As array is both lexicographically smallest and satisfies the given conditions, we print its contents on a new line as 0 1 2.