Codeforces Round 868 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

constructive algorithms

math

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. A-characteristic

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputConsider an array $$$a_1, a_2, \dots, a_n$$$ consisting of numbers $$$1$$$ and $$$-1$$$. Define $$$A$$$-characteristic of this array as a number of pairs of indices $$$1 \le i < j \le n$$$, such that $$$a_i \cdot a_j = 1$$$.

Find any array $$$a$$$ with given length $$$n$$$ with $$$A$$$-characteristic equal to the given value $$$k$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100$$$; $$$0 \le k \le \frac{(n-1) n}{2}$$$) — the length of required array and required $$$A$$$-characteristic.

Output

For each test case, if there is no array $$$a$$$ with given $$$A$$$-characteristic $$$k$$$, print NO.

Otherwise, print YES and $$$n$$$ numbers $$$1$$$ and $$$-1$$$, which form the required array $$$a$$$. If there are multiple answers, print any of them.

Example

Input

72 02 13 13 23 35 45 5

Output

YES 1 -1 YES 1 1 YES 1 -1 1 NO YES 1 1 1 YES -1 1 -1 1 1 NO

Note

In the first test case, there is only one pair of different elements in the array, and their product is $$$a_1 \cdot a_2 = -1 \neq 1$$$, hence its $$$A$$$-characteristic is $$$0$$$.

In the second test case, there is only one pair of different elements in the array, and their product is $$$a_1 \cdot a_2 = 1$$$, hence its $$$A$$$-characteristic is $$$1$$$.

In the third test case, there are three pairs of different elements in the array, and their product are: $$$a_1 \cdot a_2 = -1$$$, $$$a_1 \cdot a_3 = 1$$$, $$$a_2 \cdot a_3 = -1$$$, hence its $$$A$$$-characteristic is $$$1$$$.

In the fourth test case, we can show, that there is no array with length $$$3$$$, which $$$A$$$-characteristic is $$$2$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 21:05:18 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|