I. Another task on parentheses sequences
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A correct parentheses sequence is a string that consists only of the characters «(» and «)», from which it is possible to obtain a valid arithmetic expression by inserting the characters «+» and «1». For example, «», «(())» and «()()» are correct, while «)(» and «(()» are not correct parentheses sequences. A simple parentheses sequence is defined as a string made up of the characters «(» and «)».

We will define the correctness of a parentheses sequence as the maximum length of its correct parentheses subsequence. For example, consider the string «()())((())()». Its correct subsequences include, for example, the following: «$$$\color{red}{\underline{\color{red}{\text{()}}}}$$$())((())()», «$$$\color{red}{\underline{\color{red}{\text{(}}}}$$$)$$$\color{red}{\underline{\color{red}{\text{(}}}}$$$))((($$$\color{red}{\underline{\color{red}{\text{))}}}}$$$()», «$$$\color{red}{\underline{\color{red}{\text{()()}}}}$$$)$$$\color{red}{\underline{\color{red}{\text{((())}}}}$$$($$$\color{red}{\underline{\color{red}{\text{)}}}}$$$», as well as others (but the problem statement is too short to list them all). As can be seen, a subsequence is our sequence from which zero or more elements have been removed, and the order of the remaining elements has not changed. For this sequence, the correctness will be equal to $$$10$$$ (the last of the provided subsequences has this length).

Given $$$n$$$ initially empty parentheses sequences. There are $$$q$$$ queries of two types:

  • «$$$1 \ \ell \ r \ x$$$» — append $$$|x|$$$ parentheses to the sequences in the segment $$$[\ell, r]$$$. If $$$x \gt 0$$$, then opening parentheses, if $$$x \lt 0$$$ — closing parentheses.
  • «$$$2 \ \ell \ r$$$» — output the sum of the correctness of the sequences in the segment $$$[\ell, r]$$$.
Input

The first line of input contains two numbers $$$n$$$, $$$q$$$ ($$$1 \le n \le 5 \cdot 10^5$$$, $$$1 \le q \le 5 \cdot 10^5$$$) — the number of empty parentheses sequences and the number of queries.

In the next $$$q$$$ lines, numbers are entered according to the format:

  • Four numbers «$$$1 \ \ell \ r \ x$$$» are entered, ($$$1 \le \ell,r \le n$$$, $$$1 \le |x| \le 10^6$$$)
  • Three numbers «$$$2 \ \ell \ r$$$» are entered, ($$$1 \le \ell,r \le n$$$)
Output

For each query of the second type, output the sum of the correctness of the sequences in the corresponding segment.

Scoring
№Additional constraintsPointsRequired groupsComment
$$$n$$$$$$q$$$
$$$0$$$————Tests from the problem statement
$$$1$$$$$$n=1$$$—$$$6$$$——
$$$2$$$——$$$15$$$—$$$\ell_i = r_i$$$ in queries of the first type
$$$3$$$——$$$13$$$—The balance$$$^{\text{∗}}$$$ of all parentheses sequences does not fall below $$$0$$$
$$$4$$$$$$n \le 10^4 $$$$$$q \le 10^4 $$$$$$7$$$——
$$$5$$$$$$n \le 5 \cdot 10^4 $$$$$$q \le 5 \cdot 10^4 $$$$$$5$$$$$$4$$$—
$$$6$$$$$$n \le 10^5 $$$$$$q \le 10^5 $$$$$$14$$$$$$5$$$—
$$$7$$$$$$n \le 2 \cdot 10^5 $$$$$$q \le 2 \cdots 10^5 $$$$$$10$$$$$$6$$$—
$$$8$$$$$$n \le 3 \cdot 10^5 $$$$$$q \le 3 \cdot 10^5 $$$$$$8$$$$$$7$$$—
$$$9$$$$$$n \le 4 \cdot 10^5 $$$$$$q \le 4 \cdot 10^5 $$$$$$8$$$$$$8$$$—
$$$10$$$——$$$14$$$$$$0-9$$$—

$$$^{\text{∗}}$$$The balance of a parentheses sequence is defined as the number of opening parentheses minus the number of closing parentheses.

Example
Input
1 11
1 1 1 1
2 1 1
1 1 1 -1
2 1 1
1 1 1 1
1 1 1 -2
1 1 1 3
1 1 1 -2
1 1 1 1
1 1 1 -1
2 1 1
Output
0
2
10
Note

The queries in the example form a string explaining the correctness.