A long time ago, in the not-so-distant LCT (land of the carrot trees), where carrots grow on trees, lived a magical carrot. In this magical land, there were cities numbered , connected with roads, with no cycles. Over the course of days, some interesting things happened to the roads:

`A x y z`

: A new road of durability is built between cities and`R x y`

: The road between cities and is destroyed by a rampaging rabbit (it is guaranteed to exist prior to the operation)`Q x y`

: The eccentric king demanded to know the of the durability of all roads on the path between cities and

It is guaranteed that there will be at most one path between any two cities at any point in time.

Can you help the people of LCT by implementing a program to simulate these events?

#### Constraints

For all subtasks, the durability of a path will be a positive integer in the range .

##### Subtask 1 [20%]

##### Subtask 2 [80%]

#### Input Specification

The first line of input will have two integers, and .

The next lines will contain three integers, , indicating there is a road of durability between cities and .

The next lines will each contain a valid query.

#### Output Specification

For each `Q`

query, print the answer to it on a new line. If the two cities are not connected, output `-1`

.

#### Sample Input 1

```
5 4
1 2 3
2 4 5
3 5 6
2 3 8
R 3 2
A 3 1 6
Q 5 4
Q 3 2
```

#### Sample Output 1

```
6
5
```

#### Sample Input 2

```
6 8
1 2 3
3 4 5
4 5 6
4 1 8
6 1 4
Q 6 5
Q 3 2
R 4 3
R 4 1
A 1 3 8
Q 3 2
Q 4 5
Q 6 1
```

#### Sample Output 2

```
10
14
11
6
4
```

## Comments

Can someone take a look at my submission and suggest how to optimize? I am fairly sure that I have the intended complexity in the editorial.

Kirito r3mark

In the case that the two cities are not connected, output -1. The problem statement has been adjusted accordingly.