It’s universally acknowledged that there’re innumerable trees in the campus of HUST.
In 8102, Alisa took fishing as her business. When she was walking along the bank and forgot the distance gradually, she came upon a peach forest and found an interesting thing. These trees lining up in one row can be numbered from 1 to N, and each one had a color. Alisa sometimes likes color X, and she will color the trees in [L,R] to the same color X, or sometimes wants to query the maximum elegant values of [L,R] after being cut into at most k+1 subintervals. The elegant value of an interval is defined as the sum of the number of different consecutive digits in each subinterval.
For example:
The elegant value of 2 2 2 3 3 is 2 and it becomes 4 after cutting twice. (You can cut it into {2} {2} {2 3 3} or {2} {2 2 3} {3} or {2 2} {2 3} {3})

The first line contains two integers N and M(1≤N,M≤2×105), the number of trees and the number of operations.
The second line contains N integers ai (1≤ai≤109), the color of the i-th tree.
Then m lines follow.
1. Format of the query 1 L R X. You need to color the tree in [L,R] to the same color X.
2. Format of the query 2 L R k. You should output the elegant value of [L,R] cutting k times.
It is guaranteed that 1≤L≤R≤n,1≤X≤109,0≤k≤R-L.

For each query of the second type, print the maximum elegant value in a single line.

3 3
1 2 3
2 1 3 1
1 1 3 1
2 1 3 1

3
2