CF175F.Gnomes of Might and Magic

Vasya plays a popular game the Gnomes of Might and Magic.

In this game Vasya manages the kingdom of gnomes, consisting of several castles, connected by bidirectional roads. The kingdom road network has a special form. The kingdom has m main castles _a_1, _a_2, ..., a__m, which form the Good Path. This path consists of roads between the castles a__i, a__i + 1 (1 ≤ i < m) as well as the road between a__m and _a_1. There are no other roads between the castles of the Good Path.

In addition, for each pair of neighboring Good Path castles u and v there is exactly one Evil Shortcut — a path that goes along the roads leading from the first castle (u) to the second one (v) and not having any common vertexes with the Good Path except for the vertexes u and v. It is known that there are no other roads and castles in the kingdom there, that is, every road and every castle lies either on the Good Path or the Evil Shortcut (castles can lie in both of them). In addition, no two Evil Shortcuts have any common castles, different than the castles of the Good Path.

At the beginning of each week in the kingdom appears one very bad gnome who stands on one of the roads of the kingdom, and begins to rob the corovans going through this road. One road may accumulate multiple very bad gnomes. Vasya cares about his corovans, so sometimes he sends the Mission of Death from one castle to another.

Let's suggest that the Mission of Death should get from castle s to castle t. Then it will move from castle s to castle t, destroying all very bad gnomes, which are on the roads of the Mission's path. Vasya is so tough that his Mission of Death can destroy any number of gnomes on its way. However, Vasya is very kind, so he always chooses such path between castles s and t, following which he will destroy the smallest number of gnomes. If there are multiple such paths, then Vasya chooses the path that contains the smallest number of roads among them. If there are multiple such paths still, Vasya chooses the lexicographically minimal one among them.

Help Vasya to simulate the life of the kingdom in the Gnomes of Might and Magic game.

A path is a sequence of castles, such that each pair of the neighboring castles on the path is connected by a road. Also, path _x_1, _x_2, ... , x__p is lexicographically less than path _y_1, _y_2, ... , y__q, if either p < q and _x_1 = _y_1, _x_2 = _y_2, ... , x__p = y__p, or exists such number r (r < p, r < q), that _x_1 = _y_1, _x_2 = _y_2, ... , x__r = y__r and x__r + 1 < y__r + 1.

瓦西娅正在玩一款热门游戏《力量与魔法地精》。

在这款游戏中，瓦西娅管理着一个由若干城堡组成的地精王国，这些城堡通过双向道路相互连接。王国的道路网络具有特殊结构。王国共有 $m$ 座主城堡 $a_1,\,a_2,\,\dots,\,a_m$，它们构成一条“善之路”（Good Path）。该路径包含所有相邻主城堡 $a_i$ 与 $a_{i+1}$（其中 $1\le i<m$）之间的道路，以及 $a_m$ 与 $a_1$ 之间的道路。善之路的主城堡之间不存在其他道路。

此外，对每一对相邻的善之路主城堡 $u$ 和 $v$，恰好存在一条“恶之捷径”（Evil Shortcut）——即一条从第一座城堡 $u$ 出发、通往第二座城堡 $v$ 的路径，该路径所经由的所有道路均不与善之路共享除端点 $u$ 和 $v$ 外的任何顶点。已知王国中不存在其他道路和城堡，即每条道路、每座城堡均位于善之路或某条恶之捷径上（城堡可同时属于善之路与某条恶之捷径）。此外，任意两条恶之捷径除善之路的主城堡外，不共享任何其他城堡。

每周初，王国中会出现一名极其邪恶的地精，它出现在王国某条道路上，并开始抢劫途经该道路的商队。同一条道路可能聚集多名极其邪恶的地精。瓦西娅关心他的商队，因此有时会从一座城堡向另一座城堡派出“死亡任务”（Mission of Death）。

