나무나무나 심어야지

근성은 나무에 관심이 많다.

비록 지금은 개발을 하고 있지만, 나무에 대한 애정이 식은 것은 아니다. 어느 날 이진 트리를 가지고 놀던 근성은 이진 트리가 나무인데도 열매가 열리지 않는다는 사실을 깨닫고 큰 충격에 빠졌다. 나무에는 반드시 열매가 열려야 한다고 주장한 근성은 열매가 열리는 트리 그래프를 만들었고, 이를 "나무나무"라고 이름 지었다.

나무나무의 특징은 다음과 같다.

1. 이 트리의 $1$번 정점은 뿌리를 의미한다. 이 트리는 뿌리로부터 위로 뻗어 나간다.
2. $1$번 정점을 제외한 정점은 가지가 갈라지거나 끝나는 지점을 의미한다. 정점에는 가지가 연결될 수 있다. 단, 다른 정점에서 갈라진 가지가 정점에서 합쳐지지는 않는다.
3. 간선은 가지를 의미한다. 가지 양 끝에는 반드시 정점이 존재한다.
4. 정점에는 최대 1개의 열매가 열릴 수 있다. 뿌리에는 열매가 열리지 않는다. 매 쿼리에 앞서 열매가 열릴 수 있는 정점에는 열매가 열린다.

트리를 만든 후 무엇을 할 수 있을지 고민하다가 아래 두 가지 쿼리를 떠올렸다.

• 1 i j w: (접목) 임의의 정점 $i$에 가지를 붙인다.
  • 정점 $i$는 뿌리와 같은 그래프에 속하는 정점이다.
  • 가지 끝에는 정점이 항상 존재하므로, 새로 생긴 가지의 반대쪽에 $j$번으로 번호를 붙인 정점이 함께 붙는다.
  • 정점 $j$에는 무게 $w$의 열매가 달린다. $w=0$은 열매가 열리지 않는다는 뜻이다.
  • ($1 \le i, j \le N + M;$ $0 \le w \le 500$)
• 2 i: (수확) 정점 $i$와, 그 위로 연결된 모든 정점의 열매를 떨어뜨리려면 얼마의 힘으로 흔들어야 하는지 출력한다.
  • 임의의 정점 $i$를 흔들면 그 위로 연결된 가지와 정점들이 모두 같은 힘으로 흔들린다.
  • 정점 $i$를 흔들어 모든 열매를 떨어뜨리려면 힘이 정점 $i$와 그 위로 연결된 모든 정점에 달린 열매 무게의 합과 같아야 한다.
  • 힘 $0$으로는 흔들 수 없으므로, 무게 합이 $0$이면 -1을 출력한다.
  • ($1 \le i \le N + M$)

쿼리에 주어지는 수는 모두 정수이고, 입력이 올바름은 보장된다. 또한 수확 쿼리는 1회 이상 주어진다.

그런데 근성은 이 쿼리를 만들다가 갑자기 동아리방에 가야 한다며 떠났다. 여러분이 대신 풀어 주자.

첫째 줄에 최초 정점의 수 $N$과 쿼리의 수 $M$이 공백으로 구분되어 주어진다. 최초의 정점에는 $1$ 이상 $N$ 이하의 번호가 중복되지 않게 붙어 있다. ($2 \le N, M \le 100\,000$)

둘째 줄에 $1$번부터 $N$번까지, 각 정점이 바로 위에서 어느 정점과 가지로 연결되어 있는지가 공백으로 구분되어 주어진다. $1$번은 뿌리이므로 -1이 주어진다. 모든 정점은 최종적으로 뿌리와 같은 그래프에 속하지만, 입력 도중에는 속하지 않을 수 있다.

셋째 줄에 $1$번부터 $N$번까지, 각 정점이 가진 열매의 무게 $w_i$가 공백으로 구분되어 주어진다. ($0 \le w_i \le 500$) $0$이면 열매가 열리지 않는 것이며, 뿌리에는 열매가 열리지 않는다.

넷째 줄부터 $M$개의 줄에 걸쳐 쿼리가 주어진다.

수확 쿼리가 들어올 때마다 정점을 흔들어야 할 힘을 출력한다. 단, 흔들어야 할 힘이 $0$이라면 -1을 출력한다.

최초 트리의 형태이다. 첫 번째 쿼리에서 $1$번 정점을 흔들면 $2$, $3$번 정점이 같이 흔들리고, $3$번 정점에 달린 열매를 떨어뜨리기 위해 $3$의 힘으로 흔들어야 한다.

접목을 세 번 진행한 모습이다. $4$번 정점을 흔들면 $4$번만 흔들리고, $4$번에 달린 열매를 떨어뜨리기 위해 $5$의 힘으로 흔들어야 한다. 마찬가지로 $7$번 정점을 흔들면 $7$, $4$, $5$번이 흔들리고, $4$번과 $7$번의 열매를 떨어뜨리기 위해 $9$의 힘으로 흔들어야 한다.

두 번째 예시를 보자. 첫 번째 쿼리에서 $1$번 정점을 흔들면 $2$, $3$, $4$번이 같이 흔들리지만, 열매가 달려 있지 않다. 흔들어야 할 힘이 $0$이므로 -1을 출력한다.

$1$번 정점을 흔들면 $2$, $3$, $4$, $7$번이 같이 흔들리고, $7$번의 열매를 떨어뜨리기 위해 $500$의 힘으로 흔들어야 한다.