Bajtazar works in logistics and distributes construction materials from a warehouse in the capital of Bajtocja to shops in numerous cities. There are $n$ cities in Bajtocja (numbered from $1$ to $n$) connected by a connected network of $n-1$ roads. There is a gas station in the middle of every road.

Bajtazar's workday always looks like this: he leaves the capital (city number $1$), travels by the shortest possible route to a certain city $x$, and then returns along the same route.

Bitek, Bajtazar's son, is a fan of the "Biciaki Gang" – plush toys sold at the stations. In total, there are $m$ types of Biciaki available (for simplicity, we will number them with integers from $1$ to $m$). Each station offers only one type of toy, so to collect all the Biciaki, one has to travel a bit.

Every morning, Bajtazar wonders how many different types of Biciaki he could buy that day. The situation is complicated by the fact that the assortment at the stations changes. Help Bajtazar and write a program that solves his dilemma.

Input

The first line of input contains three integers $n$, $m$, and $z$ ($2 \le n \le 100\,000$, $1 \le m, z \le 150\,000$), representing the number of cities in Bajtocja, the number of types of Biciaki, and the number of queries, respectively.

The next $n-1$ lines contain the description of the road network: each of these lines contains three integers $a$, $b$, and $c$ ($1 \le a, b \le n$, $1 \le c \le m$), representing a road between city $a$ and city $b$, with a gas station offering a Biciak of type $c$.

The next $z$ lines contain the queries. Each of these lines starts with a single character, followed by one or two integers: $Z \ x$ represents Bajtazar's query about the number of different types of Biciaki he can buy if he travels to city $x$ ($2 \le x \le n$); $B \ i \ c$ means that at the gas station located on the $i$-th road ($1 \le i < n$; the order of roads is the same as in the input), one can now buy a Biciak of type $c$ ($1 \le c \le m$). Note that it is possible that at the time of this operation, the station was already selling a Biciak of type $c$ (in which case this operation changes nothing).

There will be at least one $Z$-type query in the input.

Output

Your program should output as many lines as there were $Z$ queries in the input. For each of them, output a single integer representing the answer to Bajtazar's question.

Examples

Input 1

6 3 5
1 2 3
1 3 2
3 4 3
5 3 1
6 4 2
Z 5
Z 6
B 2 1
Z 5
Z 6

Output 1

2
2
1
3

Note

Explanation of the example: The route to city $6$ leads through cities $1-3-4-6$. Initially, one can buy Biciaki of types $2, 3,$ and $2$ on this route (a total of $2$ different types). After changing the assortment at the station on the road $1-3$, one can buy Biciaki of types $1, 3,$ and $2$ on the route (a total of $3$ different types).

Subtasks