It Takes a Village

You are a sociologist studying a kingdom. The kingdom has a capital, several villages, and roads connecting them. Your research shows three conditions under which one village economically affects another. Village $P$ affects village $Q$ if any of the following holds.

1. There are two completely different paths from $P$ to $Q$ that share no village other than $P$ and $Q$.
2. Every path from $Q$ to the capital passes through $P$.
3. $P$ affects some village $R$, and $R$ affects $Q$.

The kingdom is building trading posts to lift the economy of its villages. Building a trading post in a village raises the revenue of that village, and it raises the revenue of every village that this village affects under the rules above. The king wants to know what his new trading posts are doing, so now and then he asks for the revenue of one village.

The king's actions are given in order, both building trading posts and asking about a village. Answer his questions.

The input holds several test cases. Each test case begins with a line of three integers $n$ ($1 \le n \le 100{,}000$), $m$ ($0 \le m \le 100{,}000$), and $q$ ($1 \le q \le 200{,}000$): the number of villages, the number of roads, and the number of actions the king performs. Villages are numbered from $1$ to $n$, and village $1$ is the capital.

Each of the next $m$ lines holds two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), a road between village $a$ and village $b$. A road can be travelled in either direction. Two villages may be joined by more than one road, and in that case each road is a separate way to travel. Every village is reachable from the capital.

The next $q$ lines give the king's actions in order. An action has one of two forms.

+ k x

The king builds a trading post in village $k$ ($1 \le k \le n$), which raises the revenue of every affected village by $x$ ($1 \le x \le 1{,}000$).

? k

The king asks for the total revenue of village $k$ ($1 \le k \le n$), counting the trading posts built in that village and the trading posts built in every village that affects it.

The parts of an action are separated by a single space, with no leading or trailing blanks. The input ends with a line holding three zeros.

For each ? k action, print one integer on its own line, the answer to that question. Answer the questions in the order they are asked. Print no extra spaces and no blank lines.