题目描述

给你一个数字构成的字符串 $s$。有 $n$ 个问题。

每个问题会给你三个整数 $l,r,m$，请输出 $s$ 从左数第 $l$ 个字符到第 $r$ 个字符构成的数除以 $m$ 的余数。

输入格式

第一行一个整数 $n$。

第二行一个字符串 $s$。

接下来 $n$ 行，每行两个整数 $l,r,m$，即当前问题。

输出格式

$n$ 行，每行分别是每个问题的答案。

3
12345678901234567890
9 15 33
4 7 100
1 2 1000

12
67
12

样例解释

9012345 % 33 = 12
4567 % 100 = 67
12 % 1000 = 12

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,|s| \le 1000$，$1\le l \le r\le |s|$, $1\le m\le 998244353$。

• 子任务 1（30 分）：保证 $l=r$。
• 子任务 2（30 分）：保证 $m=1000$。
• 子任务 3（40 分）：保证 $m=998244353$。