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 \(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 \(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]\).