DZY loves colors, and he enjoys painting.
On a colorful day, DZY gets a colorful ribbon, which consists of units (they are numbered from to from left to right). The color of the -th unit of the ribbon is at first. It is colorful enough, but we still consider that the colorfulness of each unit is at first.
DZY loves painting, we know. He takes up a paintbrush with color and uses it to draw a line on the ribbon. In such a case some contiguous units are painted. Imagine that the color of unit currently is . When it is painted by this paintbrush, the color of the unit becomes , and the colorfulness of the unit increases by .
DZY wants to perform operations, each operation can be one of the following:
- Paint all the units with numbers between and (both inclusive) with color .
- Ask the sum of colorfulness of the units between and (both inclusive).
Can you help DZY?
The first line contains two space-separated integers ().
Each of the next lines begins with a integer (), which represents the type of this operation.
If , there will be more integers (; ) in this line, describing an operation .
If , there will be more integers () in this line, describing an operation .
For each operation , print a line containing the answer — sum of colorfulness.
3 3 1 1 2 4 1 2 3 5 2 1 3
In the first sample, the color of each unit is initially , and the colorfulness is .
After the first operation, colors become , colorfulness become .
After the second operation, colors become , colorfulness become .
So the answer to the only operation of type is .
3 4 1 1 3 4 2 1 1 2 2 2 2 3 3
3 2 1
10 6 1 1 5 3 1 2 7 9 1 10 10 11 1 3 8 12 1 1 10 3 2 1 10
可以考虑使用线段树维护区间权值和以及区间/节点颜色。每次修改是直接修改颜色相同的区间，对于区间内颜色不同的则暴力递归修改，暴力修改的次数至多为 次。时间复杂度为 ，可以通过本题。