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]$.