Disaster Recovery

After a corrupted migration, only a single global log remains, recording commits across multiple repositories. A valid log line has the format id <commitId> timestamp <ts>, followed by zero or more "file path opaque identifier" pairs, with all words separated by a single space.

A valid line must satisfy all of the following: the number of words is even and at least 4; the 1st word is id and the 3rd word is timestamp; commitId and ts are non-negative decimal integers; the keys within one line (id, timestamp, and the file path of each pair) are pairwise distinct. A line that fails any of these is a malformed line and is discarded; it neither connects any commits nor causes ambiguity.

If two valid commits contain exactly the same (file path, opaque identifier) pair, they belong to the same repository; this relation is transitive, and repositories are the resulting connected components. If the same file path appears with two different opaque identifiers within one connected component, the whole input is ambiguous.

After processing all logs, answer queries start end path opaqueId: find the repository that contains (path, opaqueId), take its commits whose timestamps lie in the closed interval [start, end], and output their ids sorted by timestamp ascending, breaking ties by commit id ascending. If the input is ambiguous, ignore all queries and output only one line AMBIGUOUS INPUT!.

输入格式

The first line contains an integer N, followed by N lines, each containing one log line (non-empty, words separated by exactly one space, no leading or trailing spaces). Then a line contains an integer R, followed by R lines, each containing a query start end path opaqueId.

0≤N≤200000, 0≤R≤100000, and the total input length does not exceed 3·10^7 bytes. Each word consists of visible ASCII characters; a word made up only of digits has no extra leading zeros and does not exceed 2^63−1. The commitId values on valid lines are distinct (ids on malformed lines may duplicate them). In every query, start and end are integers in 0..2^63−1, and (path, opaqueId) appears on at least one valid log line. If the input is not ambiguous, the total number of ids output across all queries does not exceed 2·10^6.

输出格式

If the input is ambiguous, output only one line AMBIGUOUS INPUT!. Otherwise output R lines; line i lists the commit ids for the i-th query in order, each id immediately followed by a space; output an empty line if no commit qualifies. Output is compared character by character.

样例 1

输入：

3
id 0 timestamp 10 foo a bar b
id 1 timestamp 20 bar b baz c
id 2 timestamp 15 qux d
3
0 30 bar b
0 12 foo a
0 30 qux d

输出：

0 1 
0 
2 

样例 2

输入：

3
id 0 timestamp 10 foo a bar b
id 1 timestamp 20 bar b baz c
id 2 timestamp 30 baz c foo x
1
0 30 foo a

输出：

AMBIGUOUS INPUT!

样例 3

输入：

6
id 7 timestamp 5 src/a.go v1
ID 8 timestamp 6 src/a.go v1
id 9 timestamp 5 src/a.go v1 lib v3
id 3 timestamp x lib v3
id 4 timestamp 8 lib v3 lib v4
id 5 timestamp 9 lib
3
0 9 lib v3
6 6 src/a.go v1
9 0 lib v3

输出：

7 9 

样例说明

Example 1: commits 0 and 1 share bar b and belong to the same repository; commit 2 forms a repository on its own. The first query outputs "0 1 ", the second query's interval [0,12] contains only commit 0, and the third outputs "2 ". Example 2: the three commits are connected through bar b and baz c, but foo maps to both a and x, so the input is ambiguous. Example 3: line 2 has ID as its first word, line 4 has a non-numeric timestamp, line 5 repeats the key lib, and line 6 has an odd number of words, so all of them are discarded. Commits 7 and 9 are connected because they share src/a.go v1; the second query's interval [6,6] contains no commits and the third query has start>end, so both output empty lines.