Background

238 Theology Sect #3.

— How long until the sun comes out?

— I do not know...

In an ancient legend, the small village near your home was punished by the Sun God for offending him, and its sunlight was taken away. Crops withered one after another, and people struggled to survive in cold and hunger. Near the village, besides your home, there was only a vast wasteland.

Theology began to rise in the village. More and more people became theologians, studying ancient books day and night in the library that had been funded and built back then. Finally, in a dark, damp corner of the library warehouse, everyone found a book—

An old and tattered book, said to have been lost long ago, called Sun-Praying Technique.

Background

238 Theology Sect #3.

— How long until the sun comes out?

— I do not know...

In an ancient legend, the small village near your home was punished by the Sun God for offending him, and its sunlight was taken away. Crops withered one after another, and people struggled to survive in cold and hunger. Near the village, besides your home, there was only a vast wasteland.

Theology began to rise in the village. More and more people became theologians, studying ancient books day and night in the library that had been funded and built back then. Finally, in a dark, damp corner of the library warehouse, everyone found a book—

An old and tattered book, said to have been lost long ago, called Sun-Praying Technique.

Problem Description

Many records in the book are no longer readable. From the remaining fragments, everyone can only guess that it requires holding a contest, a very difficult contest. As for what to do after the contest, they have no idea at all.

But they decided to try, even if they had to figure it out by themselves.

So when you pass by the village, you see a problem posted on a board—the only contest problem.

Maintain a sequence $a$ of non-multisets, with length $n$. Support the following two operations:

1. Given $l,r,x$, for each $l\le i\le r$, merge $x$ into $a_i$.
2. Given $l,r$, let $S$ be the set obtained by merging all $a_i$ for each $l\le i\le r$ together, and output the sum of all elements in $S$.

You look at the computer you carry with you and decide to come and support (za) the event.

Then, good luck!

Input Format

At the beginning of the input, there is a string of length $2$. See the section Hint. It can help you quickly judge the properties of the testdata.

The second line contains two positive integers $n,m$, representing the length of the set sequence and the number of operations. The initial sets $a_1,a_2,\cdots,a_n$ are all empty.

In the next $m$ lines, each line starts with three positive integers $op,l,r$ as described. If $op=1$, then this line also contains a positive integer $x$ as described.

Output Format

For each input line with $op=2$, output one positive integer, in order, representing the result of each query.

II
11 13
1 6 8 4
2 7 7
2 2 4
2 11 11
1 1 11 2
1 5 5 5
1 8 11 3
2 1 8
1 5 10 2
1 2 4 4
2 2 10
2 3 9
2 2 4

4
0
0
14
14
14
6

Hint

This problem uses bundled tests.

For $100\%$ of the data, it is guaranteed that $1\le n,m,x\le10^5,1\le l\le r\le n$.

Subtask 1: For $10\%$ of the data, it is guaranteed that $1\le n,m,x\le100$.

Subtask 2: For $10\%$ of the data, it is guaranteed that $1\le n,m,x\le10^5$, and the string in the first line is PP.

Subtask 3: For $20\%$ of the data, it is guaranteed that $1\le n,m,x\le10^5$, and the string in the first line is IP.

Subtask 4: For $30\%$ of the data, it is guaranteed that $1\le n,m,x\le10^5$, and the string in the first line is PI.

Subtask 5: For the last $30\%$ of the data, there are no special restrictions.

The function of the string in the first line: this string contains two characters, each being P or I. If the first character is P, then all update operations satisfy $l=r$; if the second character is P, then all query operations satisfy $l=r$. An I in the corresponding position means there is no restriction.

Without a doubt, you won first place.

“Alright, now we will announce the winners!”

“Third place: ...” (applause, award)

“Second place: ...” (applause, award)

“First...”

The host suddenly stops, rubs his eyes, then looks at the sky in panic. People nearby curiously crowd over to look at the list in the host’s hand. They see that the first-place name is violently twisting and reconstructing in an indescribable way, repeatedly switching between two different forms.

A few characters suddenly appear above the list. As the characters gradually become clear, people see four meaningless characters that look very impatient: “div1”.

At this moment, the change in the first-place name also stabilizes—as if one side voluntarily withdrew.

In the end, the name is fixed into five letters: “David”. This is not the fake name you casually reported.

Together with the host, people look toward the sky again. A child who looks about five or six years old comes running unsteadily. “I am first place!” he laughs happily. His mother—the Sun God—stands in the distance, looking at that small figure with a loving expression.

A red sun bursts out from the horizon.

Translated by ChatGPT 5