猪猪宝典

时间限制:$1s$

空间限制:$512MB$

题目描述

$piggy$有一本猪猪宝典。猪猪宝典由$n$个单词组成，每个单词长度不超过$m$。有一天，$piggy$的偶像$kiku$知道了猪猪宝典，便想试探一下$piggy$，她提出了$q$个问题，第$i$个问题给出一个单词$s_i$，每个单词长度也不超过$m$。她希望$piggy$告诉她，猪猪宝典里有没有这个单词，如果有的话，输出$19940618$，否则的话输出最大逼近度。

其中，提问的单词$s_i$和猪猪宝典中的单词$c_j$的逼近度的定义度为下，$max$$($提问的单词$s_i$和猪猪宝典中的单词$c_j$的共同前缀长度，提问的单词$s_i$和猪猪宝典中的单词$c_j$的共同后缀长度$)$

输入描述

第一行三个整数n、m、q
随后n行，每行一个字符串表示猪猪宝典中的单词
随后q行，每行一个字符串表示提问的单词
保证都为小写字符

输出描述

共q行，每行一个整数，表示提问答案

输入样例

3 3 4
ab
cb
abc
ab
bc
cba
ba

输出样例

19940618
2
2
0

数据范围

$20pts:$ $n \leq 20,q \leq 20$

$50pts:$$n \leq 2000,q \leq 2000$

$100pts:$$n \leq 200000,q\leq 200000$

所有数据均保证$m \leq 10$，但不保证词典所有单词均不相同