给定字符串 $$$s$$$,其十进制数字 (0-9) 长度为 $$$n$$$。
子字符串是字符串的连续字符序列。该字符串的子字符串由一对索引及其左端和右端定义。因此,每对索引 ($$$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 < n$$$)。
您需要处理 $$$m$$$ 查询,每个查询的特征是 $$$3$$$ 数字 $$$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$$$。
请注意,答案可能不存在。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入测试用例的数量。
每个测试用例的第一行包含一个字符串 $$$s$$$,该字符串仅包含字符 0-9,长度为 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。
第二行包含两个整数 $$$w, m$$$ ($$$1 \le w < 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$$$。
输出
对于每个请求,在单独的行中打印:
- 所需子字符串的左边框:$$$L_1$$$ 和 $$$L_2$$$;
- -1 -1 否则,如果没有解决方案。
如果有多个解决方案,请首先最小化$$$L_1$$$,然后最小化$$$L_2$$$。
示例
输入 #1
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
输出 #1
2 4 1 5 1 2 -1 -1 1 2 -1 -1 1 3 1 3 -1 -1 -1 -1 -1 -1
注意
考虑示例输入的第一个测试用例。在此测试用例中 $$$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$$$,除以$$$9$$$ 后余数为$$$1$$$。可以证明$$$L_1=2$$$是最小可能值,$$$L_2=4$$$是$$$L_1=2$$$的最小可能值。