Benny is living in a big country. This country has N cities and M biderectional roads between cities. Each road is characterized by three integers - u, v and c where u and v are the cities connected by this road and c is the length of this road. There can be more than one road between two cities. There no roads connecting city to itself.
Benny has many friends. They really like to travel therefore they are not staying at home all the time. Sometimes they return to their homes or conversely leave their homes. You will be given all information about Benny's friends.
Every time when Benny gets bored she wants to visit some of her friends. She wants to find such friend that path between Benny's current city and friend's city has the minimal inconvenience.
Inconvenience of the path which consists of K edges with lengths C1, C2, ..., Ck equals to maximum number among C1, C2, ..., Ck.
You are given a graph with N cities and M biderectional roads. You have to process Q queries. Each query has on of the following types:
- + v -- means that one of Benny's friends return from the journey and is staying at city with index v.
- - v -- means that one of Benny's friends leaves his home which is located in the city with index v.
- ? v -- means that Benny wants to visit one of her friend that the path between them has the minimal inconvenience. This friend must be at home in this moment. Benny's current location is the city with index v.
For each query of type "?" output in a single line one integer - minimal inconvenience of the path to her friend or -1 if she can not reach home of any friend.
Input format
The first line contains two integers N and M denoting the number of cities and number of roads. Each of the next M lines contain three integers u, v, c, denoting the road between cities u and v with length c. The next line contains a single integer Q denoting the number of queries. The following Q lines contain descriptions of queries. Each query consists of one character denoting the type of query, space, and the index of vertex.
Output format
For each query of type "?" output in a single line one integer - minimal inconvenience of the path to her friend or -1 if she can not reach home of any friend.
Constraints
- 1 ≤ N, M, Q ≤ 105
- 1 ≤ Ci ≤ 109
- 1 ≤ N, M, Q ≤ 103 in test data worth 20% of all points