最弱

學園都市邪惡的實驗計畫走漏了風聲，被學園都市中最不幸最倒楣的學生，上條當麻最弱所發現了，身為愛多管閒事的好人，當麻決定要前去阻止絕對能力進化實驗。

雖然身為LV0的無能力者，當麻卻有著奇異未知，無法被當代技術判定的能力；幻想殺手。被當麻所碰觸的東西，其原有的超能力會被減弱甚至是被消除，利用此能力，能讓上條當麻消極地打敗所有攻擊他的敵人！下一場實驗開始前，當麻趕在一方通行面前試圖阻止他的攻擊，要保護御版妹妹的安全，一個最強與最弱的對決就展開。雙方在接下來的數個回合內有許多激烈的交鋒，一方通行使用$N$種不同的向量瘋狂的攻擊，被躲在一旁的實驗員默默記錄著個重要的時刻！他使用$S_i$表示第$i$個向量攻擊的強度，每一次的紀錄如下：

1 x d，把向量$S_x$的強度設定為$d$。
2 L R，受到幻想殺手影響，把向量$S_L,S_{L_+1}\cdots S_R$的強度減弱為設定為原來數值開根號後取整數。
3 L R d，上條當麻受到攻擊，損傷程度等於，$S_L,S_{L_+1}\cdots S_R$中小於等於$d$的攻擊強度總和。

根據這份紀錄，你能還原當時互相交戰的狀況嗎？

輸入說明

只有一筆測資，第一行有兩個整數$N,M$，表示向量的數量，以及依序有$M$條戰鬥紀錄。接下來有$M$行，每行的指令同題目敘述表示。

$1\leq N,M\leq 10^5$
$1\leq S_i \leq 10^9$
$1\leq d\leq 10^9$
$0\leq L\leq R\leq N-1$
$0\leq x\leq N-1$

輸出說明

對於每個第$3$號種類的指令，輸出一個數字表示攻擊強度總和，並換行。

範例輸入

15 10
18 54 23 54 87 59 31 48 65 15 76 21 65 68 32
1 2 7
2 4 12
2 4 12
3 1 13 7
3 0 14 32
3 0 14 54
2 4 12
1 8 9
2 4 12
3 1 13 3

範例輸出

Judge Setting

run-time limit: 1100 ms
memory limit: 10240000 byte
測資數量: 0