Vous recevez une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$. Écrivez un programme pour exécuter les requêtes suivantes :

• 0 l r x : Pour tout $l \le i \le r$, affecter $A_i$ à $\max(A_i, x)$.
• 1 l r : Afficher $\max\left(0, \max_{l \le u \le v \le r} \left(\sum_{i=u}^{v} A_i\right)\right)$.

Entrée

La première ligne contient deux entiers $N$ et $Q$, représentant la longueur de la séquence et le nombre de requêtes.

La deuxième ligne contient $N$ entiers $A_1, A_2, \ldots, A_N$, les éléments initiaux de la séquence $A$.

Les $Q$ lignes suivantes décrivent chacune une requête dans le format ci-dessus.

Sortie

Pour chaque requête de la forme 1 l r, affichez une ligne avec la réponse.

Exemples

Entrée 1

14 14
-3 2 1 -2 3 -4 3 -5 -1 -2 3 -5 1 5
1 3 9
0 1 14 -4
1 1 14
0 3 11 -1
1 2 8
0 3 10 -1
1 4 7
0 6 9 2
1 1 14
0 10 10 7
1 1 14
0 6 9 4
0 1 5 2
1 1 14

Sortie 1

3
6
7
5
18
26
39