• 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:

1. Change the food type to type c in all boxes with indices from l to r, inclusve.
2. 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.