Mock Grading

The POSTECH multiple-choice exam has $N$ questions, and each question has 26 choices labeled with the uppercase letters A through Z. Writing the correct letters in order from question 1 to question $N$ gives the answer string $S$ of length $N$.

$M$ students took the exam and submitted answers to every question. They do not remember every answer they submitted. Student $i$ remembers $L_i$ consecutive answers, and writing them in order gives the string $T_i$.

After the exam, students compare their remembered strings $T_i$ with the published answer string $S$ to grade themselves. The letters of $S$ are read one by one from the front, and the confidence of the students rises by the following rules.

1. Every student starts with confidence 0.
2. If the last $L_i$ correct letters read so far match $T_i$ in order, the confidence of student $i$ rises by a positive integer $B_i$. In other words, the suffix of length $L_i$ of the string read so far must match $T_i$ in order.
3. While fewer than $L_i$ correct letters have been read, the confidence of student $i$ neither rises nor falls. Increases are independent of each other. So $T_i$ triggers a rise whenever the most recent $L_i$ letters match it, regardless of whether $T_i$ also appears earlier in $S$ or matches some other $T_j$.

When the confidence of any of the $M$ students reaches $A$ or more, the self-grading is considered valid. Find the number of the question after which a student first has confidence $A$ or more.

The first line contains $N$, the number of questions in this year's quiz, $M$, the number of students who took the exam, and the integer $A$. ($1 \leq N \leq 1000000$, $1 \leq M \leq 100000$, $1 \leq A \leq 10^{15}$)

The next line contains the answer string $S$ of this year's exam. $S$ consists only of uppercase letters.

Each of the next $M$ lines contains $L_i$, $B_i$, and $T_i$, separated by spaces. ($1 \leq L_i \leq N$, $1 \leq B_i \leq 10^9$) $T_i$ consists only of uppercase letters. The sum of all $L_i$ is at most 1000000. Different students may have the same $T_i$.

Print the number of the question at which the confidence of some student first reaches $A$ or more. If no student reaches $A$ or more after all $N$ answers are read, print Fail.