Cho dãy số ~A~ có ~N~ phần tử (đánh số từ ~1~ đến ~N~). Một cặp chỉ số ~(\,i, j\,)~ được gọi là cặp nghịch thế nếu ~1 \le i < j \le N~ và ~A_i > A_j~.

Bạn cần trả lời ~Q~ truy vấn về số lượng cặp nghịch thế nằm hoàn toàn trong một đoạn con của mảng. Mỗi truy vấn ban đầu được nhập dưới dạng hai số ~x, y~, nhưng đoạn truy vấn thực tế ~[L, R]~ được tính theo quy tắc phụ thuộc vào kết quả truy vấn trước đó như sau:

• Gọi ~ans\_last~ là kết quả của truy vấn liền trước (đặt ~ans\_last = 0~ với truy vấn đầu tiên).
• Tính ~u = (x - 1 + ans\_last) \bmod N + 1~, ~v = (y - 1 + ans\_last) \bmod N + 1~.
• Đoạn cần xét là ~[L, R] = [\min(u, v), \max(u, v)]~.

Nhiệm vụ của bạn là, với mỗi truy vấn, in ra số lượng cặp nghịch thế nằm trong đoạn ~[L, R]~.

Yêu cầu

Viết chương trình đọc dữ liệu, xử lý ~Q~ truy vấn như mô tả và in ra mỗi dòng một số nguyên là kết quả tương ứng.

Dữ liệu

• Dòng 1: Hai số nguyên ~N~, ~Q~ ~(1 \le N, Q \le 10^5)~.
• Dòng 2: ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(1 \le A_i \le 10^9)~.
• Dòng 3..Q+2: Mỗi dòng chứa hai số nguyên ~x, y~ ~(1 \le x, y \le N)~.
  Với mỗi truy vấn, đặt $$ u = (x - 1 + ans\_{last}) \bmod N + 1,\quad v = (y - 1 + ans\_{last}) \bmod N + 1, $$ $$ [L, R] = [\min(u, v), \max(u, v)]. $$ Trong đó ~ans\_{last}~ là kết quả của truy vấn liền trước (với truy vấn đầu tiên, ~ans\_{last}=0~).

Kết quả

• In ra ~Q~ dòng, dòng thứ ~i~ là số lượng cặp nghịch thế trong đoạn ~[L, R]~ của truy vấn thứ ~i~.

Ví dụ

Input

6 4
7 7 4 5 2 10
1 4
2 5
3 6
4 5

Output

4
2
5
0

Giải thích tham khảo (không bắt buộc)

• Truy vấn 1: ~ans\_{last}=0~, ~u=1, v=4 \Rightarrow [L,R]=[1,4]~. Đoạn ~[7,7,4,5]~ có 4 nghịch thế: ~(1,3),(1,4),(2,3),(2,4)~.
• Truy vấn 2: ~ans\_{last}=4~, ~u=2+4=6 \mapsto 6, v=5+4=9 \mapsto 3~ (modulo theo đề), nên ~[L,R]=[3,6]~ là ~[4,5,2,10]~, kết quả ~2~.
• Các truy vấn sau tương tự.

Ví dụ bổ sung

Input

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

Output

10
3
0
6
1

Gợi ý kiểm tra tay

• Đoạn nghịch thế tối đa với mảng giảm dần: ~[1..5]~ có ~\binom{5}{2}=10~ cặp.

Chấm điểm

Bộ test gồm nhiều nhóm với tổng ~100~ điểm:

• Subtask 1 (20 điểm): ~1 \le N, Q \le 2000~ — có thể duyệt trực tiếp ~\mathcal{O}(N^2)~ cho mỗi truy vấn.
• Subtask 2 (30 điểm): ~Q \le 10^5~, nhưng các truy vấn có ~R-L+1 \le 2000~.
• Subtask 3 (50 điểm): Ràng buộc đầy đủ ~(N, Q \le 10^5)~. Gợi ý dùng:
  • MOs algorithm trên đoạn tĩnh với kỹ thuật nén giá trị + Fenwick/BIT để cập nhật đếm khi mở rộng/thu hẹp đoạn; tổng độ phức tạp xấp xỉ ~\mathcal{O}((N+Q)\sqrt{N}\,\log N)~ (hoặc ~\mathcal{O}((N+Q)\sqrt{N})~ nếu dùng đếm hai phía bằng mảng tần suất).
  • Hoặc cây phân đoạn động/merge sort tree để trả lời mỗi truy vấn ~\mathcal{O}(\log^2 N)~ và cộng dồn qua các mức, nhưng lưu ý chi phí đếm cặp cần tách trái/phải cẩn thận.

Lưu ý triển khai (không bắt buộc):

• Vì giá trị ~A_i~ tới ~10^9~, hãy nén giá trị về miền ~[1..M]~ trước khi dùng Fenwick/BIT hay mảng tần suất.
• Với MO, khi thêm phần tử ~x~ vào bên phải đoạn hiện tại, số cặp nghịch thế tăng thêm số lượng phần tử lớn hơn ~x~ đã có trong đoạn; khi thêm vào bên trái, tăng thêm số lượng phần tử nhỏ hơn ~x~. Với thao tác loại bỏ, trừ ngược lại.
• Chú ý công thức xoay chỉ số bằng ~ans\_{last}~ như đề bài; phép modulo là theo ~N~ (không theo độ dài đoạn).