在遙遠的魔法王國裡，王都城牆上鑲嵌著 $n$ 顆排成一列的魔法石，由左開始數第 $i$ 顆魔法石編號為 $i$，屬性為 $a_i$ 且蘊含 $c_i$ 的魔力值（魔力值可以為負）。相傳這些魔法石是初代大法師為了抵禦外族入侵，花費了 8 天 8 夜煉製而成的嘔心瀝血之作，在適當的使用下可以施放出高強度的咒語。

身為現任的首席大法師，你需要善用這些魔法石來守護王國。魔法石的使用有特殊的規則：在施放咒語時，你可以從中挑選一些魔法石（並保有原本的順序），若被挑選的魔法石中，任意相鄰兩顆魔法石的屬性皆不相同（假設挑選了 $m$ 顆魔法石，編號依序為 $p_1 < p_2 < \ldots < p_m$，則對於所有 $1 \le i < m$，滿足 $a_{p_i} \neq a_{p_{i+1}}$），咒語才可以成功施放，其強度為該序列的魔力值總和 $\sum_{i = 1}^ m c_{p_i}$（在此定義下，挑選 0 顆與 1 顆任意的魔法石永遠能夠成功施放咒語）。

然而，由於魔力的擾動，魔法石的屬性與魔力值隨時都在變化；同時因為魔法石非常不穩定，你時常只能使用一段連續區間內的魔法石來施放咒語。接下來發生了 $q$ 個事件，每個事件的類型如下：

• 1 p x : 第 $p$ 顆的魔法石的屬性變為 $x$。
• 2 p y : 第 $p$ 顆的魔法石的魔力值變為 $y$。
• 3 l r : 外族入侵！你需要使用編號介於 $[l, r]$ 的魔法石，施放出強度最大的咒語。

對於每個第三種的事件，輸出一個值，表示能施放的最大咒語強度。