Description

ZRQ finds that there are $N$ ores arranged in a line.

He uses a lowercase letter to represent each ore, and he also finds that each ore has an importance value $V_i$.

ZRQ wants to collect a consecutive segment of ores and bring them back to the lab.

He is very strict: the collected segment must satisfy that the lexicographic rank in descending order of this substring among all substrings equals the sum of importance values of this segment.

Here, multiple occurrences of substrings that are identical in content but appear at different positions share the same lexicographic rank.

For example, if the letter string is aa, then the rank of the first a and the second a is the same, both are 2 (the 1 is aa).

ZRQ asks you: which substrings in the original string can be collected?

Here, substrings are considered different if their positions of occurrence are different, that is, identical substrings appearing at different positions are all counted separately (of course, only if the sum of importance equals the rank).

For example, there are $4$ ores, the lowercase letter string is abcd, and the importance values are 10 0 1 1.

We rank all substrings in descending lexicographic order: 1:d 2:cd 3:c 4:bcd 5:bc 6:b 7:abcd 8:abc 9:ab 10:a.

Then the rank of d is $1$ (the largest), and its importance sum is $1$, so it can be collected.

The rank of cd is $2$, and its importance sum is $2$, so it can be collected.

The rank of a is $10$, and its importance sum is $10$, so it can be collected.

Other substrings do not satisfy this condition, so there are three substrings that can be collected.

Input Format

The first line contains a string of length $N$ consisting of lowercase letters, where each character represents an ore.

The second line contains $N$ integers, representing $V_i$.

Output Format

The first line contains a single integer, the number $S$ of substrings that can be collected.

Then output $S$ lines, each with two integers $L,R$, representing the left and right endpoints of each collectable substring, sorted by increasing left endpoint as the primary key and increasing right endpoint as the secondary key.

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

Hint

There are $10$ testpoints, each worth $10$ points, totaling $100$ points.

For all testpoints, $N \leq 10^5$, $0 \le V_i \le 1000$. It is guaranteed that the number of substrings that can be collected for each test is at most $10^5$.

Explanation for Sample #1 is included in the statement.

Explanation for Sample #2:

No substring satisfies the condition.

The rank of a is $4$, and the importance sums are all $1$.

The rank of aa is $3$, and the importance sums are all $2$.

The rank of aaa is $2$, and the importance sums are all $3$.

The rank of aaaa is $1$, and the importance sums are all $4$.

Explanation for Sample #3:

The rank of a is $3$, and the importance sums are all $1$.

The rank of aa is $2$, and the importance sums are all $2$. There are two substrings aa, at positions $1$~$2$ and $2$~$3$.

The rank of aaa is $1$, and the importance sums are all $3$.

Explanation for Sample #4:

We can see that the substring $2$~$3$ (the second aa) no longer satisfies the condition. Its rank is still $2$, but the importance sum is $3$.

Translated by ChatGPT 5