Books

Time Limit : 1 sec, Memory Limit : 131072 KB

B : Books / 本

Problem

大学生のいづあ君はかなりの読書家である。面白そうだと思った本は迷わず買うため、蔵書が増えすぎて管理できなくなっているのが悩みである。そこでいづあ君は、持っている本の中から目的の本を検索するシステムを作ることにした。

全ての本は次の 3 つの属性を持つ。

  • title : 本のタイトルを表す文字列である。
  • author : 本の著者を表す文字列である。
  • date : 本の出版日を表す 2014/07/07 のような形式をした文字列である。

検索のクエリは次のような形式で与えられる。

Q_title Q_author Q_date_from Q_date_to

  • Q_title : タイトルに文字列 Q_title を含む本がヒットする。
  • Q_author : 著者名に文字列 Q_author を含む本がヒットする。
  • Q_date_from : 出版日が Q_date_from と同じかそれより後である本がヒットする。
  • Q_date_to : 出版日が Q_date_to と同じかそれより前である本がヒットする。

ただし、クエリに * (アスタリスク)が指定された場合は任意の文字列にヒットする。ある本がヒットするかの判定は上記 4 つの論理積で行われる。つまり、 1 つ以上ヒットしていない属性がある場合はその本はヒットしていないものとする。(「ヒットする」とは本が検索クエリに合致することを意味する。)

いづあ君の仕事は与えられたクエリを順に処理するプログラムを書くことである。

Input

入力は次の形式で与えられる。

N
book 1
...
book N
Q
query 1
...
query Q

N はいづあ君が持っている本の数であり、続く N 行にはそれぞれの本に関する情報が続く。本に関する情報は次のような形式である。

title author date

Q は検索クエリの数であり、続く Q 行にクエリが続く。検索のクエリは次のような形式で与えられる。

Q_title Q_author Q_date_from Q_date_to

Constraints

  • N, Q は整数である。
  • 1 ≦ N ≦ 100
  • 1 ≦ Q ≦ 100
  • タイトルが同じ本は含まれない。
  • 本のタイトル、著者、及びそれらに対するクエリの文字列の長さは 50 文字以下であり、含まれる文字はアルファベットの大文字と小文字のみである。大文字と小文字は区別される('a'と'A'は違う文字とみなす)。ただしクエリは*一文字のこともある。
  • 本の出版日及びそれに対するクエリは 2014/07/31 のような形式で表され、西暦年 (4桁)/月(2桁)/日(2桁) という意味である。この例の場合は 2014 年 7 月 31 日を表す。
  • 日付は 1970 年 1 月 1 日から 2037 年 12 月 31 日の範囲内である。
  • 15 月 40 日のような無効な日付は入力されない。

Output

各クエリに対して、ヒットする本のタイトルを答えよ。 2 冊以上ヒットする場合は、1 行に 1 冊ずつ、入力された順番に全てのタイトルを出力せよ。 1 冊もヒットしない場合は 1 行も出力してはならない。クエリとクエリの間には空行を挟むこと。

Samples

Sample Input 1

6
antbook iwiWataKitamasa 2012/01/28
hogebook foo 2000/01/01
hugabook bar 2000/01/01
cheeterbook chokudai 2012/09/29
aojbook YutakaWatanabe 2014/06/28
piyobook buz 2000/01/01
4
a * * *
* chokudai * *
* Chokudai * *
* * 2014/01/01 2014/12/31

Sample Output 1

antbook
hugabook
aojbook

cheeterbook


aojbook

3 番目のクエリは、一見 2 番目のクエリと同じように見えるが、先頭の文字が大文字となっており、そのような名前のちょくだいさんは著者名として存在しないため、 1 行も出力してはならない。


Source: Aizu Competitive Programming Camp 2014 Day3 , Japan, 2014-09-25