Problem Statement

The city of Algorithms features a grand skyline consisting of N skyscrapers aligned in a row. The initial height of the i-th skyscraper is A i meters. The Chief Architect regularly modifies the skyline. Over the next year, Q events will occur. An event is a construction decree, a zoning law, or an audit query: Type 1 (Zoning Law) — 1 L R X : No building in the range [L, R] may exceed height X. Every building taller than X is demolished down to exactly X. Formally, A i = min(A i , X) for all L ≤ i ≤ R. Type 2 (Construction Decree) — 2 L R Y : Crews add Y meters to every building in the range [L, R]. Formally, A i = A i + Y for all L ≤ i ≤ R. Type 3 (Audit Query) — 3 L R : Report the total sum of the heights of all buildings in the range [L, R]. Input Format: The first line contains two integers N and Q . The second line contains N integers A 1 , A 2 , …, A N . Each of the following Q lines describes one event in chronological order. Each line begins