Gnomes of Might and Magic

Description:

Input:

The first line contains two integers n and m (3 ≤ m ≤ n ≤ 100000) — the number of castles in the kingdom, and the number of castles on the Good Path, respectively.

The second line contains m integers, which are numbers of Good Path castles (the castles are numbered from 1 to n) in the order of occurrence on the Path, starting with some castle. All Good Path castles are different.

Each of the following m lines describes an Evil Shortcut. First a line contains an integer k_i (3 ≤ k_i ≤ 100000) — the number of castles on the corresponding Evil Shortcut (with the two castles which are on the Good Path), followed by a k_i integers — number of castles in the order of occurrence in the given Shortcut. All castles in one Evil Shortcut are different. It is guaranteed that the first and the last castles from the Shortcut are on the Good Path and the first castles in the Evil Shortcuts form the Good Path and are presented in the same order in which the Path was represented on the second line.

The next line contains an integer q (1 ≤ q ≤ 100000) — the number of events in the life of the kingdom. Each of the following q lines describes a single event. An event is described by the symbol c_j and two numbers or castles s_j and t_j (the character and numbers of castles are separated by a single space). If the character of c_j is equal to "+" (a plus), it means that a very bad gnome (probably not the first one) has appeared on the road between castles s_j and t_j. If c_j equals "?" (a question), then Vasya sent a Mission of Death from castle s_j to castle t_j. It is guaranteed that for each request "+", the road between castles s_j and t_j exists. The events are given in chronological order, starting with the earliest one. Initially there are no very bad gnomes on the roads.

All numbers in all lines are separated by single spaces. It is guaranteed that all the given Evil Shortcuts and Good Path fit in the limitations given in the problem statement.

Output:

For each query "?" print a single number on a single line — the number of very bad gnomes destroyed by the corresponding Mission of Death. Print the answers to queries in the chronological order.

Sample Input:

6 3
1 2 3
3 1 4 2
3 2 5 3
3 3 6 1
10
+ 1 2
+ 4 2
+ 1 3
+ 2 3
? 1 2
+ 2 5
? 1 2
? 1 2
+ 1 2
? 1 2

Sample Output:

0
1
0
1

Note:

In the example after the first four requests there is only one path from castle 1 to castle 2, which does not contain roads with very bad gnomes: 1 6 3 5 2.

After a gnome stood on the road (2, 5), the next Mission of Death moves along path 1 2, and destroys the gnome, who was on the road (1, 2). The next Mission of Death follows the same path which is already free of gnomes.

After yet another gnome stood on the road (1, 2), the next Mission of Death goes on the path 1 2, and kills the gnome.