Mountain Teleportation and Climbing

We are given a mountain represented by a string \(S\) of length \(n\) consisting of lowercase letters. For any string \(S\), we denote its length by \(|S|\) and the substring from index \(L\) to \(R\) (1-indexed) by \(S_{L\ldots R}\).

Initially, Little M is at position \(i\) and wants to reach the mountain top at position \(k\). Little B is assisting her. Before performing any moves, they must use a teleportation array located at position \(p\) by casting a spell. By doing so, Little B’s position can be set arbitrarily to some \(j\) such that:

[ j\ge i \quad \text{and} \quad S_{i\ldots j}=S_{p\ldots p+(j-i)}. ]

This teleportation costs \(n-j\). It is guaranteed that there exists at least one such \(j\).

After the teleportation, assume Little M and Little B are at positions \(i\) and \(j\) respectively. Then, they can perform any number of the following operations (each costing 1):

• Little M climbs: Set \(i=i+1\) or \(i=i-1\). If after the move \(i>j\), then update \(j=i\).
• Little B climbs: Set \(j=j+1\) or \(j=j-1\). If after the move \(i>j\), then update \(i=j\).
• Spiral Ascension: Choose indices \(l\) and \(r\) such that \(S_{l\ldots r}=S_{i\ldots j}\), and update \(i=l,\; j=r\).

After every operation, it must hold that \(1\le i,j\le n\). The goal is to achieve \(i=k\) with minimum total cost (i.e. the teleportation cost plus the cost for subsequent moves). There are multiple queries.

inputFormat

The first line contains an integer \(n\) and the string \(S\) (of length \(n\)).

The next line contains an integer \(q\), the number of queries.

Each of the following \(q\) lines contains three integers: \(i\), \(p\), and \(k\) representing the initial position of Little M, the position of the teleportation array, and the target mountain top position respectively.

outputFormat

For each query, output the minimum total cost required to have Little M reach the target position \(k\).

sample

7
abacaba
3
1 3 7
4 2 1
3 5 3

6
5
4