Problem Brief

Disaster Recovery

FULLTIMEOA

A global log describes commits applied across multiple repositories after a corrupted migration. Each valid log line begins with id <commitId> timestamp <ts> followed by zero or more file-path / opaque-identifier pairs.

Two commits belong to the same repository when they can be connected through at least one matching (filePath, opaqueIdentifier) pair. If the same connected component would force one file path to have two different opaque identifiers, the input is ambiguous.

Malformed log lines must be discarded. They do not themselves make the input ambiguous.

After all log lines are processed, answer repository queries of the form "startTimestamp endTimestamp filePath opaqueIdentifier". For each query, return the commit IDs for the matching repository, filtered to the inclusive timestamp range, sorted by increasing timestamp and then increasing commit ID. Each response line should preserve the original trailing space behavior from the prompt.

If the input is ambiguous anywhere, return a single-line result containing AMBIGUOUS INPUT!.

Function Description

Complete processRepositoryQueries.

processRepositoryQueries has the following parameters:

String[] logLines: raw log lines, one string per candidate log entry
String[] queries: raw query strings in the format "start end path opaqueId"

Returns: String[] of query responses, or ["AMBIGUOUS INPUT!"] when the logs are ambiguous.

1Example 1

Input

logLines = ["id 0 timestamp 10 foo a bar b","id 1 timestamp 20 bar b baz c","id 2 timestamp 15 qux d"], queries = ["0 30 bar b","0 12 foo a","0 30 qux d"]

Output

["0 1 ","0 ","2 "]

Explanation

Commits 0 and 1 belong to the same repository because they share bar b. Commit 2 is isolated. Each query filters the connected component by timestamp and preserves the required trailing space.

2Example 2

Input

logLines = ["id 0 timestamp 10 foo a bar b","id 1 timestamp 20 bar b baz c","id 2 timestamp 30 baz c foo x"], queries = ["0 30 foo a"]

Output

["AMBIGUOUS INPUT!"]

Explanation

The three commits would be connected through shared files, but the connected component assigns two different opaque identifiers to foo. That makes the entire input ambiguous, so queries are ignored and only AMBIGUOUS INPUT! is returned.

Constraints

Limits and guarantees your solution can rely on.

0 <= N <= 10^7 log lines and 0 <= R <= 10^5 queries.
Valid log entries are space-delimited words with unique keys per line.
The first two keys of a valid log line are always id and timestamp.
Commit IDs are unique across valid log lines.
Commit IDs and timestamps fit in non-negative 64-bit integers.
Malformed log entries should be discarded.