#P1809C. Sum on Subarrays

    ID: 8322 Type: RemoteJudge 2000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>constructive algorithmsgreedymath*1500

Sum on Subarrays

No submission language available for this problem.

Description

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

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

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

You are given two integers nn and kk. Construct an array aa consisting of nn integers such that:

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

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

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

For each test case, print nn 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 tt (1t50001 \le t \le 5000) — the number of test cases.

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

Output

For each test case, print nn 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.

Sample Input 1

4
3 2
2 0
2 2
4 6

Sample Output 1

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