NSQUARE2 - NSquare Sum ( Medium )

no tags 

N-square Sum! Problem? ( Medium ) 

Given Q pairs of integers Ni, Ai ( 1 <= Ai, Q <= 10^5 , 4 <= N <= 10^2 ) a, find Ni numbers whose square sums is equal to Ai. If there're more than one solution, print the one lexicographically smallest . If there's no solution, print "Impossible".



Q = 1

Ni = 4

A1 = 16


{ 4² + 0² + 0² + 0² = 16}


Input

 There's an integer Q ( 1 <= Q <= 10^5 ) in the first line; it stands for the number of queries. The next Q lines describe each query with two integers Ni, Ai ( 1 <= Ai <= 10^5, 4 <= Ni <= 10^2 ). Ni is the number of integers that you need to find whose sum of squares is equal to Ai.

 Output

 You have to print Q lines, each one with Ni numbers such that the sum of squares is equal to Ai. If there's no solution, you've to print "Impossible".

 Example



Input:

1

4 16

Output:

0 0 0 4


Input:

1

4 15

Output:

1 1 2 3



hide comments
Mateus Dantas [ UFCG ]: 2012-10-02 04:12:40

Thank you Francky! I've adjusted time limit, and now it's feasible in all languages ( I hope so ).

Vaishali Behl: 2012-10-01 12:34:38

Last edit: 2012-10-01 12:49:46
Francky: 2012-10-01 10:14:23

I got 0.00s in C, but TLE in python, with the same algo, time limit is perhaps strict for the small case, don't forget python interpreter is slow to start, it's perhaps the problem, or it's my first part that is too slow (I don't think).

Good problem, it was really fun. Thanks.

:D: 2012-09-30 22:35:24

I didn't mean limits were too loose. It just I'm happy SPOJ has a fast machine now. Leave limits higher, so that script languages can pass.

Mateus Dantas [ UFCG ]: 2012-09-30 14:42:01

I'll set the problem feasible in Python.

Francky: 2012-09-30 14:16:23

OK, but think about Python users, please ! It seems yet very hard in Python, no ?
I always set my problem feasible in Python, even it's harder. What do you think about that ? (My fastest C code is sometimes ×100 faster than my fastest Python one, sometimes it's less, it's often around ×20).

Edit : thanks for your answer.
With the "next" constraints, it would be fun if you give a fast chrono in Python3 (and in C, or other fast language).
It will give a new challenge.
I like this kind of problem. I'll try to find some time to work on it.

Last edit: 2012-09-30 20:58:14
Mateus Dantas [ UFCG ]: 2012-09-30 13:58:55

I'll change the statement limits and recalculate the complexity. This cluster is really fast.

:D: 2012-09-30 11:09:54

You really need to recalculate your complexity estimates for the new cluster :)


Added by:Mateus Dantas [ UFCG ]
Date:2012-09-30
Time limit:0.600s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Manoel Lucas