SPOJ.com - Problem NSQUARE2

NSQUARE2 - NSquare Sum ( Medium )

no tags

Given Q pairs of integers Ni, Ai (1 <= Ai, Q <= 10⁵, 4 <= N <= 100), 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⁵) 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⁵, 4 <= Ni <= 100). 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

Submit solution!

hide comments



	nadstratosfer: 2019-12-21 22:20:18 Managed to get a green bar barely knowing what I was doing, during a nasty migraine episode. My code is likely doing some stupid stuff, will have to revisit when in shape for it. Hopefully won't be as painful the next time ;) Edit: 0.02s after translating to C. Still not fond of my algorithm.. Last edit: 2019-12-22 18:08:00
	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 ).
	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 :)

Submit solution!

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