Nervous individuals are advised not to read the terms.

Such impudence would make Cormen turn in his grave!

D.E. Knuth

At one of the "Rope Course" stations, participants face the following challenge: they must line up on a narrow bench and, without stepping off (that is, without touching the ground), rearrange themselves in reverse order.

While this contest is entertaining and intriguing, some critics find it disgraceful, claiming its concept is not original and traces back to the SRS (Summer Ritual School). In SRS-1910, it was believed that to deepen their understanding of string algorithms, students needed to gather at night and perform a dance on the grave where Dijkstra's mummy was said to rest.

The students of SRS-1910 believed that for the ritual to be effective, they had to wear tailcoats issued in previous sessions. Since the SRS was held for the $27$th time in $1910$, all students could wear one of the $26$ tailcoats from earlier years. Interestingly, over $26$ years, the colors of the tailcoats never repeated. Thus, at the start of the ritual, each SRS student wore a tailcoat of one of the $26$ unique colors.

The ritual dance proceeded as follows. All participants stood on the grave in a single line, while the leader remained on the ground to direct the dance. Occasionally, the leader would call out two numbers, $l$ and $r$, indicating the positions of certain dancers. The participants from positions $l$ to $r$ inclusive would then reverse their order, meaning the person at position $r$ would move to position $l$, the person at position (r-1) would move to position (l+1), and so forth.

Legend has it that during SRS-1910, the spirits of Knuth and Cormen observed this ritual. For their amusement, they would occasionally select positions $l$ and $r$ and determine the largest $k$ such that for every $i$ from $0$ to k-1, the colors of the tailcoats at positions l+i and r+i matched. They would then whisper this $k$ to the mummy, causing Dijkstra's mummy to turn in the grave $k$ times in frustration.

Now, in the year 2010, critics of the bench contest aim to prove that this contest is disgraceful and would not have pleased Dijkstra. To do so, they must first analyze the number of times his mummy turned during SRS-1910.

Help them determine how many times Dijkstra's mummy turned during the ritual.

Input

The first line of the input contains a string of length $n$ (1 \leq n \leq 1000000), representing the initial arrangement of the ritual participants on the grave. Each character in the string is a lowercase Latin letter, indicating the color of the tailcoat of the participant at that position.

The second line contains a single integer $m$ — the number of events during the ritual (0 \leq m \leq 10000).

Each of the next $m$ lines describes an event. Each line contains three integers $t$, $l$, and $r$, defining the event (t \in \{1, 2\}, 1 \leq l \leq r \leq n). The first integer $t$ indicates the type of event. If t = 1, the leader calls out numbers $l$ and $r$, and the participants from positions $l$ to $r$ reverse their order. If t = 2, the spirits of Knuth and Cormen select numbers $l$ and $r$ and whisper the corresponding number $k$ to the mummy.