정렬 기계

로봇 모건이 텍스트를 정렬할 수 있다는 것은 아드리안도 알고 있지만, 모건의 효율이 어느 정도인지는 확실하지 않다. 그래서 아드리안은 모건의 효율을 시험하기로 한다.

먼저 아드리안은 모건에게 길이가 같은 텍스트 $N$개의 목록을 준다. 텍스트에는 1부터 $N$까지 번호가 붙어 있다. 각 텍스트 $S_i$는 $M$개의 문자로 이루어져 있으며, 문자 위치는 1부터 $M$까지 번호로 표시된다. $S_{ij}$는 문자열 $S_i$의 $j$번째 문자이다.

아드리안은 모건에게 $Q$개의 작업을 준다. 각 작업은 다음 조건을 만족하는 튜플 $(A, B, L, R, X)$이다.

• $1 \le A \le B \le N$
• $1 \le L \le R \le M$
• $1 \le X \le B - A + 1$

각 작업에서 모건은 다음 과정을 수행한다.

1. 원래 텍스트 목록을 복사한다. 복사본을 $T$라고 한다. 이 목록은 작업이 진행되는 동안 계속 갱신된다.
2. $A \le i \le B$ 범위에 속하지 않는 텍스트 $i$를 $T$에서 모두 제거한다.
3. $T$에 남은 모든 텍스트에서 위치 $j$가 $L \le j \le R$ 범위에 속하지 않는 문자를 모두 제거한다.
4. $T$에 남은 텍스트에 1부터 $B - A + 1$까지 번호를 다시 붙인다. 그다음 $T$에서 텍스트 $X$를 표시한다.
5. $T$를 사전순으로 정렬하고, 그 결과를 $T'$라고 한다. 이때 정렬은 안정 정렬이다. 즉, 두 텍스트가 같으면 원래의 상대 순서를 유지한다.
6. $T'$에서 표시된 텍스트의 위치를 출력한다. 사전순으로 가장 앞선 텍스트의 위치는 1이다.

아래 그림은 이 과정이 어떻게 진행되는지 보여준다.

모건이 이 작업들을 푸는 데는 많은 시간이 걸린다. 아드리안은 모건의 프로그램을 개선해서 작업을 빠르고 정확하게 풀 수 있게 해 달라고 요청한다.

길이가 $n$인 문자열 $s$가 같은 길이의 문자열 $t$보다 사전순으로 작다는 것은, 모든 $1 \le j < i$에 대해 $s_j = t_j$이고 $s_i < t_i$인 인덱스 $1 \le i \le n$이 존재한다는 뜻이다.

첫 줄에는 두 정수 $N$과 $M$ ($1 \le N, M \le 100000$; $1 \le N \times M \le 100000$)이 주어진다. 이어지는 $N$개의 줄에는 각각 길이 $M$의 소문자 문자열 $S_i$가 주어진다.

다음 줄에는 작업의 개수 $Q$ ($1 \le Q \le 100000$)가 주어진다. 이어지는 $Q$개의 줄에는 각각 다섯 개의 정수 $A$, $B$, $L$, $R$, $X$ ($1 \le A \le B \le N$; $1 \le L \le R \le M$; $1 \le X \le B - A + 1$)가 주어진다.

각 작업의 답을 한 줄에 하나씩 출력한다.