B. Echo Form
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Constructive Kingdom is still chasing Little T...

Define the prefix $$$\max$$$ sequence $$$x$$$ of a sequence $$$a$$$ of length $$$n$$$ as $$$x_i = \max\{a_j : 1 \le j \le i\}$$$, and the prefix $$$\min$$$ sequence $$$y$$$ as $$$y_i = \min\{a_j : 1 \le j \le i\}$$$.

Given $$$n$$$ and $$$k$$$, please construct two sequences $$$a$$$ and $$$b$$$, both of length $$$n$$$, that satisfy the following conditions. If no such two sequences exist, report that there is no solution:

  • $$$a$$$ and $$$b$$$ are permutations of $$$1$$$ to $$$n$$$.
  • $$$a$$$ and $$$b$$$ differ in at least one position, i.e., there exists an $$$i$$$ such that $$$a_i \ne b_i$$$.
  • For each of $$$a$$$ and $$$b$$$, let its prefix $$$\max$$$ sequence be $$$x$$$ and its prefix $$$\min$$$ sequence be $$$y$$$. It must satisfy: $$$$$$ \sum_{i=1}^n (x_i - y_i) = k. $$$$$$
Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$), indicating the number of test cases.

Each test case consists of a single line containing two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5, 0 \le k \le 10^{10}$$$), representing the length of the sequences and the required sum of differences between the prefix $$$\max$$$ and $$$\min$$$.

It is guaranteed that $$$\sum n \le 3 \times 10^5$$$ over all test cases.

Output

For each test case, if there exist two sequences satisfying the conditions, output two lines.

The first line should contain $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, representing your constructed sequence $$$a$$$.

The second line should contain $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$, representing your constructed sequence $$$b$$$.

If no such two sequences exist, output a single line containing the integer $$$-1$$$.

If there are multiple valid answers, you may output any of them.

Example
Input
3
2 1
2 0
5 12
Output
1 2
2 1
-1
1 3 4 2 5
1 2 4 5 3
Note

For the 3rd testcase, let's verify if a hypothetical sequence $$$b = \{1, 2, 4, 5, 3\}$$$ satisfies the conditions:

  • $$$\{1, 2, 4, 5, 3\}$$$ is a permutation of $$$1$$$ to $$$5$$$ because each integer from $$$1$$$ to $$$5$$$ appears exactly once.
  • Suppose the second element of sequence $$$a$$$ is $$$a_2 = 3$$$, and $$$b_2 = 2$$$, then $$$a_2 \ne b_2$$$.
  • Its prefix $$$\max$$$ sequence is $$$x = \{1, 2, 4, 5, 5\}$$$, and its prefix $$$\min$$$ sequence is $$$y = \{1, 1, 1, 1, 1\}$$$. Thus, we have $$$$$$ \sum_{i=1}^n (x_i - y_i) = (1 - 1) + (2 - 1) + (4 - 1) + (5 - 1) + (5 - 1) = 0 + 1 + 3 + 4 + 4 = 12 = k. $$$$$$

Additional Notes

A permutation of $$$1$$$ to $$$n$$$ is a sequence of length $$$n$$$ in which every integer from $$$1$$$ to $$$n$$$ appears exactly once.