Description
After figuring out the correct map, Procat still doesn't have any idea about the destination of the trip. However, he has decided to visit some restaurants on the way, so that he can bring some food back to his best friend, Jason.
Procat wants to visit these restaurants one by one in a specific order. However, he is not sure if there is a route in the map that meets his requirement. Help Procat to check if there is a route on the map that visits all the restaurants consecutively in the order he wants. Since Procat go cycling everyday, he wants to query the route for multiple times, with different restaurants to visit. You should help him to check the route for each query.
Procat will give you the map in a special format he used in "Same Map" (You should be familiar with it if you have solved the problem yourself). The format is described by the following EBNF:
TREE ::= INT '(' TREE ')' '(' TREE ')'
| NIL
The tree in the sample testcase is shown in the following figure.
- For the first query, Procat wants to visit the restaurants 1→3→7. However, there is no route that visits all the restaurants consecutively in the order Procat wants.
- For the second query, Procat wants to visit the restaurants 7→3→1. There is a route that meets Procat's requirement, which is highlighted in blue.
- For the third query, Procat wants to visit the restaurants 1→5. Note that the route could start from any vertex in the map, not only from the root.
Input
- The first line contains an integer $n$, the number of vertices in a map.
- The second line contains a string $X$, representing the map in the EBNF format.
- The third line contains an integer $q$, the number of queries Procat wants to make.
- Each of the following $q$ lines contains the following:
- An integer $m$, the number of restaurants Procat wants to visit.
- $m$ integers, representing the "name" of the restaurants.
$n$
$X$
$q$
$m_1 \quad r_{1,1} \quad r_{1,2} \quad \ldots \quad r_{1,m_1}$
$\enspace \vdots$
$m_q \quad r_{q,1} \quad r_{q,2} \quad \ldots \quad r_{q,m_q}$
Constraints
- $1 \leq N \leq 10^5$
- length of $X$ and $Y$ won't exceed $10^6$ characters
- $X$ and $Y$ only contains characters
(,)and digits. - $1 \leq m_i \leq 100$
- $1 \leq q \leq 500$
Output
For each query, print YES if there is a route that visits all the restaurants consecutively in the order Procat wants. Otherwise, print NO. You should print a newline character after each query.