[Solution] Mainak and Interesting Sequence solution codeforces

Mainak and Interesting Sequence solution codeforces – Mainak has two positive integers 𝑛n and 𝑚m.

Table of Contents

[Solution] Mainak and Interesting Sequence solution codeforces

Mainak finds a sequence 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an of 𝑛n positive integers interesting, if for all integers 𝑖i (1𝑖𝑛1≤i≤n), the bitwise XOR of all elements in 𝑎a which are strictly less than 𝑎𝑖ai is 00. Formally if 𝑝𝑖pi is the bitwise XOR of all elements in 𝑎a which are strictly less than 𝑎𝑖ai, then 𝑎a is an interesting sequence if 𝑝1=𝑝2==𝑝𝑛=0p1=p2=…=pn=0.

For example, sequences [1,3,2,3,1,2,3][1,3,2,3,1,2,3][4,4,4,4][4,4,4,4][25][25] are interesting, whereas [1,2,3,4][1,2,3,4] (𝑝2=10p2=1≠0), [4,1,1,2,4][4,1,1,2,4] (𝑝1=112=20p1=1⊕1⊕2=2≠0), [29,30,30][29,30,30] (𝑝2=290p2=29≠0) aren’t interesting.

Here 𝑎𝑏a⊕b denotes bitwise XOR of integers 𝑎a and 𝑏b.

Find any interesting sequence 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (or report that there exists no such sequence) such that the sum of the elements in the sequence 𝑎a is equal to 𝑚m, i.e. 𝑎1+𝑎2+𝑎𝑛=𝑚a1+a2…+an=m.

As a reminder, the bitwise XOR of an empty sequence is considered to be 00.

[Solution] Mainak and Interesting Sequence solution codeforces

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1𝑡1051≤t≤105) — the number of test cases. Description of the test cases follows.

The first line and the only line of each test case contains two integers 𝑛n and 𝑚m (1𝑛1051≤n≤1051𝑚1091≤m≤109) — the length of the sequence and the sum of the elements.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.

Output

For each test case, if there exists some interesting sequence, output “Yes” on the first line, otherwise output “No“. You may print each letter in any case (for example, “YES“, “Yes“, “yes“, “yEs” will all be recognized as positive answer).

If the answer is “Yes“, output 𝑛n positive integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (𝑎𝑖1ai≥1), forming an interesting sequence such that 𝑎1+𝑎2+𝑎𝑛=𝑚a1+a2…+an=m. If there are multiple solutions, output any.

[Solution] Mainak and Interesting Sequence solution codeforces

input

Copy
4
1 3
6 12
2 1
3 6
output

Copy
Yes
3
Yes
1 3 2 2 3 1
No
Yes
2 2 2

[Solution] Mainak and Interesting Sequence solution codeforces

  • In the first test case, [3][3] is the only interesting sequence of length 11 having sum 33.
  • In the third test case, there is no sequence of length 22 having sum of elements equal to 11, so there is no such interesting sequence.
  • In the fourth test case, 𝑝1=𝑝2=𝑝3=0p1=p2=p3=0, because bitwise XOR of an empty sequence is 00.

For Solution

“Click Here”

Leave a Comment