Let's define a function, $\mbox{f}$, on a string, $\boldsymbol{p}$, of length $\boldsymbol{l}$ as follows:

$f(p)=(p_1\cdot a^{l-1}+p_2\cdot a^{l-2}+\cdots+p_l\cdot a^0)\ \text{mod}\ m$

where $p_i$ denotes the ASCII value of the $i^{\mbox{th}}$ character in string $\boldsymbol{p}$, $a=1\textbf{0000}1$, and $m=10^9+7$. 

Nikita has a string, $\boldsymbol{\mathrm{~S~}}$, consisting of $n$ lowercase letters that she wants to perform $\textit{q}$ queries on. Each query consists of an integer, $\boldsymbol{\mbox{k}}$, and you have to find the value of $f(w_k)$ where $w_k$ is the $k^{th}$ alphabetically smallest palindromic substring of $\boldsymbol{\mathrm{~S~}}$. If $w_k$ doesn't exist, print $-1$ instead.

Input Format

The first line contains $2$ space-separated integers describing the respective values of $n$ (the length of string $\boldsymbol{\mathrm{~S~}}$) and $\textit{q}$ (the number of queries). 

The second line contains a single string denoting $\boldsymbol{\mathrm{~S~}}$. 

Each of the $\textit{q}$ subsequent lines contains a single integer denoting the value of $\boldsymbol{\mbox{k}}$ for a query. 

Constraints

$1\leq n,q\leq10^5$  
$1\leq k\leq\frac{n\cdot(n+1)}{2}$  
It is guaranteed that string $\boldsymbol{\mathrm{~S~}}$ consists of lowercase English alphabetic letters only (i.e., $\mbox{a}$ to $\textbf{Z}$).
$a=10^5+1$
$m=10^9+7$. 

Scoring

$1\leq n,q\leq10^3$ for $25\%$ of the test cases.
$1\leq n,q\leq10^5$ for $\textbf{100\%}$ of the test cases.

Output Format

For each query, print the value of function $f(w_k)$ where $w_k$ is the $k^{th}$ alphabetically smallest palindromic substring of $\boldsymbol{\mathrm{~S~}}$; if $w_k$ doesn't exist, print $-1$ instead.

Sample Input
5 7
abcba
1
2
3
4
6
7
8       

Sample Output
97
97
696207567
98
29493435
99
-1

Explanation

