F. Yet Another Stone Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$N$$$ piles of stones, where the $$$i$$$-th pile contains $$$A_i$$$ stones. Alice and Bob play a game on these piles. They alternate turns, and Alice moves first. On each turn, the current player must:

  1. choose at least $$$1$$$ and at most $$$K$$$ non-empty piles, and
  2. remove a positive number of stones from each chosen pile.

The number of stones removed may differ between the chosen piles. The player who cannot make a move loses. Both players play optimally.

You are given $$$N$$$, $$$K$$$, $$$S$$$ and the name of a player $$$target$$$. Construct positive integers $$$A_1, A_2, \dots, A_N$$$ such that

  • $$$A_1 + A_2 + \dots + A_N = S$$$, and
  • if the piles initially contain $$$A_1, A_2, \dots, A_N$$$ stones, the player named $$$target$$$ wins the game.

If no such sequence exists, report it.

Input

The first line of the input contains an integer $$$T$$$ $$$(1 \le T \le 300)$$$ denoting the number of test cases. Each of the next $$$T$$$ lines contains three integers $$$N$$$, $$$K$$$, $$$S$$$ $$$(1 \le N \le 10^5$$$, $$$1 \le K \le 10^9$$$, $$$1 \le S \le 10^{18})$$$ and a string $$$target$$$, which is either $$$Alice$$$ or $$$Bob$$$.

The sum of $$$N$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print a single line. If no valid sequence exists, print $$$-1$$$. Otherwise, print $$$N$$$ positive integers $$$A_1, A_2, \dots, A_N$$$ separated by spaces. If there are multiple valid answers, you may print any of them.

Example
Input
3
1 1 2 Alice
1 1 2 Bob
2 1 2 Bob
Output
2
-1
1 1
Note

In the first test case, the only possible position is a single pile of $$$2$$$ stones. Alice removes both stones in her first move, and Bob cannot move, so Alice wins.

In the second test case, the only possible position is again a single pile of $$$2$$$ stones, where Alice wins. So there is no position where Bob wins.

In the third test case, the only possible position is two piles of $$$1$$$ stone each. Since $$$K = 1$$$, Alice must take one of the piles, Bob takes the other one, and Alice cannot move. So Bob wins.