Cho một cây gồm ~n~ đỉnh có gốc là ~1~. Mỗi đỉnh ~i~ sẽ được tô màu ~c_i \in \{0,1\}~. Mỗi cạnh ~i~ có trọng số ~w_i~. Có ~q~ truy vấn thuộc ~1~ trong ~2~ loại sau:

~1\ u~: đổi màu của đỉnh ~u~ (~1 \le u \le n~)

~2\ u\ v\ t\ k~: với mọi đỉnh ~x~ nằm trong cây con gốc ~u~ có ~c_x=t~ in ra ~k~ đường đi dài nhất từ ~v~ đến các đỉnh ~x~ (Đảm bảo có ~\ge k~ đỉnh có màu là ~t~ nằm trong cây con của ~u~) (~1 \le u,v \le n~) (~t \in \{0,1\}~) (~1 \le k \le 3~)

Đỉnh ~x~ nằm trong cây con gốc ~u~ khi ~u~ nằm trên đường đi từ ~1~ tới ~x~

Input

Dòng đầu tiên gồm ~2~ số ~n~ và ~q~ (~1 \le n,q \le 10^5~)

Dòng thứ ~2~ gồm ~n~ số ~c_i \in \{0,1\}~ là màu của đỉnh ~i~ ban đầu

~n-1~ dòng tiếp theo gồm ~3~ số ~u_i,v_i,w_i~ (~1 \le u_i,v_i \le n~) (~-10^9 \le w_i \le 10^9~)

~q~ dòng tiếp theo là ~1~ trong ~2~ truy vấn.

Output

Gồm các dòng là đáp án cho các truy vấn ~2~

Scoring

Sample Input 1

5 5
1 0 0 0 0
1 2 -1
2 3 2
4 3 1
3 5 -3
2 2 2 0 3
1 5
2 1 1 0 3
1 2
2 1 1 1 3

Sample Output 1

3 2 0
2 1 -1
0 -1 -2