P4143 Collecting Ores

ZRQ successfully escaped from the collapsed cave. At last, he saw the ores he needed to study. He wants to pick some to take back and complete the task. Problem source: [Zhang_RQ](https://www.luogu.org/space/show?uid=31565)~~Oh right, it is ZRQ, yeah~~.

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.

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$.

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.

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