题目背景

在帆之大陆里，这里的人们掌握着一种魔法,但是释放魔法需要咒语,每个人的魔法威力不是一成不变的,具体来说,一段咒语与人体的契合度越高,那么这段咒语所带来的魔法威力越强,因此,大陆上的每个人都在竭尽所能找到契合自身的咒语,冒险家$red$也不例外,从小他感应到与他契合度最高的咒语由$k$个小写字母组成。

现在$red$已经找到了$n$个长度为$k$的字符串,并且收集到了$q$条信息,他能感应到与自身相契合的咒语就藏在这$n$个字符串里,聪明的$red$凭借自身感应从$q$条信息里推断出找到咒语的方法。

在这$q$条信息里,每条信息包含$l,r$两个数,意味着$red$最终要找到的咒语里的第$l$到第$r$个位置的字符会获得一点能量值,$red$会将其记做闪耀点。最终这$q$条信息会为咒语的每个位置$i$带来一个总闪耀点,这里记做$tol_i$,意味着$red$要找的咒语中第$i$个字符是第$tol_i\%n$个字符串里的第$i$个字符。

形式化来说,每个位置会有一个总闪耀点$tol_i$,最终你要找的咒语是由$s_{tol_i\% n,i}$组成,其中$i \left(1 \le i \le k \right)$

题目描述

我们将给定你$n\left(1 \le n \le 10\right)$个长度为$k \left(1 \le k \le 2\times10^5\right)$的字符串,记为$s_0,s_1,....s_{k-1}$,接下来将会给定你$q \left(1 \le q \le 2\times10^5\right)$个区间$l,r$,该区间内的所有点都将获得$1$点闪耀点,你需要输出满足题目要求的一段字符串。

输入格式

第一行输入三个数$n,k,q$,分别表示给定你的$n$个字符串,字符串长度为$k$,给定你的信息数为$q$

第$2$行到第$n+1$行,每行包含$k$个字符

接下来$q$行每行包含$l,r \left(l \le r \le k\right)$两个数

输出格式

输出一个长度为k的字符串表示冒险家$red$最后要找到的咒语

输入输出样例

输入 #1

3 4 3
pvwj
crbi
shht
3 4
1 2
1 2

输出 #1

shbi

解释 #1

第一条信息$l=3,r=4$,此时第三个位置和第四个位置闪耀点$tol_3=1,tol_4=1$

同理,最后我们得出每个点的闪耀值为$tol_1=2,tol_2=2,tol_3=1,tol_4=1$

所以答案为$s_{2,1}s_{2,2}s_{1,3}s_{1,4}$即$shbi$