401678: GYM100513 C Component Tree

This problem is a little bit unusual. Here you are to write a program to process queries in online mode. That means that your program will be allowed to read a query only after writing answer for the previous query. Please be sure to use the stream flushing operation after each query's output in order not to leave part of your output in some buffer. For example, in С++ you've got to use the fflush(stdout) function, in Java — call System.out.flush(), and in Pascal — flush(output).

Imagine a complex application that consists of n components (the application itself is not essential in this problem, so we omit its description). All components form a tree-like hierarchy: each component except one (let's call this special component a main component) is contained in exactly one other component (let's call it a parent component). For the sake of convenience, let's assume that the components are numbered with integers from 1 to n with the main component having the number 1.

Each component has a set of properties associated with it. Each property is given in the form "KEY=VALUE". All property keys within a single component are distinct.

You are given the component tree together with all properties. Your task is to handle several queries for finding the property of a component. Each query is given as a pair (c, key), which means that you have to find the value of the property key for the component number c.

To answer the query, you have to follow this algorithm:

1. If the value of the property is defined for the component c, report this value as an answer. Otherwise, go to step 2.
2. If the component number c is not main, continue search in the parent component (set c equal to the number of parent component) and go to the step 1. Otherwise, the value of the property is not defined and considered to be "N/A".

The first line of the input contains an integer n (1 ≤ n ≤ 3·10⁵) — the number of components. Then the input contains the descriptions of components 1, 2, ..., n.

Each description starts with a line containing two space-separated integers p_i and k_i (0 ≤ p_i ≤ n, k_i ≥ 0) — the number of parent component and the number of properties. For the first component p_i is equal to 0. Each of the following k_i lines contains a single property in the form KEY=VALUE, where both KEY and VALUE are strings of Latin letters and digits with length between 1 and 10 characters each. All keys for a given component are distinct. The keys are case-sensitive, so, for example, properties with keys "Length" and "length" are considered distinct. The values are also case-sensitive.

The next line contains an integer q (1 ≤ q ≤ 3·10⁵) — the number of queries you have to answer. Each of the following q lines contains an integer c_j (1 ≤ c_j ≤ n) and a string key_j, separated by a single space, where key_j is a string of Latin letters and digits with length between 1 and 10 characters. Note that for each query, starting from the second, you will be able to read it only when you print the answer for the previous query and make a flush operation.

It is guaranteed that the total number of properties does not exceed 3·10⁵.

For each query, print a line with the value of the required property. You should make a flush operation after each line.

4
0 2
enabled=true
foreground=white
1 2
enabled=false
fontSize=12
2 3
enabled=true
foreground=black
caption=OK
2 1
fontSize=10
5
3 enabled
4 enabled
3 fontSize
4 foreground
2 caption

true
false
12
white
N/A

1
0 2
width=300
height=500
2
1 width
1 Width

300
N/A