In the new world, we also have a new system called Cybalphabit system.
The system assigns points to each Latin lowercase alphabet as follows:-
'a' is assigned $2^{0}$ , 'b' is assigned $2^{1}$, 'c' $2^{2}$ and so on. Thus, finally 'z' is assigned $2^{25}$ points.

A Cyberstring is a sequence of lowercase Latin alphabets.

Now, the total score of a Cyberstring will be the sum of points of its characters.
You will be given two integers $N$ and $K$. 
Construct a Cyberstring $X$ of length $N$ with total score $K$ or print $-1$ if it is not possible to form the Cyberstring ($X$). 
If there are multiple answers, print any.

------ INPUT: ------

First line contains $T$, the number of test cases.
Each of the next $T$ lines denotes a different test case :
The ${(i+1)}^{th}$ line denotes the $i^{th}$ test case, and contains two integers $N$ and $K$, the length of the string that is to be constructed, and the score of the string respectively. 

------ OUTPUT: ------

For each test case, provide the output on a different line.
Output the required string $X$, if one exists, otherwise output $-1$.

------ Constraints:- ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ n ≤ 10^{5}$
$1  ≤ k  ≤ 5*10^{7}$

The sum of $n$ over all test cases is less than $10^{5}$

----- Sample Input 1 ------ 
4
2 2
2 5
4 5
3 2
----- Sample Output 1 ------ 
aa
ac
baaa
-1
----- explanation 1 ------ 
In the first test case, $n=2$ and $k=2$. So,we have to construct a string of length $2$ with total score $2$. It can be easily seen that the only possible string is "aa". Its total score will be equal to $2^{0} + 2^{0} = 2$.
 
In the second case, "ac" will have score $2^{0} + 2^{2} = 5$. Obviously, "ca" will also have the same score and is also a possible answer.

In the fourth test case, it can be shown that there is no possible string which satisfies the conditions.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Constructive algorithms


Solutions:
d = {2 ** i: chr(i + 97) for i in range(26)}
import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	a = 0
	for i in range(26):
		if k & 1 << i:
			l.append(1 << i)
			a += 1
	if n < a:
		print(-1)
	elif k == n:
		print('a' * n)
	elif a == n:
		answer = ''
		for i in range(a):
			answer += chr(int(math.log(l[i], 2) + 97))
		print(answer)
	else:
		l = []
		temp = k
		while temp:
			maximum = temp & ~(temp - 1)
			l.append(maximum)
			temp -= maximum
		if n < len(l) or n > k:
			print(-1)
			continue
		elif n == len(l):
			answer = ''
			for element in l:
				answer += d[element]
			print(answer)
		else:
			l = sorted(l)
			temp = []
			while len(l) + len(temp) != n:
				x = l.pop(0)
				if x == 1:
					temp.append(1)
					continue
				if x // 2 == 1:
					temp.append(1)
					temp.append(1)
				else:
					l = [x // 2, x // 2] + l
			l += temp
			answer = ''
			for element in l:
				answer += d[element]
			print(answer)