Lihwy đang bận rộn chuẩn bị cho Bedao contest mới nhất. Lihwy có một danh sách các bài tập, được đánh dấu từ ~1~ đến ~n~. Ban đầu, các bài tập có độ khó là ~A_i = 0~. Tại ~q~ thời điểm sẽ có một trong hai việc sau xảy ra:

~1~ ~l~ ~r~ ~x~ ~(1 \le x \le 10^9)~: Với những bài tập ~i~ thoả mãn ~l \le i \le r~, Lihwy đã thêm thắt dữ kiện để bài tập đó trở nên khó hơn. Độ khó mới của bài tập thứ ~i~ luôn là ~A_i = A_i \oplus x~ với ~\oplus~ là phép toán xor.

~2~ ~l~ ~r~: Anh ấy muốn biết tổng xor độ khó của các bài tập trong đoạn ~[l, r]~. Nói cách khác, hãy tính giá trị ~A_l \oplus A_{l + 1} \oplus ... \oplus A_r~. Sau đó, do không hài lòng về kết quả, Lihwy sẽ xoá toàn bộ những dữ kiện thêm thắt của ~n~ bài tập. Lúc này độ khó tất cả các bài tập trở thành ~0~.

Hãy giúp Lihwy tính toán để Lihwy có thể chuẩn bị một contest Bedao chất lượng nhất nhé!

Input

Dòng đầu chứa hai số nguyên dương ~n~ và ~q~ ~(1 \le n, q \le 2 \times 10^5)~.

~q~ dòng tiếp theo chứa một trong hai sự việc.

Output

Với mỗi sự việc loại ~2~, in ra tổng độ khó cần tìm.

Scoring

Sample Input 1

3 4
1 1 3 1
2 1 3
1 1 2 2
2 2 2

Sample Output 1

1
2

Notes

Sau sự việc thứ nhất, độ khó các bài là ~[1, 1, 1]~. Do đó tổng xor độ khó đoạn ~[1, 3]~ là ~1~.

Sau sự việc thứ hai, độ khó tất cả các bài tập trở thành ~0~.

Sau sự việc thứ ba, độ khó các bài là ~[2, 2, 0]~. Tổng xor độ khó đoạn ~[2, 2]~ là ~2~.