*"Raju - zor zor se bolke sabko scheme bata de".  
Raju intends to scam everyone in order to become rich quickly. But before doing that, he must prove to everyone his innocence, by doubling his own money with the help of a scheme.*

Raju wants to double his money, but in order to invest in the scheme, he is required to solve the following problem. He has asked you to help him in solving the problem.

You are given the following:
K strings P_{1}, P_{2}, P_{3}, \ldots, P_{K}
A string S of length N.
Some number of available characters from 'a' to 'z'. This is given to you as an array C of size 26, where C_{1} is the number of 'a'-s, C_{2} is the number of 'b'-s, \ldots, C_{26} is the number of 'z'-s you have.

Solve the following problem independently for each X from 0 to K:
Is it possible to append some (possibly 0) characters to S from the available characters such that the resulting string is strictly lexicographically greater than *exactly* X of the given K strings?

Note that the process is independent for each X. That is, for each X, you start with the original string S and the values C_{1}, C_{2}, \ldots, C_{26} given in the input.

Note: A string A is said to be lexicographically larger than a string B if:
B is a proper prefix of A (for example, abc is larger than a and ab); or
Let i be the first position where A and B differ (i.e, A_{1} = B_{1}, A_{2} = B_{2}, \ldots, A_{i-1} = B_{i-1}). Then, A_{i} > B_{i}.

------ Input Format ------ 

- The first line of input will contain one integer N, the size of the string S.
- The second line of input will contain string S.
- The third line of input will contain 26 space-separated integers, representing the values C_{1}, C_{2}, \ldots, C_{26}.
- The fourth line of input will contain one integer K.
- The i-th of the next K lines of input will contain the string P_{i}.

------ Output Format ------ 

Print K+1 lines of output. The i-th of these lines should contain the answer for X = i-1: Yes if it's possible to append some of the given characters to S to make it strictly lexicographically larger than exactly i-1 strings, and No otherwise.

Each letter of the output may be printed in either uppercase or lowercase, i.e, Yes, YES, and yEs will all be treated as equivalent.

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

$1 ≤ N ≤ 10^{4}$
$0 ≤ C_{i} ≤ 10^{6}$
$1 ≤ K ≤ 10^{4}$
$1 ≤ |P_{i}| ≤ 10^{4}$
- Every input string will contain only lowercase English letters, i.e, the letters from $a$ to $z$.
- The sum of $|P_{i}|$ across all $K$ strings won't exceed $10^{5}$.

----- Sample Input 1 ------ 
4
abcd
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
6
abc
abcd
ab
abcde
a
abcd

----- Sample Output 1 ------ 
No
No
No
Yes
No
Yes
Yes

----- explanation 1 ------ 
The answer for a few values of $X$ is as follows:

- $X = 3$: Leave $S$ unchanged, and it is already greater than exactly three of the given strings ("abc", "ab", "a"). So, the answer is "Yes".
- $X = 4$: There is no way to append some characters to the string $S$ from the ones we have (one copy each of 'a', 'c', 'z') such that the resulting string will be greater than exactly $4$ strings out of the given $6$ strings. So, the output is "No".
- $X = 5$: Append 'c' to $S$, to form "abcdc". This is greater than all the input strings except "abcde", as needed.
- $X = 6$: Append 'z' to $S$, to form "abcdz". This is greater than every input string.

Source: codechef | Difficulty: VERY_HARD
Tags: String algorithms

Sorting

Data structures

Ad-hoc


Solutions:
n = int(input())
s = input()
have = list(map(int, input().split()))
k = int(input())
strings = sorted(list((input() for _ in range(k))))
strings.append((len(strings[-1]) + 5) * 'z')
print('Yes' if s <= strings[0] else 'No')
for i in range(k):
	if strings[i] == strings[i + 1] or s > strings[i + 1]:
		print('No')
		continue
	if s > strings[i]:
		print('Yes')
		continue
	if len(strings[i]) < n or strings[i][:n] != s:
		print('No')
		continue
	used = [0 for _ in range(26)]
	ans = 'Yes'
	ispref = strings[i + 1][:n] == s
	for pos in range(n, 200000):
		hi = 0
		if ispref == True:
			hi = ord(strings[i + 1][pos]) - ord('a') + 1
		else:
			hi = 26
		if pos == len(strings[i]):
			ans = 'No'
			for c in range(hi):
				if used[c] < have[c]:
					ans = 'Yes'
					break
			break
		lo = ord(strings[i][pos]) - ord('a') + 1
		ans = 'No'
		for c in range(lo, hi):
			if used[c] < have[c]:
				ans = 'Yes'
				break
		if ans == 'Yes':
			break
		if used[lo - 1] < have[lo - 1]:
			used[lo - 1] += 1
			if ispref == True and strings[i][pos] != strings[i + 1][pos]:
				ispref = False
			ans = 'Yes'
			continue
		ans = 'No'
		break
	print(ans)