Cache Query Handler

Cache records give timestamp, key, and value; for each (key,timestamp) query, return the corresponding value.

输入格式

n,q≤200000; then n lines of key timestamp value, followed by q lines of key timestamp. Times are HH:MM:SS, and value is an integer. This site adds the guarantee that (key,timestamp) is unique, removing the duplicate-key conflict the original problem left unspecified.

输出格式

Output each value in order, separated by spaces.

样例 1

输入：

2 2
a 10:00:00 7
b 10:00:00 9
b 10:00:00
a 10:00:00

输出：

9 7

样例 2

输入：

1 1
x 00:00:00 -1
x 00:00:00

输出：

-1

样例 3

输入：

2 2
a 12:30:00 4
a 12:31:00 5
a 12:31:00
a 12:30:00

输出：

5 4