U503909 踩到第几个 CTH 了？

**注：题目改编自 [【MX-S5-T1】王国边缘](https://www.luogu.com.cn/problem/P11267)** 在原题的基础上增加了新的询问 >Aqr 喜欢踩在 CTH 的身体上走路

**约定记号 $S^c$ 表示字符串 $S$ 循环 $c$ 次拼接而成的字符串。特别地，若 $c=∞$，则表示字符串 $S$ 无限循环拼接而成的字符串。** Aqr 在一个无限循环的 01 字符串 $T=S^∞$ 上进行着他的旅程，一个循环 $S$ 可以被视为是一个 CTH 身体的复制，其中 $S$ 的长度为 $n$，$T$ 的第 $i$ 个字符为 $T_i$，CTH 的第 $c$ 个身体复制品为字符串 $T_{(c-1)\times n+1...c\times n}$。 Aqr 的视野有限，只能看到后面 $m$ 个字符，令人不可思议的的是，**Aqr 可以随意决定 $m$ 的大小**，起初他会不断更改 $m$ 的大小直到他认为当前的 $m$ 是一个合适的视野大小，并且之后不会再更改 $m$。 Aqr 移动的方式如下，当 Aqr 在 $T_i$ 上时： * 若 $T_{i+1…i+m}$ 中存在 1，则 Aqr 下一次会移动到其中最远的一个 1 上。 * 否则，Aqr 下一次会移动到下一个字符 $T_{i+1}$ 上。 所以你需要先回答 **$t$ 次询问**，每次一个不同的 $m$ 和一个位置 $st$，你需要回答 Aqr 站在 $st$ 处一次可以移动到哪个位置上的字符以及可以这个字符处于第几个 CTH 的身体复制品上。 之后 Aqr 会**以最后一个 $m$ 作为视野大小**进行 $q$ 次旅程，每次起点不同，移动次数也不同。 对于这 $q$ 次旅程，你需要告诉 Aqr，他会在哪里停下以及停下的位置正处于 CTH 身体的第几个复制品上。由于答案会很大，你只需要告诉他对 $10^9+7$ 取模后的结果。

第一行，三个正整数 $n,t,q$。 第二行，一个长度为 $n$ 的 01 字符串 $S$。 接下来 $t$ 行，每行两个整数 $st,m$，表示起点在 $T_{st}$，视野大小为 $m$。 接下来 $q$ 行，每行两个整数 $s,k$，表示起点在 $T_s$，移动 $k$ 次。

$t$ 行，每行两个整数，分别表示**Aqr 最远可以看到的位置 $pos$** 以及 **$pos$ 在字符串 $S$ 的第几次循环中，即为 $\lfloor \frac {pos-1}{n} \rfloor$；** $q$ 行，每行两个整数，分别表示**停下的位置 $pos$** 以及 **$pos$ 是循环的第几个字符串中的，即为 $\lfloor \frac {pos-1}{n} \rfloor$。** **所有输出对 $10^9+7$ 取模。**

### 【#样例 1 解释】 T 的前 16 位为 1000101110001011。 * 第一组询问： * 从 1 位置开始的 15 个字符即为区间 $[2,16]$，区间内最后一个 1 的位置在 16 处； * 从 4 位置开始的 3 个字符即为区间 $[5,7]$，区间内最后一个 1 的位置在 8 处。 * 第二组询问： * 第一次旅行，位置移动为 $1→2→5$，$5$ 位于第 1 个循环字符串中。 * 第二次旅行，位置移动为 $4→7→9→10$，$10$ 位于第 2 个循环字符串中。 ### 【数据范围】 **对于所有测试数据，保证：$1≤n≤2×10^5，1≤t≤2\times 10^{6}，1≤m≤10^{18}，1≤q≤2×10^5，1≤s≤10^{18}，0≤k≤10^{18}$。**