U297797 2023“郡园杯”春季编程挑战活动C

给定长度为 $n$ 的字符串 $s$（下标为 $0 \sim n-1$），字符串仅由小写字母和数字字符构成。 给定 $q$ 个下标区间 $[l,r]$。你需要回答：子串 $s[l\dots r]$ 中数字之和是多少？需要注意的是，**连续的多个数字字符将被视为一个数字**。 由于答案可能很大，答案只需输出对 $10000$ 取模的结果。

第一行输入两个正整数 $n$ 和 $q$。 第二行输入一个字符串 $s$。 接下来 $q$ 行，每行输入两个整数 $l$ 和 $r$，表示询问的区间。

输出 $q$ 行，每行一个正整数，表示答案。

【样例解释】 对于样例 $1$： 第一个子串为 `qwert456789hi98`，答案为 `(456789+98)%10000=6887`。 第二个子串为 `qwer`，答案为 `0`。 第三个子串为 `456789`，答案为 `456789%10000=6789`。 第四个子串为 `89hi`，答案为 `89`。 第五个子串为 `56789hi9`，答案为 `(56789+9)%10000=6798`。 【测试点约束】 对于所有测试点：$1\leq q\leq 10^5$，$1\leq n\leq 10^5$，$0\leq l\leq r