- Russian version of the problem can be read here.
There are N boxes where cats can sleep and eat, numbered from the left to the right starting from 1. Each box contains some type of food, which is a positive integer. Initially, the i-th box contains food of type A[i].
A cat will occupy some consecutive subset of boxes, and all the food in the subset must be of the same type.
M events happened. There are events of two types:
- Change the food type to type c in all boxes with indices from l to r, inclusve.
- Count the number of possible subsets a cat can choose, considering that he is allowed to occupy only boxes with indices from l to r, inclusve.
Your task is to process all the given events.
Input format
The first line of the input contains two integers N and M. The second line contains N space separated integers, which are the array A[i]. The following M lines contain desription of the events, in chronological order. Each line is if format "0 l r c" in case of an event of the first type, and "1 l r" in case of the second one.
Output format
For each event of the second type print the answer to the corresponding event.
Constraints
1 ≤ N, M ≤ 100,000, all types of food are integers between 1 and 1,000,000,000.