题目描述

zjh 发现这里有 N 块排成一排的矿石。

他用一个小写字母来表示每块矿石，他还发现每块矿石有一个重要度 Vi。

zjh 想采集一段连续的矿石回研究所。

他非常严格，被采集的一段矿石必须满足小写字母的字典序降序排名等于这段矿石的重要度和。

这里多个出现在不同位置的本质相同串的字典序排名相同。

比如说字母串为 aa，那么第一个 a 的排名和第二个 a 的排名相同，都是 2（第 1 是 aa）。

zjh 问你，在原串中有哪些不同的子串可以被采集？

这里子串不同定义为出现位置不同，也就是说本质相同的子串出现在不同位置都要计算一次（当然重要度和等于排名是前提）。

比如共有 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 个整数，表示 Vi

输出格式

一行一个整数，表示能被采集的子串个数 S。

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

abcd
10 0 1 1

3
1 1
3 4
4 4

数据规模与约定

N≤10^5，0≤Vi≤1000