Get Query Answers

A cache entry contains timestamp, key and an integer value; each query gives key and timestamp and returns the value of that exact entry, not the version with the nearest time. Keys do not repeat at the same time, and every query is guaranteed to hit.

输入格式

The first line contains n q, followed by n lines of timestamp key value, then q lines of key timestamp. 1≤n,q≤100000, 1≤value≤10^8; times are 8-character hh:mm:ss (hours 00..23, minutes and seconds 00..59); keys consist of lowercase letters and digits. On this site keys are 1..64 characters.

输出格式

Output q lines of integers in query order.

样例 1

输入：

2 2
01:34:05 abc 352
20:34:20 a1 490
a1 20:34:20
abc 01:34:05

输出：

490
352

样例 2

输入：

2 1
00:00:00 x 1
00:00:01 x 2
x 00:00:00

输出：

1

样例 3

输入：

2 2
12:00:00 a 8
12:00:00 b 9
b 12:00:00
a 12:00:00

输出：

9
8

样例说明

The examples give 490 and 352; 1; and 9 and 8 respectively.