Asset Lineage Finder

In this problem, you are given a series of operations that describe asset acquisitions and asset transformations. An acquisition operation is formatted as A user asset, which indicates that a particular user acquired an asset identified by asset. A transformation operation is formatted as T newAsset ignored parent1 parent2 ...; the second number is ignored, and the remaining numbers represent the parent assets.

For a given queried asset, you must determine its earliest acquired ancestor by repeatedly following the transformation chain. At each step, if a transformation exists for the current asset, replace it with the minimum parent (using natural integer order). Continue this process until no further transformation is present or a cycle is detected. Finally, output the asset id of the ancestor along with the user who originally acquired it.

Input is given via standard input and output should be printed to standard output.

inputFormat

The input begins with an integer N representing the number of operations. The following N lines each contain an operation in one of the two formats:

• Acquisition: A user asset • Transformation: T newAsset ignored parent1 parent2 ...

After these, a line with an integer Q is given, representing the number of queries, followed by Q lines each containing one query asset id.

outputFormat

For each query, print a line containing two integers separated by a space: the id of the earliest acquired ancestor asset and the user who originally acquired that asset.## sample

5
A 1 10
A 2 20
T 30 5 10 20
A 3 40
T 50 6 40 30
2
30
50

10 1
10 1