Given the string $s$ of decimal digits (0-9) of length $n$.

A substring is a sequence of consecutive characters of a string. The substring of this string is defined by a pair of indexes — with its left and right ends. So, each pair of indexes ($l, r$), where $1 \le l \le r \le n$, corresponds to a substring of the string $s$. We will define as $v(l,r)$ the numeric value of the corresponding substring (leading zeros are allowed in it).

For example, if $n=7$, $s=$"1003004", then $v(1,3)=100$, $v(2,3)=0$ and $v(2,7)=3004$.

You are given $n$, $s$ and an integer $w$ ($1 \le w < n$).

You need to process $m$ queries, each of which is characterized by $3$ numbers $l_i, r_i, k_i$ ($1 \le l_i \le r_i \le n; 0 \le k_i \le 8$).

The answer to the $i$th query is such a pair of substrings of length $w$ that if we denote them as $(L_1, L_1+w-1)$ and $(L_2, L_2+w-1)$, then:

$L_1 \ne L_2$, that is, the substrings are different;

the remainder of dividing a number $v(L_1, L_1+w-1) \cdot v(l_i, r_i) + v(L_2, L_2 + w - 1)$ by $9$ is equal to $k_i$.

If there are many matching substring pairs, then find a pair where $L_1$ is as small as possible. If there are many matching pairs in this case, then minimize $L_2$.

Note that the answer may not exist.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — number of input test cases.

The first line of each test case contains a string $s$, which contains only the characters 0-9 and has a length $n$ ($2 \le n \le 2 \cdot 10^5$).

The second line contains two integers $w, m$ ($1 \le w < n, 1 \le m \le 2 \cdot 10^5$), where $n$ — is the length of the given string $s$. The number $w$ denotes the lengths of the substrings being searched for, and $m$ is the number of queries to be processed.

The following $m$ lines contain integers $l_i, r_i, k_i$ ($1 \le l_i \le r_i \le n$, $0 \le k_i \le 8$) — $i$th query parameters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. It is also guaranteed that the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each request, print in a separate line:

left borders of the required substrings: $L_1$ and $L_2$;

-1 -1 otherwise, if there is no solution.

If there are several solutions, minimize $L_1$ first, and minimize $L_2$ second.


-----Examples-----

Input
5
1003004
4 1
1 2 1
179572007
4 2
2 7 3
2 7 4
111
2 1
2 2 6
0000
1 2
1 4 0
1 4 1
484
1 5
2 2 0
2 3 7
1 2 5
3 3 8
2 2 6
Output
2 4
1 5
1 2
-1 -1
1 2
-1 -1
1 3
1 3
-1 -1
-1 -1
-1 -1


-----Note-----

Consider the first test case of example inputs. In this test case $n=7$, $s=$"1003004", $w=4$ and one query $l_1=1$, $r_1=2$, $k_1=1$. Note that $v(1,2)=10$. We need to find a pair of substrings of length $4$ such that $v(L_1, L_1+3)\cdot10+v(L_2,L_2+3)$ has a remainder of $k_1=1$ when divided by $9$. The values $L_1=2, L_2=4$ actually satisfy all the requirements: $v(L_1, L_1+w-1)=v(2,5)=30$, $v(L_2, L_2+w-1)=v(4,7)=3004$. Indeed, $30\cdot10+3004=3304$, which has a remainder of $1$ when divided by $9$. It can be shown that $L_1=2$ is the minimum possible value, and $L_2=4$ is the minimum possible with $L_1=2$.

Difficulty: HARD
Tags: String algorithms

Mathematics

Starter code:

Solutions:
from collections import defaultdict
import sys
input = sys.stdin.readline

def get_remainder(i, j):
	if i == 0:
		return pref[j]
	else:
		return (pref[j] - pref[i - 1]) % 9
for _ in range(int(input())):
	s = [int(i) for i in input().strip()]
	n = len(s)
	pref = []
	cur = 0
	for i in range(n):
		cur = cur * 10 + s[i]
		cur %= 9
		pref.append(cur)
	(w, m) = map(int, input().split())
	dic = defaultdict(lambda : [])
	for i in range(n - w + 1):
		cur = get_remainder(i, i + w - 1)
		dic[cur].append(i)
	ans = []
	for qi in range(m):
		(l, r, k) = map(int, input().split())
		cur = get_remainder(l - 1, r - 1)
		flag = 0
		for i in dic:
			req = (-(cur * i) + k) % 9
			lst = [req]
			if req != i and req in dic:
				ans.append([dic[i][0] + 1, dic[req][0] + 1])
				flag = 1
			elif req == i and len(dic[i]) >= 2:
				ans.append([dic[i][0] + 1, dic[i][1] + 1])
				flag = 1
			if flag:
				break
		if not flag:
			ans.append([-1, -1])
	for i in ans:
		print(*i)