Library Bookshelf Manager

Little J is a librarian at the National Library. He is in charge of managing a huge bookshelf that consists of \(N\) slots, numbered from \(1\) to \(N\). Each slot contains a book with a specific code. Due to the enormous size of the bookshelf, Little J’s work efficiency is often low. His tasks include the following two operations:

• Update operation: Since the bookshelf is always full, when a new book is purchased, Little J must remove the book at a specified position and replace it with the new one.
• Query operation: Answer customer queries. A customer asks how many books with a given code exist in a contiguous segment of the bookshelf.

For example, suppose \(N=5\) and the initial book codes are \(1, 2, 3, 4, 5\). Then:

1. A query for the range from slot 1 to 3 for code 2 returns 1.
2. A query for the range from slot 1 to 3 for code 1 returns 1.
3. After updating slot 2 to code 1, a query for the range from slot 1 to 3 for code 2 returns 0 and for code 1 returns 2.

Your task is to write a program that processes a sequence of operations and answers each query correctly.

Note: All formulas are provided in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(N\) and \(Q\) \( (1 \leq N, Q \leq 10^5) \) representing the number of book positions and the number of operations respectively.

The second line contains \(N\) integers, where the \(i\)-th integer represents the initial code of the book at position \(i\).

Each of the next \(Q\) lines represents an operation in one of the following two formats:

• 1 x y: Update operation. Replace the book at position \(x\) with a new book having code \(y\).
• 2 l r x: Query operation. Output the number of books with code \(x\) in the range from position \(l\) to \(r\) (inclusive).

outputFormat

For each query operation (operations beginning with 2), output one integer on a separate line representing the count of books with the queried code in the specified range.

sample

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

1
1
0
2