采集矿石

**ZRQ** 成功从坍塌的洞穴中逃了出来。终于，他看到了要研究的矿石。他想挑一些带回去完成任务。 题目来源：[Zhang\_RQ](https://www.luogu.org/space/show?uid=31565)~~哦对了 ZRQ 就他，嗯~~

**ZRQ** 发现这里有 $N$ 块排成一排的矿石。 他用一个小写字母来表示每块矿石，他还发现每块矿石有一个重要度 $V_i$。 **ZRQ** 想采集一段连续的矿石回研究所。 他非常严格，被采集的一段矿石必须满足**小写字母的字典序降序排名等于这段矿石的重要度和。** **这里多个出现在不同位置的本质相同串的字典序排名相同。** 比如说字母串为 `aa`，那么第一个 `a` 的排名和第二个 `a` 的排名相同，都是 `2`（第 `1` 是 `aa`）。 **ZRQ** 问你，在原串中有哪些不同的子串可以被采集？ **这里子串不同定义为出现位置不同，也就是说本质相同的子串出现在不同位置都要计算一次（当然重要度和等于排名是前提）。** 比如共有 $4$ 块矿石，小写字母串为 `abcd`，重要度各为 `10 0 1 1`。 我们把所有的子串按照字典序从大到小排名：`1:d 2:cd 3:c 4:bcd 5:bc 6:b 7:abcd 8:abc 9:ab 10:a`。 那么串 `d` 的排名为 $1$（第一大），重要度和为 $1$，可以被采集。 串 `cd` 的排名为 $2$，重要度和为 $2$，可以被采集。 串 `a` 的排名为 $10$，重要度和为 $10$，可以被采集。 其他串则不满足这个条件，故有三个串可以被采集。

第一行一个长度为 $N$ 由小写字母组成的字符串，每个字符代表一个矿石。 第二行 $N$ 个整数，表示 $V_i$。

一行一个整数，表示能被采集的子串个数 $S$。 接下来 $S$ 行每行两个整数 $L,R$，分别表示每个可采集子串的左端点与右端点，按照左端点升序为第一关键字，右端点升序为第二关键字排序。

abcd
10 0 1 1

3
1 1
3 4
4 4

aaaa
1 1 1 1

0

aaa
1 1 1

2
1 2
2 3

aaa
1 1 2

1
1 2

共 $10$ 个测试点，每个点 $10$ 分，计 $100$ 分。  对于所有测试点，有 $N\leq 10^5$，$0 \le V_i \le 1000$。保证每个点可被采集的子串不超过 $10^5$ 个。 **样例#1解释**放在题面里了。 **样例#2解释：** 每个子串都不满足条件。 串 `a` 的排名是 $4$，重要度和都是 $1$。 串 `aa` 的排名是 $3$，重要度和都是 $2$。 串 `aaa` 的排名是 $2$，重要度和都是 $3$。 串 `aaaa` 的排名是 $1$，重要度和都是 $4$。 **样例 #3解释：** 串 `a` 的排名是 $3$，重要度和都是 $1$。 串 `aa` 的排名是 $2$，重要度和都是 $2$，共有两个串`aa`，位置分别为 $1$~$2$ 和 $2$~$3$。 串 `aaa` 的排名是 $1$，重要度和都是 $3$。 **样例 #4解释：** 可以发现，串 $2$~$3$（第二个 `aa`）不满足条件了。它的排名还是 $2$ 不变，但是重要度和为 $3$。