35034번 - 생성 문자열

문제

알파벳 소문자와 대문자로 구성된 $N(\leq 26)$개의 문자열 $S_1,S_2,\dots ,S_N$이 주어진다. 각 문자열 $S_i$는 1ドル$번부터 $N$번까지의 번호가 매겨져 있으며, 알파벳 대문자 ’A’는 $S_1,ドル ’B’는 $S_2,ドル $\dots,ドル $k$번째 알파벳 대문자는 $S_k$에 대응된다.

각 문자열 $S_i$를 바탕으로 문자열 $T_i$는 다음 규칙을 $S_i$의 첫 번째 문자부터 마지막 문자까지 순서대로 적용하여 생성된다.

• 소문자인 경우: 해당 문자를 그대로 $T_i$에 추가한다.
• 대문자인 경우: 해당 대문자가 $k$번째 알파벳 대문자라면, $T_i$에 문자열 $T_k$를 추가한다.

이 때 생성된 문자열 내부에 다시 대문자가 포함되어 있다면 동일한 규칙을 적용하여 문자열을 다시 생성한다. 이 과정에서 $T_i$의 길이는 무한히 증가할 수 있다.

예를 들어 $N=2$이고 $S_1=$ ”goodB”이고 $S_2=$ ”byeAbyeB”인 경우를 고려하자.

• $S_1$의 ’B’는 $T_2$로 대체되므로 $T_1$ = ”good” + $T_2$이다.
• $S_2$의 ’A’는 $T_1$으로, ’B’는 $T_2$로 대체되므로 $T_2$ = ”bye” + $T_1$ + ”bye” + $T_2$이다.
• 이를 결합하면 $T_1$은 goodbyegoodbyeg..., $T_2$는 byegoodbyegoodb...와 같이 무한히 긴 문자열이 생성된다.

$Q$개의 순서쌍 $(x_j,L_j,R_j)$이 주어진다. 각 순서쌍에 대하여 $T_{x_j}$의 $L_j$번째 문자부터 $R_j$번째 문자까지의 부분 문자열을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 문자열의 개수 $N$와 쿼리의 개수 $Q$가 주어진다.

이어지는 $N$개의 줄 중 $i$번째 줄에는 문자열 $S_i$가 주어진다.

이어지는 $Q$개의 줄 중 $j$번째 줄에는 각 쿼리를 나타내는 세 정수 $x_j,ドル $L_j,ドル $R_j$이 공백으로 구분되어 주어진다.

출력

$Q$개의 줄에 걸쳐 답을 출력한다. 이 중 $j$번째 줄에는 $T_{x_j}$의 $L_j$번째 문자부터 $R_j$번째 문자까지, 총 $R_j-L_j+1$개의 문자를 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル\leq N\leq 26$
• 1ドル\leq Q\leq 300,円 000$
• $S_i$의 각 문자는 알파벳 소문자와, $N$번째 이내의 알파벳 대문자로만 구성된다.
• 1ドル\leq |S_i|,ドル $\sum |S_i|\leq 300,円 000$
• 모든 $S_i$의 첫 번째 문자는 알파벳 소문자이다.
• 1ドル\leq x_j\leq N$
• 1ドル \le L_j \le R_j \le 10^{18}$
• $T_{x_j}$의 길이가 유한할 경우, $R_j \le |T_{x_j}|$
• 모든 쿼리에 대해 출력해야 하는 문자열 길이의 합($\sum R_j-L_j+1$)은 300ドル,円 000$을 넘지 않는다.

노트