Yet another interesting problem about queries!

You have an array of n integers and q queries on this array. There are two types of queries:

1. 1 $a_i$ $b_i$ $x_i$ $y_i$ - change all occurrences of $x_i$ to $y_i$ on the segment $[a_i, b_i]$
2. 2 $a_i$ $b_i$ $x_i$ - count number of occurrences of $x_i$ on the segment $[a_i, b_i]$

This problem will be very popular! So you should solve it before before it became mainstream.

Input format

The first line of input contains two space separated integers n and q ($1 \leq n, q \leq 5 \cdot 10^5$) - size of array and number of queries.

The second line of input contains n space separated integers $a_i$ ($1 \leq a_i \leq n$) - the elements of the array before queries.

Then q lines follow. The i-th of them contains parameters of the i-th query.

The i-th line can be:

• 1 $a_i$ $b_i$ $x_i$ $y_i$ ($1 \leq a_i \leq b_i \leq n$, $1 \leq x_i, y_i \leq n$) - parameters for first type query or
• 2 $a_i$ $b_i$ $x_i$ ($1 \leq a_i \leq b_i \leq n$, $1 \leq x_i \leq n$) - parameters for second type query

Output format

For each query of second type print number of occurrences of $x_i$ on the segment $[a_i, b_i]$.