這天，巴已己、巴已已、和巴已巳結伴去一座小島上旅行。他們在島上發現了一道長達五十萬公里的大斷層，每天都在活躍著，而且斷層的活動居然是他們一念之間就可以掌控的！
巴已己說，要有山，便有了山。他在心裡想好兩個數字 $a, b$，對於斷層起始處開始算 $x$ 公里的位置，該處的海拔會被抬升到至少 $ax + b$ 公尺。
巴已已說，山不該如此高聳，於是巴已已一記手刀，山峰被夷平了。他手刀將會砍在海拔為 $c$ 的地方，所有海拔高度高過 $c$ 公尺的地方都會被巴已已大手一揮砍成 $c$ 公尺。
在巴已己和巴已已互鬥的過程中，巴已巳想實地考察斷層活動。喜歡登高山的他會走過斷層中間的一小段，並紀錄下海拔最高的位置。
每一天，他們在旅行日記上記下當天是巴已己造出了一座山、巴已已揮出一記手刀、還是巴已巳出門進行了一次考察。旅程結束之後，巴已巳發現他的斷層考察紀錄居然弄丟了！好在他們的旅行日記還保留著，你能根據他們的旅行日記幫巴已巳還原出他的考察紀錄嗎？
（以上情節純屬虛構，如有雷同實為巧合）
請你維護一個序列。這個序列一開始都是 $0$，請支援 $Q$ 次操作：
第一行有兩個正整數 $N, Q$，代表斷層長度和旅行日記上有幾筆紀錄，也就是序列長度和接下來的操作數量。
接下來的 $Q$ 行，每行代表一次操作，形如：
1 a b：巴已己造出了一座山，序列所有數字跟直線 $ax + b$ 取 $\max$2 c：巴已已砍出一記手刀，序列所有數字跟常數 $c$ 取 $\min$3 l r：巴已巳出門考察斷層活動，詢問序列中區間 $[l, r]$ 的最大值對於巴已巳每次的斷層考察，請回答那次考察紀錄下的最高海拔（公尺）。
換句話說，對於每次的第三種詢問，請輸出詢問結果。
5 12 1 2 4 3 1 5 3 1 3 3 4 4 1 -3 16 3 1 5 3 1 3 3 4 4 2 11 3 1 5 3 1 3 3 4 4
14 10 12 14 13 12 11 11 11
2 8 1 2 0 3 1 1 3 2 2 2 3 1 1 0 1 1 -1 3 1 1 3 2 2
2 4 2 3
10 20 1 -453353365212 674873070581144417 1 -85160889177 269787146516281711 1 -930606453139 825606402140251908 3 1 2 3 3 3 1 617371516011 -624022640298407667 1 -888181834668 953248485257432197 1 715351850672 -76635650028418802 1 73081726339 -538387878798345572 2 -615715699483791915 3 4 5 3 1 4 1 -596772663595 -424950645442517140 2 -446076358334831415 1 -71965294359 -113670135348127706 3 5 6 2 -596446837547520399 1 891165226159 830876300085435778 2 -391653930343521915 3 2 3
825605471533798769 825603610320892491 -615715699483791915 -615715699483791915 -113670495174599501 -391653930343521915
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0~9 | $N, Q \leq 5000$ | 10 |
| 3 | 10~14 | 只有第一、三種操作 | 20 |
| 4 | 15~22 | $a \geq 0$ | 40 |
| 5 | 0~35 | 無額外限制 | 30 |