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