Read problems statements in Mandarin Chinese , Russian and Vietnamese as well. 
Akhil has an array consisting of N positive integers. As we know that there are (N*(N+1))/2 non-empty contiguous subarrays in an array of size N. Akhil found that exactly E of the contiguous subarrays had even sum and remaining O = (N*(N+1))/2 - E have odd sum.

Next day, he lost the original array. But he still remembered the E and O values correctly. Now, he wants to recreate any such array which has exactly E even sum continuous subarrays and O odd ones. If there are many such possible arrays, printing any one of them will make him happy.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows:
First line of each test case contains an integer N denoting the length of lost array.
Second line of each test case contains two space separated integers E and O, denoting number of contiguous subarrays with even and odd sums, respectively. 

------ Output ------ 

For each test case, output a single line containing all the integers of an array separated by a space.
Each integer should lie between 0 and 100(both inclusive).
If there is no such possible array, print -1 in a single line.

------ Constraints ------ 

$0 ≤ E, O ≤ N*(N+1)/2$
$E + O = N*(N+1)/2$

------ Subtasks ------ 

Subtask #1 (20 points) : 1 ≤ sum of N over all test cases ≤ 15
Subtask #2 (20 points) : 1 ≤ sum of N over all test cases ≤ 2 * 10^{3}
Subtask #3 (60 points) : 1 ≤  sum of N over all test cases  ≤ 10^{6}

------ Example ------ 

Input:
3
3
2 4
3
3 3
3
0 6

Output:
2 1 2
1 2 2
-1

------ Explanation ------ 

Example case 1. There are total 6 subarrays : {2},{1},{2},{2,1},{1,2},{2,1,2}. Their sums {2, 1, 2, 3, 3, 5} are respectively. As 2 of them are even and 4 of them are odd. So, this is one possible answer which satisfies Akhil's requirements.
Example case 3. There is no array of length 3 whose all the subarrays have odd sum. Akhil might have remembered something incorrectly. Hence, you should print -1.

Source: codechef | Difficulty: VERY_HARD
Tags: Constructive algorithms

Range queries

Number theory

Mathematics

Ad-hoc


Solutions:
import sys

def compute(n):
	res = {}
	for i in range(0, n + 1):
		res[i * (n + 1 - i)] = i
	return res

def output(n, k):
	for i in range(1, n + 1):
		if i == k:
			sys.stdout.write('1 ')
		else:
			sys.stdout.write('2 ')
	sys.stdout.write('\n')
	sys.stdout.flush()
ans = {}
tc = int(sys.stdin.readline().split()[0])
for i in range(tc):
	n = int(sys.stdin.readline().split()[0])
	if n not in ans:
		ans[n] = compute(n)
	odd = int(sys.stdin.readline().split()[1])
	if odd in ans[n]:
		output(n, ans[n][odd])
	else:
		print('-1')