Give a C$++$ solution

$1.$ Disaster Recovery

Your company has been using an archaic repository management system and is switching to a modern version control system. Unfortunately, much of the repositories' states were lost in the process of upgrading! Fortunately, you have a global log of "commits" applied to each repository that can be used to reconstruct much of the commit histories.

Each log entry corresponds to a commit applied to a particular repository and consists of a globally unique nonnegative integral commit id$,$ the non$-$negative integral timestamp of the commit, and the files changed in the commit. Each of these files is described by its path and an opaque identifier that's a function of the path and repository. Two commits for different repositories may contain the same file path, but the file's opaque identifier should be distinct, and vice$-$versa. And you may assume neither a file's path nor its opaque identifier contain whitespace.

To recover the commit histories, commits need to be combined to more accurately describe the set of commits applied to each repository. Commits can be combined with other commits containing at least one matching file path and opaque identifier. For example, the log below describes two repositories, where the first and last entries describe one of those two repositories:

id $0$ timestamp $23534$ include$/$foo$.$h da$39$a$3$ include$/$bar$.$h e$615$fe id $2$ timestamp $23534$ include$/$baz$.$h $249$e$5$d

id $1$ timestamp $23606$ include$/$bar$.$h e$615$fe src$/$bar$.$cpp $89$bff$2$

The following log$,$ however, is considered ambiguous because foo. py has conflicting opaque identifiers of ac$819$f and $918$ca$,$ but the three commits could otherwise be combined based on bar. py and baz. py:

id $38024$ timestamp $74820$ foo$-$py ac$819$f bar$-$py $0$d$82$b$9$

id $49283$ timestamp $19837$ bar$-$py $0$d$82$b$9$ baz$-$py f$28$dc$2$ id $20391$ timestamp $23488$ baz.py f$28$d$2$ foo.py f$918$ca

While the investigation is ongoing to better understand how the repositories' states were lost, you would like to provide employees with a tool to query commit histories based on the logs$.$ Specifically, queries are parameterized by a start timestamp, end timestamp, file path, and opaque identifier. The response for each query is the commit id of each commit corresponding to the repository referenced by the query's file path and opaque identifier, sorted by increasing timestamp followed by increasing commit id and filtered by the start and end timestamps, inclusive. Note that repositories should be determined based on all commits, not just the commits in the start and end timestamp range.

Input

Input is provided via standard input. The first line of input consists of a single integer N representing the number of lines that follow, one per line $(0<=$ N $<=107).$ Each line is either a valid log entry, or malformed.

$$ Valid log entries consist of a line of words, delimited by a single space character.

$$ Each word does not contain any whitespace.

$$ Each two consecutive words make up a key$-$value pair and the first two keys are always $\text{'}$id$\text{'}$ followed by 'timestamp'.

$$ Keys are always unique within a line.

$$ The commit id and timestamp values are always non$-$negative $64-$bit integers. All other words are opaque strings.

$$ Commit IDs are guaranteed to be unique across lines.

Bonus: detect and discard malformed log entries that don't follow this format.

After the N log entries is another line consisting of a single integer R representing the number of queries that follow, one per line $(0<=$ R $<=105).$ Each query is a space$-$delimited sequence of start timestamp, end timestamp, file path, and opaque identifier.

Output

Output should be sent to standard output. If there are ambiguous log entries, the output should consist of a single line: AMBIGUOUS INPUT!. Recall that malformed log entries should be discarded and do not directly result in ambiguity. Otherwise, the output should consist of R lines, where each line is the space$-$delimited response to the associated query with a trailing space. As described above, each response consists of the commit ids for the repository associated with the query parameters, sorted by increasing timestamp followed by increasing commit id and filtered by the start and end timestamps, inclusive.

Regardless of whether the input is ambiguous, your program should always exit $0.$

Sample Input

$6$

id $8$ timestamp $200$ quicksort.cpp $839$ad$0$ mergesort.cpp $0$cadel bubblesort.cpp $248$ddl

id $0$ timestamp $500$ array.h $163111$ sequence.h $294$d$3$f

id $6$ timestamp $200$ mergesort.pp Ocddel bogosort. cpp $4213$ff

id $4$ timestamp $1000$ array.h $163111$ vector.h fcc$2$af

id $2$ timestamp $300$ bubblesort.cpp $248$ddl bogosort.cpp $4213$ff

id $3$ timestamp $300$ bubblesort.cpp eaf$88$a bogosort.cpp $4$f$1$laa

$4$

$010000$ quicksort.cpp $839$adO

$0500$ vector.h fec$2$af

$0100000$ no$\_$found.h empty$\_$ response

$100200$ bogosort.cpp $4213$ff

Sample Output

$682$

$0$

$68$