采集矿石

题目背景

**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$,分别表示每个可采集子串的左端点与右端点,按照左端点升序为第一关键字,右端点升序为第二关键字排序。

输入输出样例

输入样例 #1

abcd
10 0 1 1

输出样例 #1

3
1 1
3 4
4 4

输入样例 #2

aaaa
1 1 1 1

输出样例 #2

0

输入样例 #3

aaa
1 1 1

输出样例 #3

2
1 2
2 3

输入样例 #4

aaa
1 1 2

输出样例 #4

1
1 2

说明

共 $10$ 个测试点,每个点 $10$ 分,计 $100$ 分。 ![pcg6nP.png](https://s1.ax1x.com/2018/01/19/pcg6nP.png) 对于所有测试点,有 $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$。