白茶听闻他的好朋友弥明因院楼搬迁而来到了自己的校区。为了给他一个惊喜,白茶打算偷偷地送给他一份礼物。但弥明尚未告诉他具体所住的宿舍,目前白茶只知道弥明是舍长,且已知舍长名会挂在宿舍门口。所以白茶打算让星月悄(正)悄(大)咪(光)咪(明)去 DFS 整个校区的宿舍楼,直到找到为止。
校区里有 n 栋宿舍楼,每栋宿舍楼有 m 层,宿舍楼编号从 1 到 n ,楼层编号从 1 到 m ,每层楼至多有 k 间宿舍,宿舍编号从 1 到 k 递增,且已知每个舍长名字各异,且区分大小写。
输入
首先输入一行三个整数 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 |