시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 (추가 시간 없음) | 512 MB | 3 | 3 | 3 | 100.000% |
Johnny became a controller at the Road Center. His task is to investigate the effectiveness of snow removal on a certain road during a series of blizzards. The road is divided into consecutive one kilometer-long segments, numbered with consecutive integers from $1$ to $n$. Johnny quickly got to work and gathered the information on events:
Johnny pre-processed and sorted the collected data. Unfortunately, computing the answer to queries is too difficult for him. Help him! Write a program that computes the answers to queries of the Road Center.
The first line of the input contains two integers $n$ and $q$ ($ 1 \le n \le 10^9, 1 \le q \le 300\,000$) separated by a single space and denoting, respectively, the number of kilometer segments of the road and the number of events. In each of the following $q$ lines there is a description of an event of one of the following four types:
t L a b
, which means that the plow cleared in $t$-th minute a road fragment consisting of segments numbered from $a$ to $b$.t S a b s
, meaning that a sander spreads salt of quality $s$ in $t$-th minute on a road fragment consisting of segmentst ? a b
, meaning that the Road Center wants to knowt B f g
, meaning that $t$-th minute is the last minute of the previous blizzard (if it exists), and $(t+1)$-th minute is the first minute of the blizzard with intensity $ f, g $.In all events the following conditions are met: $ 1 \le t \le 10^9, 1 \le a \le b \le n, 1 \le s, f, g \le 10^9$.
In addition, the values of $t$ for consecutive events are increasing, and the first event is always of type B
.
For each event ?
print in a separate line the remainder modulo $10^9+7$ of the largest thickness of snow cover at the end of the given minute at the specified road segment.
3 4 2 B 1 2 3 ? 2 2 4 L 1 3 5 ? 1 3
3 5
The table below shows the snow coverage on each of the road segment in Sample 1 at the end of each minute. It also shows the amount of snow that fell in each minute. The numbers in bold correspond to queries.
minute | 1 | 2 | 3 | snowfall |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 0 | 0 |
3 | 3 | 3 | 3 | 3 |
4 | 0 | 0 | 0 | 4 |
5 | 5 | 5 | 5 | 5 |
Till the first query $1 \cdot 1 + 2 = 3$ milimeters of snow fell on the whole road. Between the plow passage in minute $4$ and the second \texttt{?} query additional $3 \cdot 1+2=5$ milimeters of snow fell.
1 3 1 B 1 1 2 B 3 3 3 ? 1 1
8
minute | 1 | snowfall |
---|---|---|
0 | 0 | 0 |
1 | 0 | 0 |
2 | 2 | 2 |
3 | 8 | 6 |
Till the ?
event the first blizzard took place for one minute and the second also took place for one minute.
5 5 1 B 1 2 2 S 1 3 5 3 ? 3 4 4 ? 1 1 10 ? 1 1
7 0 30
minute | 1 | 2 | 3 | 4 | 5 | snowfall |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 0 | 3 | 3 | 3 |
3 | 0 | 0 | 0 | 7 | 7 | 4 |
4 | 0 | 0 | 0 | 12 | 12 | 5 |
5 | 0 | 0 | 0 | 18 | 18 | 6 |
6 | 0 | 0 | 0 | 25 | 25 | 7 |
7 | 0 | 0 | 0 | 33 | 33 | 8 |
8 | 9 | 9 | 9 | 42 | 42 | 9 |
9 | 19 | 19 | 19 | 52 | 52 | 10 |
10 | 30 | 30 | 30 | 63 | 63 | 11 |