Background

CTT2021 D3T3

Problem Description

Little $Z$ and Little $A$ are playing a poker card comparison game.

The rules of their game are as follows:

• Before the game starts, the system deals a pile of hand cards to Little $Z$ and a pile of hand cards to Little $A$ (the numbers of cards in the two piles may be different). Each card has a lowercase letter written on it.

• In each round of the game, Little $Z$ and Little $A$ simultaneously flip the first card on the top of their piles. If the two flipped cards are different, then the player whose card corresponds to the smaller lowercase letter wins. If the two flipped cards are the same, they put the flipped cards into the bottom of their piles and continue the game until one side wins.

In fact, the system deals cards from a huge deck. Specifically, suppose the deck has $n$ cards, which are $a_1,a_2,\cdots,a_n$. Then the system randomly selects cards from the $l$-th card to the $r$-th card to deal to a player. In other words, from the top of the pile to the bottom of the pile, the cards are $a_l,a_{l+1},\cdots,a_r$.

Now Little $Z$ and Little $A$ will play a total of $q$ games. Little $Z$ learns in some way that, in the $i$-th game, the cards dealt to Little $A$ are $a_{l_i},a_{l_i+1},\cdots,a_{r_i}$. Little $Z$ wants to know how many possible hand card piles he could have that would allow him to beat Little $A$. Two hand card piles are considered different if and only if the numbers of cards in the two piles are different, or there exists a position $d$ such that the cards at distance $d$ from the top of the piles are different.

Input Format

The first line contains a string $a$ consisting only of lowercase letters.

The second line contains a positive integer $q$ and an integer $type$, where $type$ indicates the data type.

The next $q$ lines each contain two integers $l_i$ and $r_i$ on line $i$.

Output Format

Output $q$ lines. Each line contains an integer indicating how many possible hand card piles Little $Z$ could have that would allow him to beat Little $A$.

abbab
5 0
1 3
2 4
3 5
1 4
2 5

4
7
6
2
8

Hint

For all testdata, it holds that $1\le l_i\le r_i\le |a| \le 5\times 10^5$, $1\le q \le 5\times 10^5$.

The meaning of data type $type$ is as follows:

• $type=0$: The data has no special restrictions.

• $type=1$: It is guaranteed that $\exists 1\le l'\le r'\le |a|$, $a_{l_i,r_i}+a_{l_i,r_i}=a_{l',r'}$.

• $type=2$: It is guaranteed that $\forall r'-l'=r_i-l_i+1$, if $a_{l',r'-1}=a_{l_i,r_i}$, then it must hold that $a_{r'}\neq a_{l_i}$.

• $type=3$: It is guaranteed that $\sum r_i-l_i \le 10^5$.

Here $a_{l,r}$ denotes the string $a_la_{l+1}\cdots a_r$. The result of concatenating two strings $a+b$ is the string obtained by appending $b$ after $a$ in order.

Translated by ChatGPT 5