1694. 星月寻人(20分)

白茶听闻他的好朋友弥明因院楼搬迁而来到了自己的校区。为了给他一个惊喜,白茶打算偷偷地送给他一份礼物。但弥明尚未告诉他具体所住的宿舍,目前白茶只知道弥明是舍长,且已知舍长名会挂在宿舍门口。所以白茶打算让星月悄(正)悄(大)咪(光)咪(明)去 DFS 整个校区的宿舍楼,直到找到为止。

校区里有 n 栋宿舍楼,每栋宿舍楼有 m 层,宿舍楼编号从 1n ,楼层编号从 1m ,每层楼至多有 k 间宿舍,宿舍编号从 1k 递增,且已知每个舍长名字各异,且区分大小写。

输入

首先输入一行三个整数 n,m,k(1\le n,m,k\le40)

接下来输入 n\times m 行,每行首先输入三个整数 a_i,b_i,c_i(1\le a_i\le n,1\le b_i\le m,1\le c_i\le k) ,代表在第 a_i 栋宿舍楼第 b_i 楼层有 c_i 间宿舍。然后在同一行内输入 c_i 个只含大小写英文字母、数字和下划线且长度不超过 20 的非空字符串,第 j 个字符串 s_j 代表编号为 j 的宿舍的舍长名字为 s_j

接着输入一行一个整数 q(q\le 10) ,代表询问的个数

接下来输入 q 行,每行输入一个只含大小写英文字母、数字和下划线且长度不超过 20 的非空字符串 p ,代表查询的舍长名

输出

对于每个询问,若舍长名存在,输出三个整数分别代表他/她所在的宿舍楼编号、楼层编号和宿舍编号。若不存在,输出 not found

样例

标准输入 复制文本
3 6 4
1 1 3 bai_cha xing_yue dakta
1 2 2 he_feng Hyper_Chordfish
1 3 1 guo_dong
1 4 2 if_1178 mi_ming
1 5 3 jin_le sang_ze bai_fu
1 6 4 cst7 Pop_Slime yun_yan wumeibanfa
2 1 1 m1saka
2 2 1 linear_algebra
2 3 3 public protected private
2 4 1 Python
2 5 2 dayuanx HK_SHAO
2 6 4 Shuvi_Doura qaq hazy_lazy_doll3 QAQ
3 1 1 ljlnb
3 2 2 discrete_mathematics advanced_mathematics
3 3 1 bobby285271
3 4 4 noname0 asirpa Thorfinn_Karlsefni nanachi
3 5 1 Emanon
3 6 3 LiZiMing lr580 lr581
5
LiZiMing
mi_ming
QAQ
Bai_cha
lr581
标准输出 复制文本
3 6 1
1 4 2
2 6 4
not found
3 6 3
标准输入 复制文本
2 3 2
2 1 2 compile_elegantly time_limit_enough
1 3 2 AK CE
1 1 1 tian_jiang
2 2 2 wonderful_answer run_excellently
2 3 2 TLE MLE
1 2 2 WA RE
6
WA
RE
TLE
MLE
CE
AC
标准输出 复制文本
1 2 1
1 2 2
2 3 1
2 3 2
1 3 2
not found
登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 313
通过 151