CF1729F.Kirei and the Linear Function

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 \lt 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.

给定一个长度为 $n$ 的十进制数字字符串 $s$（字符为 0–9）。

子串是指字符串中连续的一段字符。该字符串的一个子串由其左右端点的下标对唯一确定。因此，每一对下标 $(l, r)$（满足 $1 \le l \le r \le n$）对应字符串 $s$ 的一个子串。我们记 $v(l,r)$ 为该子串所表示的数值（允许前导零）。

例如，若 $n=7$，$s=$"1003004"，则 $v(1,3)=100$，$v(2,3)=0$，$v(2,7)=3004$。

你将获得 $n$、$s$ 和一个整数 $w$（$1 \le w \lt n$）。

你需要处理 $m$ 个查询，每个查询由三个整数 $l_i, r_i, k_i$ 描述（满足 $1 \le l_i \le r_i \le n$；$0 \le k_i \le 8$）。

第 $i$ 个查询的答案是一对长度均为 $w$ 的子串，记作 $(L_1, L_1+w-1)$ 和 $(L_2, L_2+w-1)$，满足：

• $L_1 \ne L_2$，即这两个子串位置不同；
• 数值 $v(L_1, L_1+w-1) \cdot v(l_i, r_i) + v(L_2, L_2 + w - 1)$ 除以 $9$ 的余数等于 $k_i$。

若存在多组满足条件的子串对，则选择其中 $L_1$ 最小的一组；若仍有多个，则在这些中选择 $L_2$ 最小的一组。

注意：答案可能不存在。

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 \lt 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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 输入测试用例的数量。

每个测试用例的第一行包含一个字符串 $s$，该字符串仅由字符 0–9 组成，长度为 $n$（$2 \le n \le 2 \cdot 10^5$）。

第二行包含两个整数 $w, m$（$1 \le w \lt n,\ 1 \le m \le 2 \cdot 10^5$），其中 $n$ 是给定字符串 $s$ 的长度。数值 $w$ 表示所查找子串的长度，$m$ 表示需处理的查询数量。

接下来的 $m$ 行每行包含三个整数 $l_i, r_i, k_i$（$1 \le l_i \le r_i \le n,\ 0 \le k_i \le 8$）—— 第 $i$ 个查询的参数。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。同时保证所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

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.

对于每个查询，在单独一行中输出：

• 所需子串的左边界：$L_1$ 和 $L_2$；
• 若无解，则输出 -1 -1。

若存在多个解，优先最小化 $L_1$，其次最小化 $L_2$。

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$.

考虑示例输入的第一个测试用例。在此测试用例中，$n=7$，$s=$"1003004"，$w=4$，且有一个查询：$l_1=1$，$r_1=2$，$k_1=1$。注意 $v(1,2)=10$。我们需要找到一对长度为 $4$ 的子串，使得 $v(L_1, L_1+3)\cdot10+v(L_2,L_2+3)$ 除以 $9$ 的余数为 $k_1=1$。实际上，取 $L_1=2$、$L_2=4$ 满足所有要求：$v(L_1, L_1+w-1)=v(2,5)=30$，$v(L_2, L_2+w-1)=v(4,7)=3004$。确实，$30\cdot10+3004=3304$，而 $3304$ 除以 $9$ 的余数为 $1$。可以证明，$L_1=2$ 是可能的最小值，且在 $L_1=2$ 的前提下，$L_2=4$ 是可能的最小值。