스프링클러

JOI 군은 집 텃밭에서 여러 해 동안 채소를 길러 왔다. 이제 그는 IOI 농장을 관리하려 한다.

IOI 농장에는 1번부터 $N$번까지 번호가 붙은 땅 $N$개가 있다. 1번부터 $N-1$번까지 번호가 붙은 도로 $N-1$개가 있다. $i$번 도로는 땅 $A_i$와 땅 $B_i$를 양방향으로 잇는다. 도로를 따라 어느 땅에서든 다른 어느 땅으로든 갈 수 있다.

모든 땅에는 스프링클러가 하나씩 있다. 스프링클러는 주변 땅에 물을 뿌린다.

JOI 군은 JOI 수수를 키운다. 이 식물은 물을 주는 즉시 키가 변한다. 그런데 약하다. 키가 $L$ 이상이 되면 길이 $L$만큼의 윗부분이 곧바로 부러지고, JOI 군은 부러진 부분을 거둬들인다.

처음에 JOI 군은 땅 $j$에 키가 $H_j$인 JOI 수수를 심는다($1 \le j \le N$). 그 뒤 $Q$일 동안 매일 수수를 돌본다. $k$일째에는 다음 중 하나를 한다.

• 1형: JOI 군은 땅 $X_k$의 스프링클러를 사용해, $X_k$로부터의 거리가 $D_k$ 이하인 모든 땅에 물을 준다. 물을 받은 수수의 키는 $W_k$배가 된다. 다만 부러지는 규칙 때문에, 키가 $h$인 수수에 물을 주면 최종 키는 $h \times W_k$를 $L$로 나눈 나머지가 된다.
• 2형: JOI 군은 땅 $X_k$에 있는 수수의 키를 잰다.

두 땅 사이의 거리는 한 땅에서 다른 땅까지 이르는 경로가 지나는 도로 수의 최솟값이다.

N L
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}
H_1
H_2
...
H_N
Q
질의 1
...
질의 Q

각 질의는 다음 중 하나의 줄이다.

• 1형 행동은 1 X D W 형식이다.
• 2형 행동은 2 X 형식이다.

2형 행동마다, 그날 측정한 땅 $X_k$의 수수 키를 입력 순서대로 한 줄에 하나씩 출력한다.

• $2 \le N \le 200000$
• $2 \le L \le 10^9$
• $1 \le A_i < B_i \le N$ ($1 \le i \le N-1$)
• 도로를 따라 어느 땅에서든 다른 어느 땅으로든 갈 수 있다.
• $0 \le H_j \le L-1$ ($1 \le j \le N$)
• $1 \le Q \le 400000$
• $T_k$는 1 또는 2이다 ($1 \le k \le Q$).
• $T_k = 1$이면 $1 \le X_k \le N$, $0 \le D_k \le 40$, $0 \le W_k \le L-1$이다.
• $T_k = 2$이면 $1 \le X_k \le N$이다.