假设“死亡任务”需从城堡 $s$ 前往城堡 $t$，则它将沿某条从 $s$ 到 $t$ 的路径行进，并消灭该路径上所有道路上的极其邪恶的地精。瓦西娅实力强大，其“死亡任务”可在行进途中消灭任意数量的地精。然而，瓦西娅心地善良，因此他总会选择一条从 $s$ 到 $t$ 的路径，使得被消灭的地精总数最少。若存在多条满足该条件的路径，则从中选择边数最少的一条；若仍存在多条，则选择字典序最小的一条。

请帮助瓦西娅模拟《力量与魔法地精》游戏中王国的运行过程。

路径是指一个城堡序列，其中序列中每一对相邻城堡均由一条道路连接。此外，路径 $x_1,\,x_2,\,\dots,\,x_p$ 在字典序上小于路径 $y_1,\,y_2,\,\dots,\,y_q$，当且仅当以下任一条件成立：

• $p < q$，且 $x_1 = y_1,\,x_2 = y_2,\,\dots,\,x_p = y_p$；
• 或存在某个整数 $r$（满足 $r < p$ 且 $r < q$），使得 $x_1 = y_1,\,x_2 = y_2,\,\dots,\,x_r = y_r$，且 $x_{r+1} < y_{r+1}$。

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.

第一行包含两个整数 $n$ 和 $m$（$3 \leq m \leq n \leq 100000$）—— 分别表示王国中城堡的总数，以及“善之路”（Good Path）上城堡的数量。

第二行包含 $m$ 个整数，表示“善之路”上的城堡编号（城堡编号从 $1$ 到 $n$），按其在路径上出现的顺序给出，起始点为某一座城堡。所有“善之路”上的城堡互不相同。

接下来的 $m$ 行每行描述一条“恶之捷径”（Evil Shortcut）。每行首先是一个整数 $k_i$（$3 \leq k_i \leq 100000$）—— 表示该条“恶之捷径”所经过的城堡数量（包括两端位于“善之路”上的两座城堡），随后是 $k_i$ 个整数—— 表示该捷径上城堡的编号，按其在该捷径中出现的顺序给出。同一条“恶之捷径”上的所有城堡互不相同。保证每条“恶之捷径”的首尾城堡均位于“善之路”上，且各条“恶之捷径”的首尾城堡恰好构成“善之路”，并以与第二行中给出的相同顺序排列。

下一行包含一个整数 $q$（$1 \leq q \leq 100000$）—— 表示王国历史中发生的事件总数。接下来的 $q$ 行每行描述一个事件。每个事件由一个字符 $c_j$ 和两个数字（即城堡编号）$s_j$、$t_j$ 描述（字符与数字之间、数字之间均以单个空格分隔）。若字符 $c_j$ 为 "+"（加号），表示一只极其邪恶的哥布林（可能并非第一只）出现在了城堡 $s_j$ 与 $t_j$ 之间的道路上；若 $c_j$ 为 "?"（问号），则瓦夏（Vasya）从城堡 $s_j$ 向城堡 $t_j$ 派出了一支“死亡任务”（Mission of Death）。保证对于每个 "+" 类型的请求，城堡 $s_j$ 与 $t_j$ 之间确实存在一条道路。所有事件按时间顺序给出，最早发生的事件排在最前面。初始时，所有道路上均无极其邪恶的哥布林。

所有行中的数字均以单个空格分隔。保证所有给定的“恶之捷径”和“善之路”均满足题目陈述中给出的限制条件。

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.

对于每个查询 “?”，在单独一行输出一个数字——即对应“死亡任务”所消灭的极坏小矮人的数量。请按时间顺序输出各查询的答案。

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.

在前四次请求之后的示例中，城堡 1 到城堡 2 之间仅存在一条不经过“非常坏的侏儒”所在道路的路径：1 6 3 5 2。

当一名侏儒站在道路 (2, 5) 上后，下一次“死亡任务”将沿路径 1 2 行进，并消灭位于道路 (1, 2) 上的侏儒。随后的“死亡任务”将沿同一条已清除所有侏儒的路径行进。

当又一名侏儒站在道路 (1, 2) 上后，下一次“死亡任务”将沿路径 1 2 行进，并杀死该侏儒。