F. xor-sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given four integers $$$n$$$, $$$m$$$, $$$s$$$, $$$x$$$.

You should construct an array of size $$$n$$$, such that:

1)All elements are integers between 0 and $$$m$$$.

2)The sum of the array should be $$$s$$$.

3)The xor sum of the array should be $$$x$$$.

Can you?

Input

The first line of input contains one integer $$$t$$$ $$$(1 \leq t \leq 10 ^ {5})$$$ which is the number of test cases.

For each test case, the input will contain four integers $$$n$$$, $$$m$$$, $$$s$$$, $$$x$$$ $$$(1 \leq n \leq 10^{5})$$$ $$$(0 \leq m \lt 2 ^ {30})$$$ $$$(0 \leq s \leq 10 ^ {18})$$$ $$$(0 \leq x \lt 2 ^ {30})$$$.

The sum of $$$n$$$ overall test cases will not exceed $$$3 \times 10^{5}$$$.

Output

For each test case, if there were no way to construct the array, print $$$-1$$$; otherwise, print an array of size $$$n$$$ that satisfies the rules on a line.

Example
Input
3
4 4 15 7
4 4 4 4
4 4 15 1
Output
4 4 4 3
4 0 0 0
-1