Tourist Ratings in Utopia

Utopia has \( n \) cities numbered from 1 to \( n \) and \( n-1 \) bidirectional roads connecting these cities; the network forms a tree. There are also \( m \) tourists numbered from 1 to \( m \). Initially, the \( i\)-th tourist is visiting city \( a_i \). Note that multiple tourists can start at the same city. Every tourist begins with a rating of 0.

During their stay, some tourists travel between cities. Traveling is fast but inconvenient: when a tourist moves along a path comprising \( k \) roads (always choosing the shortest path), their rating decreases by \( k \).

To encourage further travel, the Utopian government organizes events in chosen cities. When an event is held in city \( c \) with an effect value \( d \), the rating of every tourist currently located in city \( c \) increases by \( d \).

You will be given \( q \) queries. Process the queries in the order given. Each query is one of the following types:

• Type 1: 1 p x — Tourist \( p \) travels from his current city to city \( x \). Deduct the number of roads in the shortest path (i.e. the distance) from the tourist's rating, then update his location to \( x \).
• Type 2: 2 c d — An event in city \( c \) increases the rating of every tourist currently in \( c \) by \( d \).
• Type 3: 3 p — Output the current rating of tourist \( p \).

Note: The cities form a tree, so there is a unique shortest path between any two cities.

inputFormat

The first line of input contains three integers: n (number of cities), m (number of tourists), and q (number of queries).

Then follow n-1 lines each containing two integers u and v, representing a bidirectional road between cities u and v.

The next line contains m integers: a1, a2, ..., am, where ai is the starting city of the \( i\)-th tourist.

Then follow \( q \) lines, each representing a query in one of the following formats:

• 1 p x: Tourist \( p \) travels to city \( x \). Their rating decreases by the distance (number of roads) between the current city and \( x \), and their position is updated to \( x \).
• 2 c d: An event is organized in city \( c \) that increases the rating of every tourist in city \( c \) by \( d \).
• 3 p: Output the current rating of tourist \( p \).

outputFormat

For each query of type 3, output the current rating of the specified tourist on a new line.

sample

3 2 5
1 2
2 3
1 2
3 1
1 1 3
3 1
2 3 5
3 1

0
-2
3