Description

  「啊?數學平均五十分?這麼高?」段考完後,我感到身體被抽空般地無力,腦子更是處於動不了的狀態。望著臺上的數學老師,頂著銀灰色的頭髮,實在很難想像這樣的人還不到四十,更難以想像一副和藹的面容,居然懷著一身唬爛絕技。
  「我就說吧,數學很簡單。」聽到後因為計算錯誤只剩 25 分的我差點沒破防,不禁低下頭思考著未來,卻得不到任何結論。
  如果這時候能有哆啦A夢就好了,用個時光回到過去讓自己改變解題策略,會寫的都把它寫到對至少也能及格啊!想到這裡,不禁覺得自己連大雄都不如。
  就在這時,哆啦A夢還真的出現了,只是他看起來怪怪的,一出現便掏出如果電話亭,不知道想幹嘛但感覺很恐怖,所以我很快便把他送回未來了。

  真的沒救了嗎?

  此時,數學老師出現問了我要不要打幫他打原神。「我不會打音遊。」他說,由於他唬爛的次數真的多到大概兩句話裡有三句話在唬爛,所以我很直覺地回了「唬爛啦」後才想到,真的沒什麼看過他在打音遊。幸好原神裡的音遊就是一般的下落式音遊,沒有什麼環狀的怪東西。

  然而,打完音遊,我的精神狀態並沒有變好;相反地,我變得全身無力。受不了後我倒到床上,閉上眼睛。

  刺耳的鬧鐘聲。

  醒來後,疲憊感卻不見消失,反而愈來愈強。直到要出門前,我的腳幾乎抬不起來。於是,我和我爸請求請假。在思考發生什麼事的同時,時空隧道打開了。
  「我們是時空警察。你因涉嫌違反時空旅行相關規定而被逮捕。」我感到困惑,接著馬上想起昨天的事。「沒有,我沒有!我只是在阻止他...」「少囉唆!」在昏倒之前,我似乎聽見了我爸在說話,然而,聽不清楚。

  再次醒來,我身處亞空間中。「讓我解釋,昨天那個...」猛地一陣電流立即竄過我的身體,感到一陣劇痛。「別吵。」一句話讓我氣得牙癢癢。
  為了掙脫,我在下船時故意踩空,墜入了亞空間。

  剎那間,我看到了五彩的時空分支呈一排出現在眼前,同時,耳邊響起細細聲響:

  挑一個,進去吧。
  他是這麼說的。

  然而,怎麼做?我發現,每個時空具有它的能量 $E$,可以轉換成它的記憶 $m$ 和它的顏色 $c$ 表示,$E = mc2$,但是這些時空數量過於龐大,我無法一次處理全部。

  於是,我在這請求你幫我一個忙:寫一個程式,模擬一排的時空,並依照我的要求在特定位置插入特定記憶、特定顏色的一堆時空。對,是一堆,可能有很多很多個。
  要求還沒完,因為它們會變,所以希望也可以實作一個功能:修改特定位置時空的記憶或者顏色。
  模擬時我也會需要特定區間的總能量,一樣在我要求時給我答案就好了。

  拜託了!

Input Format

第一行有一個數 $Q$ ,代表接下來有 $Q$ 筆操作。
接下來有 $Q$ 行,每行的第一個數 $t$ 會告訴你要進行什麼操作。
當 t = 1 代表你要在特定位置插入一堆時空。這時會有四個數 $x, m, c, n$ 分別代表插入後的時空的起始位置、它們的記憶、顏色以及數量。
當 t = 2 代表你要修改特定位置的記憶和顏色,這時會有三個數 $x, m, c$ 分別代表要修改的位置、新的記憶和新的顏色。
當 t = 3 代表你要查詢某個範圍的能量和,這時會有兩個數 $l, r$ 代表要查詢第 $l$ 個到第 $r$ 個時空的能量和。

$Q \leq 4\times105$
$1\leq x$ 且保證 $x$ 不超過當時時空的總數 + 1
$1\leq l \leq r$ 且保證 $l,\ r$ 不超過當時時空的總數
$0 < m,\ c,\ n \leq 109$
保證第一次操作會是插入

Output Format

請對於每筆 3 操作輸出一行,代表該區間的能量總和。
結果可能會很大,請將輸出模 $109+7$

Sample Input 1

3
1 1 2 3 10
2 5 3 2
3 3 7

Sample Output 1

84

Sample Input 2

6
1 1 2 3 10
1 3 5 4 10
2 9 1 6
2 2 6 7
3 1 20
3 2 13

Sample Output 2

1212
1068

Hints

沒意外的話這會是最好想的 C 部份題
不要管劇情中的怪異之處,我亂唬爛的

Problem Source

TopCoder

AaW
學弟電爛我了

User's AC Ratio

75.0% (3/4)

Tags

Problem Setter

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~6 $Q \leq 100$ 且 $n = 1$ 5
3 7~16 $Q \leq 8000$ 10
4 17~36 $n = 1$ 30
5 0~66 無其他限制 55

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 524288 65536 1 5
1 5000 524288 65536 1 5
2 5000 524288 65536 2 5
3 5000 524288 65536 2 5
4 5000 524288 65536 2 5
5 5000 524288 65536 2 5
6 5000 524288 65536 2 5
7 5000 524288 65536 3 5
8 5000 524288 65536 3 5
9 5000 524288 65536 3 5
10 5000 524288 65536 3 5
11 5000 524288 65536 3 5
12 5000 524288 65536 3 5
13 5000 524288 65536 3 5
14 5000 524288 65536 3 5
15 5000 524288 65536 3 5
16 5000 524288 65536 3 5
17 5000 524288 65536 4 5
18 5000 524288 65536 4 5
19 5000 524288 65536 4 5
20 5000 524288 65536 4 5
21 5000 524288 65536 4 5
22 5000 524288 65536 4 5
23 5000 524288 65536 4 5
24 5000 524288 65536 4 5
25 5000 524288 65536 4 5
26 5000 524288 65536 4 5
27 5000 524288 65536 4 5
28 5000 524288 65536 4 5
29 5000 524288 65536 4 5
30 5000 524288 65536 4 5
31 5000 524288 65536 4 5
32 5000 524288 65536 4 5
33 5000 524288 65536 4 5
34 5000 524288 65536 4 5
35 5000 524288 65536 4 5
36 5000 524288 65536 4 5
37 5000 524288 65536 5
38 5000 524288 65536 5
39 5000 524288 65536 5
40 5000 524288 65536 5
41 5000 524288 65536 5
42 5000 524288 65536 5
43 5000 524288 65536 5
44 5000 524288 65536 5
45 5000 524288 65536 5
46 5000 524288 65536 5
47 5000 524288 65536 5
48 5000 524288 65536 5
49 5000 524288 65536 5
50 5000 524288 65536 5
51 5000 524288 65536 5
52 5000 524288 65536 5
53 5000 524288 65536 5
54 5000 524288 65536 5
55 5000 524288 65536 5
56 5000 524288 65536 5
57 5000 524288 65536 5
58 5000 524288 65536 5
59 5000 524288 65536 5
60 5000 524288 65536 5
61 5000 524288 65536 5
62 5000 524288 65536 5
63 5000 524288 65536 5
64 5000 524288 65536 5
65 5000 524288 65536 5
66 5000 524288 65536 5