온 마을이 필요하다

당신은 사회학자로서 어느 왕국을 연구하고 있다. 이 왕국에는 수도 하나와 여러 마을이 있고, 그 사이를 잇는 도로가 놓여 있다. 연구 결과 한 마을이 다른 마을의 경제에 영향을 주는 조건은 세 가지다. 다음 중 하나라도 성립하면 마을 $P$는 마을 $Q$에 영향을 준다.

1. $P$에서 $Q$로 가는 완전히 다른 두 경로가 있고, 두 경로는 $P$와 $Q$ 외에 어떤 마을도 공유하지 않는다.
2. $Q$에서 수도로 가는 모든 경로가 $P$를 지난다.
3. $P$가 마을 $R$에 영향을 주고, $R$이 $Q$에 영향을 준다.

왕국은 마을 경제를 살리려고 교역소를 짓기 시작했다. 어떤 마을에 교역소를 지으면 그 마을의 수입이 늘어나고, 위 규칙에 따라 그 마을이 영향을 주는 모든 마을의 수입도 늘어난다. 왕은 새 교역소의 효과가 궁금해서 이따금 특정 마을의 수입을 묻는다.

교역소를 짓는 행동과 마을을 묻는 행동이 순서대로 주어진다. 왕의 질문에 답하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 세 개 $n$ ($1 \le n \le 100{,}000$), $m$ ($0 \le m \le 100{,}000$), $q$ ($1 \le q \le 200{,}000$)가 주어진다. 차례대로 마을의 수, 도로의 수, 왕이 하는 행동의 수다. 마을 번호는 $1$번부터 $n$번까지이고, $1$번이 수도다.

다음 $m$개 줄에는 정수 두 개 $a$, $b$ ($1 \le a, b \le n$, $a \ne b$)가 주어진다. 마을 $a$와 마을 $b$를 잇는 도로를 뜻하며, 도로는 양쪽 방향으로 모두 다닐 수 있다. 두 마을 사이에 도로가 여러 개 놓여 있을 수도 있고, 이때 각 도로는 서로 다른 길이다. 수도에서 모든 마을로 갈 수 있다.

그다음 $q$개 줄에는 왕의 행동이 순서대로 주어지며, 형태는 둘 중 하나다.

+ k x

왕이 마을 $k$ ($1 \le k \le n$)에 교역소를 짓는다. 영향을 받는 모든 마을의 수입이 $x$ ($1 \le x \le 1{,}000$)만큼 늘어난다.

? k

왕이 마을 $k$ ($1 \le k \le n$)의 총수입을 묻는다. 그 마을에 지어진 교역소와, 그 마을에 영향을 주는 모든 마을에 지어진 교역소를 모두 더한 값이다.

행동을 이루는 각 부분은 공백 하나로 구분하고, 줄 앞뒤에 여분의 공백은 없다. 입력의 마지막 줄에는 $0$이 세 개 주어진다.

? k 행동마다 그 질문의 답을 정수 하나로 한 줄에 출력한다. 질문이 나온 순서대로 답하고, 여분의 공백이나 빈 줄은 출력하지 않는다.