25546번 - 가채점

POSTECH의 객관식 시험은 $N$개의 문항이 주어지고 보기로 A부터 Z까지 26개의 알파벳 대문자가 주어지는 26지선다형 시험이다. 첫 번째 문항의 정답 알파벳부터 마지막 문제의 정답 알파벳까지를 나열한 것은 길이가 $N$인 정답 문자열 $S$가 된다.

시험에 참가한 $M$명의 학생들은 모든 문제의 답을 제출했다. 학생들은 자신이 제출한 모든 답을 기억하지는 못하지만, $i$번째 학생은 자신이 제출한 답 중 연속한 $L_i$개를 기억하고 이를 순서대로 나열한 것은 답 문자열 $T_i$가 된다.

시험이 끝난 뒤 학생들은 자신이 기억하는 답 문자열 $T_i$와 공개된 정답 문자열 $S$를 비교하여 가채점을 할 것이다. $S$의 문자가 첫 번째부터 하나씩 불릴 때 $M$명의 학생의 자신감은 다음과 같은 규칙으로 상승한다.

1. 모든 학생의 초기 자신감은 $0$이다.
2. 마지막으로 불린 정답 $L_i$개가 $i$번째 학생이 기억하는 $T_i$와 순서대로 모두 일치한다면 $i$번째 학생의 자신감이 양의 정수 $B_i$만큼 상승한다. 즉 지금까지 불린 정답 문자열에서 길이가 $L_i$인 접미사가 $i$번째 학생의 답 문자열 $T_i$와 순서대로 일치해야 한다.
3. $L_i$개 미만의 정답이 불렸을 때는 $i$번째 학생의 자신감의 하락과 상승이 없으며, 자신감의 상승은 서로 독립적이기 때문에 $T_i$가 $S$의 앞쪽 다른 부분과 일치하거나 다른 학생의 $T_j$가 일치하는지와 관계 없이 최근 $L_i$개가 $T_i$와 일치하기만 한다면 상승한다.

$M$명의 학생들은 자신감이 $A$ 이상이 되면 이 가채점이 유효했다고 생각하게 된다. 가채점을 몇 번째 문제까지 진행했을 때 최초로 자신감이 $A$ 이상인 학생이 나타나는지 구하여라.

첫 번째 줄에 올해 퀴즈의 문항 수 $N$과 시험을 응시한 학생 수 $M$, 정수 $A$가 주어진다. $(1 \leq N \leq 1\,000\,000, 1 \leq M \leq 100\,000, 1 \leq A \leq 10^{15})$

다음 줄에 올해 시험의 정답 문자열 $S$가 주어진다. $S$는 모두 알파벳 대문자로만 구성되어 있다.

이후 $M$개 줄에 걸쳐 각 줄에 $L_i, B_i, T_i$가 공백으로 구분되어 주어진다. $(1 \leq L_i \leq N, 1 \leq B_i \leq 10^9)$. $T_i$는 모두 알파벳 대문자로만 구성되어 있으며 모든 $L_i$의 합은 $1\,000\,000$ 이하임이 보장된다. 모든 $T_i$가 서로 다름이 보장되지 않음에 유의하여라.

최초로 $M$명의 학생들 중 자신감이 $A$ 이상이 되는 학생이 나타나는 문제 번호를 출력하여라. 만약 $N$개 답을 모두 불러도 자신감이 $A$ 이상인 학생이 나타나지 않는다면 Fail을 출력하여라.