P17809 [ICPC 2019 Nanchang R] Dynamic Suffix Array

In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used, among others, in full-text indices, data compression algorithms and within the field of bibliometrics. Assume $S[1,n]$ is a string, let's denote $S[i,j]$ as the substring of $S$ ranging from $i$ to $j$ and denote suffix $i$ as $S[i,n]$. The suffix array $A$ of $S$ is now defined to be an array of integers providing the starting positions of suffixes of $S$ in lexicographical order. This means, an entry $A[i]$ contains the starting position of the $i$-th smallest suffix in $S$ and thus $S[A[i-1],n]

The first line of the input contains an integer $q$ ($2 \leq q \leq 1000000$), denoting the number of events. For the next $q$ lines, each line describes an event. It is guaranteed that the first event is of the first type, and the last event is of the second type.

For each event of the second type, output an integer denotes the answer in a single line.