codeforces#P1809C. Sum on Subarrays

Sum on Subarrays

Description

For an array $a = [a_1, a_2, \dots, a_n]$, let's denote its subarray $a[l, r]$ as the array $[a_l, a_{l+1}, \dots, a_r]$.

For example, the array $a = [1, -3, 1]$ has $6$ non-empty subarrays:

  • $a[1,1] = [1]$;
  • $a[1,2] = [1,-3]$;
  • $a[1,3] = [1,-3,1]$;
  • $a[2,2] = [-3]$;
  • $a[2,3] = [-3,1]$;
  • $a[3,3] = [1]$.

You are given two integers $n$ and $k$. Construct an array $a$ consisting of $n$ integers such that:

  • all elements of $a$ are from $-1000$ to $1000$;
  • $a$ has exactly $k$ subarrays with positive sums;
  • the rest $\dfrac{(n+1) \cdot n}{2}-k$ subarrays of $a$ have negative sums.

The first line contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases.

Each test case consists of one line containing two integers $n$ and $k$ ($2 \le n \le 30$; $0 \le k \le \dfrac{(n+1) \cdot n}{2}$).

For each test case, print $n$ integers — the elements of the array meeting the constraints. It can be shown that the answer always exists. If there are multiple answers, print any of them.

Input

The first line contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases.

Each test case consists of one line containing two integers $n$ and $k$ ($2 \le n \le 30$; $0 \le k \le \dfrac{(n+1) \cdot n}{2}$).

Output

For each test case, print $n$ integers — the elements of the array meeting the constraints. It can be shown that the answer always exists. If there are multiple answers, print any of them.

4
3 2
2 0
2 2
4 6
1 -3 1
-13 -42
-13 42
-3 -4 10 -2