Patchouli's magic library contains ~N~ books, where each book has a label ~A_i~ to keep things organized. Due to the overwhelmingly large amount of books, Patchouli asks you to help her keep track of the book's labels as she does ~Q~ operations in the library.

The operations are of the following types ~t_i~:

1. Set the label of all books from book ~l_i~ to book ~r_i~, inclusive, to ~v_i~.
2. Query the number of books with a label equal to ~v_i~ from book ~l_i~ to book ~r_i~, inclusive.

Constraints

~1 \le N \le 10^6~

~1 \le Q \le 2 \times 10^5~

~1 \le l_i \le r_i \le N~

~1 \le A_i, v_i \le 500~

~t_i \in \{1, 2\}~

Subtask 1 [2/15]

~1 \le N, Q \le 100~

Subtask 2 [6/15]

~l_i = r_i~ for all queries of type ~1~.

Subtask 3 [7/15]

No additional constraints.

Input Specification

The first line of input contains ~2~ space separated integers, ~N~ and ~Q~, the number of books and the number of operations respectively.

The second line of input contains ~N~ space separated integers, ~A_i~, the label of each book in order.

The next ~Q~ lines of input contains ~4~ integers each, ~t_i~, ~l_i~, ~r_i~, and ~v_i~, the parameters for each operation.

Output Specification

For each type ~2~ operation, output ~1~ integer on its own line, the answer to that query.

Sample Input

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

Sample Output

2
4
1

Explanation for Sample Output

In the first operation, the queried books have labels ~[4, 3, 4]~, ~2~ of which have a label equal to ~4~.

In the second operation, the book's labels become ~[1, 1, 1, 1, 6, 6]~.