← 返回题目列表

Codeforces · 1729/F

F. Kirei 和线性函数

中文机器翻译题面 查看原题

给定字符串 $$$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$$$的最小可能值。