SUM1SEQ - Sum of one-sequence

We say that a sequence of integers is a one-sequence if the difference between any two consecutive numbers in this sequence is 1 or -1 and its first element is 0. More precisely: [a1, a2, ..., an] is a one-sequence if

  • for any k, such that 1 <= k < n : |ak - ak+1| = 1 and
  • a1 = 0

Task

Write a program that for each test case:

  • reads two integers describing the length of the sequence and the sum of its elements;
  • finds a one-sequence of the given length whose elements sum up to the given value or states that such a sequence does not exist;
  • writes the result to the standard output.

Input

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.

In the first line of a test case there is a number n, such that 1 <= n <= 10 000, which is the number of elements in the sequence. In the second line there is a number S, which is the sum of the elements of the sequence, such that |S| <= 50 000 000.

Output

For each test case there should be written n integers (each integer in a separate line) that are the elements of the sequence (k-th element in the k-th line) whose sum is S or the word "No" if such a sequence does not exist. If there is more than one solution your program should output any one.

Consequent test cases should by separated by an empty line.

Example

Input:
1
8
4

Output:
0
1
2
1
0
-1
0
1

Added by:MichaƂ Czuczman
Date:2004-08-10
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:5th Polish Olympiad in Informatics, stage 1 (Grzegorz Jakacki)

hide comments
2015-09-13 09:46:58 Oasis
Very Gud question..few wa due to silly mistakes and not testing corner cases..
2014-09-11 14:57:10 jkelava6
My code prints 0 1 0 1 0 1 0 1, and yes it should be correct! "If there is more than one solution your program should output any one."
2013-06-24 10:43:01 V Sriharsha
is 0 1 0 1 0 1 0 1 not a solution of above test case?
2011-08-18 06:54:58 Wu Huachi
I think there exists some cases which n is larger than 10000
2011-05-17 07:48:16 Anuj Mahajan
plz....someone give more testcases
2010-08-28 20:15:10 rizwan hudda
@pritam cool down buddy. This problem was not set by amritapuri psetters,it is like 5 years old if u read the source in this page. The test data is correct here. Moreover the amritapuri versions constraints were very low to test the logic. Might be the test data was also weak.
2010-01-05 12:33:06 Pritam Bhattacharya
@Michal : I could even send you my code if you provide me with your email .. & maybe you could check it out once manually ? thing is, I'm pretty confident that it is correct .. am I asking too much ??
2010-01-05 12:30:58 Pritam Bhattacharya
@Michal : hey buddy, could you please make sure that your test case judging is correct one more time, coz the piece of code submitted by me that is getting "WA" for this problem was actually accepted by Mooshak in the online qualifying round for ACM ICPC 2009 Regionals at Asia-Amritapuri site, where precisely this problem was set !

Last edit: 2010-01-05 12:31:32
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.