Poker Card Game: Winning Hand Count

In this problem, player Z and player A play a card game using piles of cards dealt from a huge deck. Each card in the deck bears a lowercase English letter. The rules of the game are as follows:

• Before the game begins, the system deals each player a pile of cards (the two piles can have different sizes). Each pile is a contiguous segment of the huge deck. That is, if the deck is given by \(a_1,a_2,\cdots,a_n\), then a player’s hand is given by \(a_l,a_{l+1},\cdots,a_r\).
• At each round the two players simultaneously reveal the top card of their piles. If the two revealed cards are different, then the player whose card has the smaller letter (in lexicographical order) wins the round.
• If the two cards are the same, both cards are moved to the bottom of their respective piles, preserving the order, and the process repeats until a winner is determined.

This procedure is equivalent to comparing the infinite periodic strings obtained by repeating the initial pile. More formally, if player Z’s hand is \(X\) and player A’s hand is \(Y\), then the game outcome is decided by comparing \(X^\infty\) with \(Y^\infty\). A well known fact is that \(X^\infty < Y^\infty\) (i.e. player Z wins) if and only if \(XY < YX\) in lexicographical order, with letters compared in the usual way and all formulas rendered in \(\LaTeX\).

In total, there are \(q\) rounds. In the \(i\)-th round, player A’s hand is given by the substring \(a_{l_i},a_{l_i+1},\cdots,a_{r_i}\) of the huge deck. Knowing this, player Z wonders: How many possible hands (i.e. contiguous substrings of the huge deck) can he receive so that he wins against player A? Two hands are considered different if they differ in length or if there exists at least one position where the letters differ.

Your task is to compute, for each game, the number of contiguous substrings from the huge deck that would lead to a win for player Z.

inputFormat

The first line contains two integers \(n\) and \(q\), where \(n\) is the length of the huge deck and \(q\) is the number of games.

The second line contains a string of length \(n\) consisting of lowercase English letters, representing the deck \(a_1a_2\cdots a_n\).

Each of the following \(q\) lines contains two integers \(l\) and \(r\) (1-indexed) defining the segment of the deck given to player A for that game.

outputFormat

For each game, output a single integer representing the number of possible winning hands for player Z.

sample

3 1
aba
1 3

2