A good war commander must take quick decisions, and at the same time be a good strategist. One of the functions of the commander is to delegate soldiers to several strategic points, such that the enemy can be caught surprised and be defeated. There are several strategic points at the battle field, as well as several routes that connect these points.

Your field is, however, being bombarded, and these routes are not so safe as they were. Once a bomb falls at one route, such terrain becomes irregular and your crossing becomes impossible. To deal with such problem, the commander ordered a new task to some soldiers: find new routes.

The commander asked your help to calculate the shortest path between the base of operation and the strategic points. You will be informed about the initial state of the battle field, with N strategic points (being the point 1 the base of operation) and M routes. As the bombs falls over some routes, and other routes are found by the soldiers, you must update your map such that your commander can make good use of such information.

Good luck, the country depends on you.

Input

The input contains several test cases. Each test case begins with two integers, N and M (2 ≤ N ≤ 1000 and 1 ≤ M ≤ 10000), representing, respectively, the number of strategic points and the number of routes that connects two strategic points. After that, there will be M lines, each one with three integers U, V and W (1 ≤ U, V ≤ N and 1 ≤ W ≤ 100) each, representing that there is a route that connects the point U to the point V, in unique direction, with distance W.

There will be, then, an integer Q (1 ≤ Q ≤ 1000), that represents the number of consults or updates that will be done over the routes. At the next Q lines there will be a letter and a determined number of integers.

If the letter is a R, there will be two integers U and V (1 ≤ U, V ≤ N), indicating that the route that used to connect the point U to the point V was bombed.

In the case that the letter is a I, there will be three integers U, V and W (1 ≤ U, V ≤ N and 1 ≤ W ≤ 100), indicating that a new route was found, which connects the point U to the point V, with distance W.

And in the case that the letter is a P, there will be one integer V (1 ≤ V ≤ N), and you must inform to the commander what is the shortest distance between the base of operation and the strategic point V.

The input ends when N = M = 0.

Output

For each test case there will be a not defined number of output lines. When the commander order to know the shortest distance between the base of operation and a strategic point (letter P), such distance must be print in an unique line. If it is not possible to reach such strategic point, the number -1 must be printed. There must have a blank line after each test case.

Example

Input:

3 3
1 2 2
2 3 3
1 3 4
5
P 3
R 2 3
P 3
I 2 3 1
P 3

Output:

4
4
3