Best Cake Ever
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.Chef is baking a large cake! The cake consists of $N$ different ingredients numbered $1$ through $N$. Chef can choose how much of each ingredient to use in his cake recipe; let's denote the amount of the $i$-th ingredient used in the cake by $g_i$. Chef can only measure ingredients in fixed whole units, so the amounts of all ingredients must be integers. In order to keep the cake inexpensive (and, of course, use each ingredient from the recipe), the chosen amounts of ingredients have to satisfy the condition $1 \le g_i \le K$ (for each $1 \le i \le N$). The *taste* of the resulting cake is computed as the bitwise XOR of the amounts of all ingredients, i.e. $g_1 \oplus g_2 \oplus \dots \oplus g_N$. For example, if $N=3$ and $g = [1, 2, 5]$, the taste of the cake is equal to $1 \oplus 2 \oplus 5 = 6$. Please help Chef and find one way to choose the amounts of all ingredients such that the taste of the cake is maximum possible. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first and only line of each test case contains two space-separated integers $N$ and $K$. ### Output For each test case, print a single line containing $N$ space-separated integers $g_1, g_2, \dots, g_N$ — the amounts of ingredients $1, 2, \dots, N$. ### Constraints - $1 \le T \le 40$ - $1 \le N \le 10^4$ - $1 \le K \le 10^9$ ### Example Input ``` 2 3 5 4 3 ``` ### Example Output ``` 5 1 3 1 2 3 3 ``` ### Explanation **Example case 1:** The maximum possible taste of the cake is $5 \oplus 1 \oplus 3 = 7$. **Example case 2:** The maximum possible taste is $1 \oplus 2 \oplus 3 \oplus 3 = 3$.
|Tags||constructive, cook94, hloya_ygrt, xor|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.