There are $7$ palindromic substrings of $\textbf{"abcba''}$. Let's list them in lexicographical order and find value of $w_k$:

$w_1=\textbf{”a''}$, $f(w_1)=97$  
$w_2=\textbf{“a''}$, $f(w_2)=97$  
$w_3=\textbf{"abcba"}$, $f(w_3)=696207567$  
$w_4=\textbf{“b''}$, $f(w_4)=98$  
$w_5=\textbf{“b''}$, $f(w_5)=98$  
$w_6=\textbf{"bcb''}$, $f(w_6)=29493435$  
$w_7=\textbf{“c''}$, $f(w_7)=99$  
$w_8=$ doesn't exist, so we print $-1$ for $k=8$.

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
def Function(S):
	result = 0
	for (i, s) in enumerate(reversed(S)):
		result += ord(s) * (10 ** 5 + 1) ** i
		result %= 10 ** 9 + 7
	return result

def FindPalindromes(S, left, right):
	result = []
	while left >= 0 and right < len(S) and (S[left] == S[right]):
		result += [S[left:right + 1]]
		left -= 1
		right += 1
	return result
(_, nQueries) = map(int, input().split())
S = input()
result = list(S)
for i in range(len(S)):
	result += FindPalindromes(S, i - 1, i)
	result += FindPalindromes(S, i - 1, i + 1)
result.sort()
for __ in range(nQueries):
	K = int(input()) - 1
	print(Function(result[K]) if K < len(result) else -1)


import sys
sys.setrecursionlimit(30000)
from collections import Counter, defaultdict, deque
from math import ceil, floor, factorial, fsum, isinf, exp, log, log10, log2, isfinite, sqrt
from math import pi as PI, e as E
from math import sin, cos, tan, sinh, cosh, tanh, asin, acos, atan
from fractions import Fraction
from itertools import starmap, tee, chain, filterfalse, combinations as combos
from itertools import permutations as perms, product as prod, combinations_with_replacement as rcombos
from functools import reduce, partial
import operator as ops
from operator import __not__ as notit, __abs__ as absit, __or__ as orit
from bisect import insort_left
from copy import deepcopy
(PHI, PHI2) = ((1 + 5 ** 0.5) / 2, (5 ** 0.5 - 1) / 2)
INF = float('inf')

class TreeNode:

	def __init__(self, v):
		self.val = v
		self.left = None
		self.right = None

def setBit(x, offset):
	return x | 1 << offset

def clearBit(x, offset):
	return x & ~(1 << offset)

def getBit(x, offset):
	return 1 if testBit(x, offset) > 0 else 0

def testBit(x, offset):
	return x & 1 << offset

def flipBitAt(x, offset):
	return x ^ 1 << offset

def flipBits(x, length=-1):
	length = x.bit_length() - 1 if length == -1 else length
	return x ^ (1 << length) - 1

def numBits(x):
	return x.bit_length()

def countOnes(x):
	return bin(x).count('1')

def countZeros(x, length=-1):
	length = x.bit_length() if length == -1 else length
	return length - countOnes(x)

def getList(tcast=str):
	return [tcast(x) for x in input().strip().split(' ')]

def getItems(*tcast):
	return map(lambda f, x: f(x), tcast, getList())

def getVal(tcast=str):
	return tcast(input().strip())

def getMatrix(r, tcast=str):
	return [getList(tcast) for row in range(r)]

def isOdd(n):
	return n & 1 > 0

def isEven(n):
	return not n & 1

def numDigits(n):
	return len(str(n)) - (1 if n < 0 else 0)

def _gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def gcd(*xs):
	nums = xs[0] if type(xs[0]) == list else list(xs)
	cur = nums[0]
	for n in nums[1:]:
		if cur == 1:
			return cur
		cur = _gcd(cur, n)
	return cur

def _lcm(a, b):
	return a // gcd(a, b) * b

def lcm(*xs):
	nums = xs[0] if type(xs[0]) == list else list(xs)
	cur = nums[0]
	for n in nums[1:]:
		cur = _lcm(cur, n)
	return cur

def primesUpto(n):
	isp = [True] * (n + 1)
	(isp[0], isp[1]) = (False, False)
	primes = []
	for (i, x) in enumerate(isp):
		if x:
			primes.append(i)
			mults = i * i
			while mults <= n:
				isp[mults] = False
				mults += i
	return primes

def primeFactor(n):
	factors = Counter()
	while not n & 1:
		factors[2] += 1
		n >>= 1
	trynum = 3
	while trynum <= ceil(sqrt(n)):
		while n % trynum == 0:
			factors[trynum] += 1
			n //= trynum
		trynum += 2
	if n != 1:
		factors[n] += 1
	return factors

def isPrime(n):
	if n & 1 and n >= 2:
		trynum = 3
		limit = ceil(sqrt(n))
		while trynum < limit:
			if n % trynum == 0:
				return False
			trynum += 2
		else:
			return True
	else:
		return False

def nthFib(n):
	if n <= 2:
		return 1
	else:
		(a, b) = (1, 1)
		while n > 2:
			(a, b) = (b, a + b)
			n -= 1
		return b

def zipNWith(f, *x):
	return (f(y) for y in zip(*x))

def zipWith(f, xs, ys):
	return (f(x, y) for (x, y) in zip(xs, ys))

def flatten(xs):
	return reduce(ops.concat, xs)

def quantify(pred, it):
	return sum(map(pred, it))

def dotproduct(xs, ys):
	return sum(map(ops.mul, xs, ys))

def adjpairs(it):
	(a, b) = tee(it)
	next(b, None)
	return zip(a, b)

def bipartition(pred, it):
	(t, f) = tee(it)
	return (filter(pred, t), filterfalse(pred, f))

def powerset(it):
	s = list(it)
	return chain.from_iterable((combos(s, r) for r in range(len(s) + 1)))

def depProduct(bounds, f=lambda y: y + 1, g=lambda *x: tuple(x)):
	args = [-1]
	nbounds = len(bounds)
	while args:
		n = len(args)
		args[-1] += 1
		if args[-1] >= bounds[n - 1]:
			args.pop()
		elif n == nbounds:
			yield g(*args)
		else:
			_f = f[n] if type(f) == list else f
			args.append(_f(args[-1]) - 1)

def revEnumerate(xs):
	n = len(xs) - 1
	for (i, x) in enumerate(reversed(xs)):
		yield (n - i, x)

def ispalin(s):
	for i in range(len(s) // 2):
		if s[i] != s[-i - 1]:
			return False
	else:
		return True
(n, nq) = getList(int)
s = getVal(str)
modby = 1000000007
powers = [1]
multby = 100001
checkedpalins = {}
for p in range(n - 1):
	nextpower = powers[-1] * multby % modby
	powers.append(nextpower)

def getval(s):
	total = 0
	for (i, c) in enumerate(s):
		total += ord(c) * powers[len(s) - i - 1]
	return total % modby

def _manichers(s, n, isEven):
	for centerpos in range(n):
		left = centerpos
		right = left + 1 if isEven else centerpos
		buffer = min(centerpos, len(s) - right - 1)
		for i in range(buffer + 1):
			if s[left - i] == s[right + i]:
				yield s[left - i:right + i + 1]
			else:
				break

def manichers(s):
	n = len(s)
	yield from _manichers(s, n, False)
	yield from _manichers(s, n - 1, True)
palincount = Counter(manichers(s))
palinkeys = list(palincount.keys())
palinkeys.sort()
palins = []
for p in palinkeys:
	palins.extend([p] * palincount[p])
for q in range(nq):
	want = getVal(int) - 1
	out = -1
	if want < len(palins):
		wanted = palins[want]
		if wanted not in checkedpalins:
			out = getval(wanted)
			if palincount[wanted] > 1:
				checkedpalins[wanted] = getval(wanted)
		else:
			out = checkedpalins[wanted]
	print(out)


import sys
import math
import time
import bisect
start = time.time()
(n, q) = [int(i) for i in input().strip().split(' ')]
s = input().strip()
palindromes = []
combos = {}

def addCombo(i, j):
	combos[s[i:j]] = combos.get(s[i:j], 0) + 1
for i in range(len(s)):
	twocharstart = 0
	addCombo(i, i + 1)
	if i > 0 and s[i - 1] == s[i]:
		addCombo(i - 1, i + 1)
		for j in range(1, i):
			if i + j >= len(s) or s[i - j - 1] != s[i + j]:
				break
			addCombo(i - 1 - j, i + 1 + j)
	for j in range(1, i + 1):
		if i + j >= len(s) or s[i - j] != s[i + j]:
			break
		addCombo(i - j, i + 1 + j)
a = sorted([(a, b) for (a, b) in combos.items()], key=lambda a: a[0])
acum = 0
findit = []
querysolutions = {}
for i in a:
	acum = acum + i[1]
	findit.append(acum)
for query in range(q):
	k = int(input().strip()) - 1
	if k >= findit[len(findit) - 1] or k < 0:
		print(-1)
	else:
		p = bisect.bisect_right(findit, k)
		s = a[p][0]
		if s not in querysolutions:
			val = 0
			for i in s:
				val *= 100001
				val %= 1000000007
				val += ord(i)
				val %= 1000000007
			querysolutions[s] = val
		print(querysolutions[s])


(n, q) = (int(x) for x in input().split(' '))
text = input()
palindromes = {}
MOD = 1000000007

def func(string):
	t = len(string) - 1
	s = 0
	for c in string:
		s += ord(c) * pow(100001, t, MOD)
		t -= 1
		s %= MOD
	return s

def calculate():
	N = n
	if N == 0:
		return
	N = 2 * N + 1
	L = [0] * N
	L[0] = 0
	L[1] = 1
	C = 1
	R = 2
	i = 0
	iMirror = 0
	start = -1
	end = -1
	diff = -1
	palindromes[text[0]] = 1
	for i in range(2, N):
		iMirror = 2 * C - i
		L[i] = 0
		diff = R - i
		if diff > 0:
			L[i] = min(L[iMirror], diff)
		try:
			while (i + L[i] < N and i - L[i] > 0) and ((i + L[i] + 1) % 2 == 0 or text[(i + L[i] + 1) // 2] == text[(i - L[i] - 1) // 2]):
				L[i] += 1
		except Exception as e:
			pass
		if L[i] > 0:
			j = L[i]
			while j > 0:
				start = (i - j) // 2
				end = start + j
				word = text[start:end]
				j -= 2
				if word in palindromes:
					palindromes[word] += 1
				else:
					palindromes[word] = 1
		if i + L[i] > R:
			C = i
			R = i + L[i]
calculate()
pals = list(palindromes.keys())
pals.sort()
counter = [(pals[0], palindromes[pals[0]], func(pals[0]))]
for k in range(1, len(pals)):
	triple = (pals[k], palindromes[pals[k]] + counter[k - 1][1], func(pals[k]))
	counter.append(triple)
while q > 0:
	q -= 1
	index = int(input()) - 1
	if index >= counter[-1][1]:
		print(-1)
	else:
		for t in counter:
			if t[1] > index:
				print(t[2])
				break


import sys

def all_palindromes(text):
	results = []
	text_length = len(text)
	for (idx, char) in enumerate(text):
		(start, end) = (idx, idx)
		while start >= 0 and end < text_length and (text[start] == text[end]):
			results.append(text[start:end + 1])
			start -= 1
			end += 1
		(start, end) = (idx, idx + 1)
		while start >= 0 and end < text_length and (text[start] == text[end]):
			results.append(text[start:end + 1])
			start -= 1
			end += 1
	return results
global a
global m
a = 100001
m = 10 ** 9 + 7

def fx(obj):
	res = 0
	l = len(obj)
	for (i, c) in enumerate(obj):
		res += ord(c) * a ** (l - (i + 1))
	return res % m

def main():
	(s, q) = input().split(' ')
	q = int(q)
	s = int(s)
	string = input()
	queryval = []
	for i in range(q):
		queryval.append(int(input()))
	output = all_palindromes(string)
	output.sort()
	maxi = len(output)
	for i in range(q):
		if queryval[i] > maxi:
			sys.stdout.write('-1 \n')
		else:
			sys.stdout.write(str(fx(output[queryval[i] - 1])) + '\n')
main()


import heapq

def f(s):
	m = 1000000007
	a = 100001
	result = 0
	for c in s:
		result = (result * a % m + ord(c)) % m
	return result

def palindromic_substrings(s):
	n = len(s)
	for i in range(n):
		radius = 0
		while i - radius >= 0 and i + radius < n and (s[i - radius] == s[i + radius]):
			yield s[i - radius:i + radius + 1]
			radius += 1
	for i in range(n - 1):
		radius = 0
		while i - radius >= 0 and i + radius + 1 < n and (s[i - radius] == s[i + radius + 1]):
			yield s[i - radius:i + radius + 2]
			radius += 1

def functional_palindromes(s, k):
	subs = palindromic_substrings(s)
	sorted_subs = sorted(subs)
	return [f(sorted_subs[ki - 1]) if ki <= len(sorted_subs) else -1 for ki in k]
(n, q) = [int(s) for s in input().split()]
s = input()
k = [int(input()) for _ in range(q)]
for i in functional_palindromes(s, k):
	print(i)


def f(word):
	a = 100001
	m = 10 ** 9 + 7
	l = len(word)
	result = 0
	for letter in word:
		result = (result * a + ord(letter)) % m
	return result

def all_palindromes(word):
	palindromes = []
	n = len(word)
	for (idx, char) in enumerate(word):
		(i, j) = (idx, idx)
		while i >= 0 and j < n and (word[i] == word[j]):
			palindromes.append(word[i:j + 1])
			i -= 1
			j += 1
		(i, j) = (idx, idx + 1)
		while i >= 0 and j < n and (word[i] == word[j]):
			palindromes.append(word[i:j + 1])
			i -= 1
			j += 1
	return sorted(palindromes)
(n, q) = [int(x) for x in input().strip().split()]
word = input().strip()
palindromes = all_palindromes(word)
N = len(palindromes)
for _ in range(q):
	idx = int(input().strip())
	if idx <= N:
		print(f(palindromes[idx - 1]))
	else:
		print(-1)


def f(text):
	ans = 0
	l = len(text)
	if l % 2 == 0:
		for i in range(l // 2):
			ans += (ord(text[i]) * a ** (l - (i + 1)) % m + ord(text[-(i + 1)]) * a ** i % m) % m
	else:
		for i in range(l // 2):
			ans += (ord(text[i]) * a ** (l - (i + 1)) % m + ord(text[-(i + 1)]) * a ** i % m) % m
		ans += ord(text[l // 2]) * a ** (l // 2) % m
	return ans % m

def all_palindromes(text):
	results = list()
	text_length = len(text)
	for (idx, char) in enumerate(text):
		results.append(char)
		(start, end) = (idx - 1, idx + 1)
		while start >= 0 and end < text_length and (text[start] == text[end]):
			results.append(text[start:end + 1])
			start -= 1
			end += 1
		(start, end) = (idx, idx + 1)
		while start >= 0 and end < text_length and (text[start] == text[end]):
			results.append(text[start:end + 1])
			start -= 1
			end += 1
	return list(results)
(n, q) = map(int, input().split())
t = input()
ar = all_palindromes(t)
ar.sort()
a = 10 ** 5 + 1
m = 10 ** 9 + 7
for _ in range(q):
	pos = int(input())
	pos -= 1
	if pos >= len(ar):
		print(-1)
	else:
		palin = ar[pos]
		print(f(palin))


PRIME = 1000000007
BASE = 100001

def power(a, n, modulo):
	if a == 0:
		if n == 0:
			return 1
		else:
			return 0
	result = 1
	current = a
	while n > 0:
		if n % 2 == 1:
			result = result * current % modulo
		n //= 2
		current = current * current % modulo
	return result

def function(w, base, modulo):
	value = 0
	coefficient = 1
	for c in reversed(w):
		value = (value + ord(c) * coefficient) % modulo
		coefficient = coefficient * base % modulo
	return value

def generate_substrings(string, predicate):
	result = []
	for length in range(1, len(string) + 1):
		for position in range(len(string) - length + 1):
			substring = string[position:position + length]
			if predicate(substring):
				result.append(substring)
	return result

class SubString:

	def __init__(self, origin, start, length):
		self.origin = origin
		self.start = start
		self.length = length
		self._hash = None

	def value(self):
		return self.origin[self.start:self.start + self.length]

	def _get_hash(self):
		return hash(self.value())

	def __hash__(self):
		if not self._hash:
			self._hash = self._get_hash()
		return self._hash

	def __cmp__(self, other):
		return self.value().__cmp__(other.value())

def generate_subpalindromes(string):
	result = []
	string_length = len(string)
	for location in range(string_length):
		start = location
		end = location + 1
		while start >= 0 and end <= string_length and (string[start] == string[end - 1]):
			palindrome = string[start:end]
			result.append(palindrome)
			start -= 1
			end += 1
		start = location
		end = location + 2
		while start >= 0 and end <= string_length and (string[start] == string[end - 1]):
			palindrome = string[start:end]
			result.append(palindrome)
			start -= 1
			end += 1
	return result

def is_palindrome(s):
	for position in range(len(s) // 2):
		if s[position] != s[len(s) - 1 - position]:
			return False
	return True

def main():
	(_, queries) = list(map(int, input().split()))
	string = input().strip()
	substrings = generate_subpalindromes(string)
	substrings.sort()
	for _ in range(queries):
		k = int(input()) - 1
		if k < len(substrings):
			substring = substrings[k]
			print(function(substring, BASE, PRIME))
		else:
			print(-1)
main()


(n, q) = map(int, input().split())
s = input()
palindromes = [[] for i in range(27)]

def getIndex(char):
	return ord(char) - ord('a')

def prepare(s):
	for i in range(len(s)):
		for j in range(len(s)):
			if i + j >= len(s) or i - j < 0:
				break
			elif s[i + j] == s[i - j]:
				palin = s[i - j:i + j + 1]
				palindromes[getIndex(s[i - j])].append(palin)
			else:
				break
		if i < len(s) - 1:
			for j in range(len(s)):
				if i + 1 + j >= len(s) or i - j < 0:
					break
				elif s[i + 1 + j] == s[i - j]:
					palin = s[i - j:i + 1 + j + 1]
					palindromes[getIndex(s[i - j])].append(palin)
				else:
					break

def f(palin):
	a = 10 ** 5 + 1
	m = 10 ** 9 + 7
	l = len(palin)
	power = [0] * l
	power[0] = 1
	res = 1 * ord(palin[l - 1])
	for i in range(1, l):
		power[i] = power[i - 1] * a % m
		index = l - i - 1
		res = (res + ord(palin[index]) * power[i]) % m
	return res
prepare(s)
totalPalins = 0
for i in range(27):
	palindromes[i].sort()
	totalPalins += len(palindromes[i])
for i in range(q):
	k = int(input())
	if k > totalPalins:
		print(-1)
	else:
		for i in range(0, 27):
			if k > len(palindromes[i]):
				k = k - len(palindromes[i])
			else:
				palin = palindromes[i][k - 1]
				print(f(palin))
				break


A = 10 ** 5 + 1
M = 10 ** 9 + 7
a_powers = []

def add_palindromes(result, string, i, j):
	while i >= 0 and j < len(string) and (string[i] == string[j]):
		result.append(string[i:j + 1])
		i -= 1
		j += 1

def get_palindromes(string):
	result = []
	for i in range(len(string)):
		add_palindromes(result, string, i, i + 1)
		add_palindromes(result, string, i, i)
	return result

def f(w):
	total = 0
	for i in range(len(w)):
		total += ord(w[i]) * a_powers[len(w) - i - 1] % M
		total %= M
	return total
(n, q) = map(int, input().split())
a_cur = 1
a_powers.append(a_cur)
for i in range(n):
	a_cur = a_cur * A % M
	a_powers.append(a_cur)
s = input()
palindromes = sorted(get_palindromes(s))
for i in range(q):
	k = int(input())
	if k > len(palindromes):
		print(-1)
	else:
		print(f(palindromes[k - 1]))


import sys
a = 100001
m = 10 ** 9 + 7
(n, q) = map(int, input().strip().split(' '))
s = str(input().strip())
pals = list()
for (ndx, char) in enumerate(s):
	(start, end) = (ndx, ndx)
	while start >= 0 and end < n and (s[start] == s[end]):
		pals.append(s[start:end + 1])
		start -= 1
		end += 1
	(start, end) = (ndx, ndx + 1)
	while start >= 0 and end < n and (s[start] == s[end]):
		pals.append(s[start:end + 1])
		start -= 1
		end += 1
pals.sort()
while True:
	try:
		query = int(input().strip())
		try:
			char = pals[query - 1]
			sumP = 0
			l = len(char)
			for (idx, c) in enumerate(char):
				sumP += ord(c) * a ** (l - (idx + 1))
			print(sumP % m)
		except IndexError:
			print('-1')
	except EOFError:
		break


def Function(S):
	result = 0
	for (i, s) in enumerate(reversed(S)):
		result += ord(s) * (10 ** 5 + 1) ** i
		result %= 10 ** 9 + 7
	return result

def FindPalindromes(S, left, right):
	result = []
	while left >= 0 and right < len(S) and (S[left] == S[right]):
		result += [S[left:right + 1]]
		left -= 1
		right += 1
	return result
(_, nQueries) = map(int, input().split())
S = input()
result = list(S)
for i in range(len(S)):
	result += FindPalindromes(S, i - 1, i)
	result += FindPalindromes(S, i - 1, i + 1)
result.sort()
for __ in range(nQueries):
	K = int(input()) - 1
	print(Function(result[K]) if K < len(result) else -1)


def Function(S):
	result = 0
	for (i, s) in enumerate(reversed(S)):
		result += ord(s) * (10 ** 5 + 1) ** i
		result %= 10 ** 9 + 7
	return result

def FindPalindromes(S, left, right):
	result = []
	while left >= 0 and right < len(S) and (S[left] == S[right]):
		result += [S[left:right + 1]]
		left -= 1
		right += 1
	return result
(_, nQueries) = map(int, input().split())
S = input()
result = list(S)
for i in range(len(S)):
	result += FindPalindromes(S, i - 1, i)
	result += FindPalindromes(S, i - 1, i + 1)
result.sort()
for __ in range(nQueries):
	K = int(input()) - 1
	print(Function(result[K]) if K < len(result) else -1)