Little H encountered a problem while studying "Sets and Graph Theory" and, after thinking about it for a long time, was still unable to solve it well. He has come to you for help. Given a weighted undirected graph with $n$ vertices and $m$ edges (where each undirected edge has a weight), there are 3 sets: A, B, and C. Initially, all vertices in the undirected graph belong to set A. There are 9 types of operations:
MoveA x: Remove vertex $x$ from its current set and add it to set A.MoveB x: Remove vertex $x$ from its current set and add it to set B.MoveC x: Remove vertex $x$ from its current set and add it to set C.AskAA: Query the minimum weight among all edges where both endpoints belong to set A.AskAB: Query the minimum weight among all edges where one endpoint belongs to set A and the other belongs to set B.AskAC: Query the minimum weight among all edges where one endpoint belongs to set A and the other belongs to set C.AskBB: Query the minimum weight among all edges where both endpoints belong to set B.AskBC: Query the minimum weight among all edges where one endpoint belongs to set B and the other belongs to set C.AskCC: Query the minimum weight among all edges where both endpoints belong to set C.
Can you help him solve this problem?
Input
The first line contains two positive integers $n$ and $m$. From the 2nd line to the $m+1$-th line, each line contains three positive integers $u$, $v$, and $w$, representing an undirected edge between vertices $u$ and $v$ ($u \neq v$) with weight $w$ ($w \le 10^9$). The $m+2$-th line contains a positive integer $q$, representing the number of queries. From the $m+3$-th line to the $m+q+2$-th line, each line contains one of the 9 operations described above.
Output
For all Ask operations, output the minimum weight. If no such edge exists, output "No Found!".
Examples
Input 1
4 3 1 2 1 2 3 2 3 1 3 5 AskAA AskAB MoveB 2 AskAA AskAB
Output 1
1 No Found! 3 1
Constraints
- For 20% of the data: $n \le 50, m \le 2500, q \le 2500$.
- For another 30% of the data: $n \le 100, m \le 10000, q \le 20000$.
- For the remaining 50% of the data: $n \le 100000, m \le 500000, q \le 100000$. Additionally, for any two vertices in the undirected graph, at most 3 edge-disjoint paths can be found between them.