Cho mảng ~A_0~ có độ dài ~n~, bạn cần thực hiện ~q~ truy vấn, mỗi truy vấn thứ ~i~ thuộc trong ~2~ loại sau :

• ~1~ ~id~ ~v:~ Copy mảng ~A_{id}~ vào ~A_i~, sau đó thêm ~v~ vào cuối mảng ~A_i~.

• ~2~ ~id~ ~v:~ Copy mảng ~A_{id}~ vào ~A_i~, sau đó thực hiện ~XOR~ tất cả các phần tử của mảng ~A_i~ cho ~v~.

Sau khi thực hiện ~q~ truy vấn, hãy cho biết phần từ nhỏ nhất trong từng mảng ~A_0, A_1, \ldots ,A_q~.

Input

Dữ liệu vào từ file văn bản copyarray.inp

• Dòng đầu tiên nhập ~2~ số nguyên dương ~n~ và ~q~ ~(1 \le n, q \le 10^5)~.

• Dòng thứ hai nhập ~n~ số nguyên của dãy ~A_0~ ~(1 \le A_{0_i} \le 2^{30})~.

• ~q~ dòng tiếp theo, dòng thứ ~i~ nhập ~3~ số ~type_i, id_i, v_i~ ~(1 \le type_i \le 2, 0 \le id_i < i, 0 \le v_i \le 2^{30})~.

Output

Kết quả in ra file văn bản copyarray.out

• In ra ~q + 1~ số nguyên không âm trên một dòng, số thứ ~i~ cho biết phần tử nhỏ nhất của mảng ~A_i~.

Scoring

Sample Input 1

2 4
2 3
1 0 4
2 1 5
1 2 6
1 0 7

Sample Output 1

2 2 1 1 2

Notes

• ~A_0 = \{2, 3 \}~.

• ~A_1 = \{2, 3, 4 \}~.

• ~A_2 = \{7, 6, 1 \}~.

• ~A_3 = \{7, 6, 1, 6\}~.

• ~A_4 = \{2, 3, 7\}~.