Rule of League solution codeforces

There is a badminton championship in which 𝑛n players take part. The players are numbered from 11 to 𝑛n.

The championship proceeds as follows: player 11 and player 22 play a game, then the winner and player 33 play a game, and then the winner and player 44 play a game, and so on. So, 𝑛1n−1 games are played, and the winner of the last game becomes the champion. There are no draws in the games.

You want to find out the result of championship. Currently, you only know the following information:

  • Each player has either won 𝑥x games or 𝑦y games in the championship.

Given 𝑛n𝑥x, and 𝑦y, find out if there is a result that matches this information.

Input

Rule of League solution codeforces

The first line contains one integer 𝑡t (1𝑡1051≤t≤105) — the number of test cases.

The only line of each test case contains three integers 𝑛n𝑥x𝑦y (2𝑛1052≤n≤1050𝑥,𝑦<𝑛0≤x,y<n).

It is guaranteed that the sum of 𝑛n over all test cases doesn’t exceed 21052⋅105.

Output

Print the answer for each test case, one per line. If there is no result that matches the given information about 𝑛n𝑥x𝑦y, print 1−1. Otherwise, print 𝑛1n−1 space separated integers, where the 𝑖i-th integer is the player number of the winner of the 𝑖i-th game.

If there are multiple valid results, print any.

Example

input

Copy
5
5 2 0
8 1 2
3 0 0
2 0 1
6 3 0

output

Copy

Rule of League solution codeforces

1 1 4 4
-1
-1
2 
-1
Note

In the first test case, player 11 and player 44 won 𝑥x times, player 22 and player 33 won 𝑦y times.

In the second, third, and fifth test cases, no valid result exists.

Solution – CLICK HERE

Leave a Comment

Your email address will not be published.