Truy vấn khó

Lokk yêu thích cấu trúc dữ liệu, và thú tiêu khiển ưa thích của Lokk là nghĩ ra những bài toán cấu trúc dữ liệu mới lạ rồi thách bạn bè giải. Hôm nay, Lokk nghĩ ra bài toán dưới đây và gửi cho Quang.

Cho mảng $a$ gồm $n$ phần tử $a_1,a_2,\dots ,a_n$. Nhiệm vụ của bạn là xử lý $q$ truy vấn thuộc các loại sau:

• 1 $p$: Hoán đổi hai phần tử $a_p$ và $a_{p+1}$.
• 2 $l$ $r$ $x$: Tính tổng bình phương của tất cả các vị trí từ $l$ đến $r$ có phần tử bằng $x$. Nói cách khác, tính ${\sum }_{i=l}^r{i}^2\times [a_i=x]$, trong đó $[P]$ là biểu thức có giá trị $1$ nếu $P$ đúng và $0$ nếu ngược lại.
• 3 $l$ $r$ $x$: Gọi $b$ là mảng gồm tất cả các vị trí trong mảng $a$ có phần tử bằng $x$, liệt kê theo thứ tự tăng dần (từ $1$ đến $n$). Tính ${\sum }_{i=l}^r{b}_i^2$.

Là một người giải bài xuất sắc, Quang nhanh chóng giải xong bài toán. Vì vậy, Lokk đặt thêm một thử thách: Quang phải trả lời các truy vấn trực tuyến, nghĩa là các truy vấn được mã hóa sao cho cần biết đáp án đúng của truy vấn hiện tại mới giải mã được truy vấn tiếp theo.

Điều này quá sức với Quang, nên Quang bỏ cuộc và nhờ các thí sinh giúp đỡ. Bạn có giải được không?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($2\le n\le 2\times {10}^5$, $1\le q\le 2\times {10}^5$), độ dài mảng $a$ và số truy vấn cần xử lý.

Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$), các phần tử của mảng $a$.

Mỗi dòng trong $q$ dòng tiếp theo mô tả một truy vấn cần xử lý. Số đầu tiên là $t$ ($1\le t\le 3$), loại truy vấn. Các truy vấn được mã hóa như sau: gọi $\mathit{l}\mathit{a}\mathit{s}\mathit{t}$ là đáp án của truy vấn loại $2$ hoặc $3$ gần nhất mà bạn đã trả lời (ban đầu $\mathit{l}\mathit{a}\mathit{s}\mathit{t}=0$).

Nếu $t=1$, tiếp theo là một số nguyên $p^{\prime }$ ($1\le p^{\prime }<n$). Giải mã truy vấn bằng phép tính $p=(p^{\prime }+\mathit{l}\mathit{a}\mathit{s}\mathit{t}-1)mod(n-1)+1$.

Nếu $t=2$ hoặc $t=3$, tiếp theo là ba số nguyên $l^{\prime }$, $r^{\prime }$ và $x^{\prime }$ ($1\le l^{\prime },r^{\prime },x^{\prime }\le n$). Giải mã truy vấn bằng các phép tính sau:

• $l=(l^{\prime }+\mathit{l}\mathit{a}\mathit{s}\mathit{t}-1)modn+1$
• $r=(r^{\prime }+\mathit{l}\mathit{a}\mathit{s}\mathit{t}-1)modn+1$
• $x=(x^{\prime }+\mathit{l}\mathit{a}\mathit{s}\mathit{t}-1)modn+1$
• Nếu $l>r$, hoán đổi $l$ và $r$.

Với $t=3$, dữ liệu bảo đảm $r$ không vượt quá độ dài của mảng $b$ (định nghĩa trong mô tả truy vấn).

Dữ liệu ra

Với mỗi truy vấn loại $2$ hoặc $3$, in ra một số nguyên là đáp án của truy vấn.

Ràng buộc

• $2\le n\le 2\times {10}^5$, $1\le q\le 2\times {10}^5$
• $1\le a_i\le n$
• $1\le p^{\prime }<n$; $1\le l^{\prime },r^{\prime },x^{\prime }\le n$
• Với truy vấn loại $3$, $r$ sau khi giải mã không vượt quá độ dài mảng $b$.

Ví dụ