가채점

POSTECH의 객관식 시험은 26지선다형이며 문항은 $N$개다. 보기는 A부터 Z까지 26개의 알파벳 대문자다. 첫 번째 문항부터 마지막 문항까지의 정답 알파벳을 차례로 나열한 문자열이 길이 $N$의 정답 문자열 $S$다.

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

시험이 끝난 뒤 학생들은 기억하는 답 문자열 $T_i$와 공개된 정답 문자열 $S$를 비교해 가채점을 한다. $S$의 문자를 앞에서부터 하나씩 불러 나갈 때, 학생들의 자신감은 다음 규칙에 따라 오른다.

1. 모든 학생의 초기 자신감은 $0$이다.
2. 지금까지 불린 정답 문자열의 길이 $L_i$인 접미사가 $T_i$와 순서대로 일치하면, $i$번째 학생의 자신감이 양의 정수 $B_i$만큼 오른다.
3. $L_i$개 미만의 정답이 불렸을 때는 $i$번째 학생의 자신감이 오르지도 내리지도 않는다. 자신감의 상승은 서로 독립적이다. 따라서 $T_i$가 $S$의 앞부분 다른 곳과 일치하는지, 다른 학생의 $T_j$와 일치하는지와 관계없이, 최근 $L_i$개가 $T_i$와 일치하기만 하면 오른다.

$M$명의 학생 중 누구든 자신감이 $A$ 이상이 되면 이 가채점이 유효했다고 본다. 가채점을 몇 번째 문항까지 진행했을 때 처음으로 자신감이 $A$ 이상인 학생이 나타나는지 구하라.

첫 번째 줄에 올해 퀴즈의 문항 수 $N$, 시험을 응시한 학생 수 $M$, 정수 $A$가 주어진다. ($1 \leq N \leq 1000000$, $1 \leq M \leq 100000$, $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$의 합은 1000000 이하임이 보장된다. 서로 다른 학생의 $T_i$가 같을 수도 있다.

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