简单字符串

题号：NC201916
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

对于字符串 ${s}$ 和整数 ${k}$ ，定义 ${f(s,k)}$ 为，将 ${s}$ 划分为至多 ${k}$
段 $u_1,u_2,\ldots u_l$ ，最小化 $\max_{1\leq i\leq l} u_i$ (比较按照字典序) ，求最小化的结果。
现在我们有一个字符串 ${S}$ ， ${q}$ 次询问 $f(s[l_i\ldots |s|],k_i)$ 的值，对于每个询问输出 $a_i,b_i$ 表示 $f(s[l_i\ldots |s|], k_i)=S[a_i\ldots b_i]$ ，其中要求 $S[a_i \ldots b_i]$ 在一个可能的划分中。
如果有多个，输出 $a_i$ 最小的解，要求 $a_i \geq l_i$ 。

输入描述:

第一行一个字符串  和一个整数  ，意义如题目所示。
接下来的  行每行两个整数  ，表示一个询问。
 。
保证  由小写字母构成。

输出描述:

对于每个询问，输出  表示
 。

示例1

输入

复制

abaababa 2
1 4
3 2

输出

复制

1 2
3 7