Repasses em cadeia

Time limit: 3000 msMemory limit: 256 MB

Uma campanha tem $n$ participantes em uma ordem fixa. O participante $i$ tem uma meta $a_i$ . Ao receber um repasse de valor $x$ , ele envia ao próximo participante exatamente $\max(0,a_i-x)$ . Todo o valor recebido é considerado no cálculo; não há outros pagamentos.

Você deve processar alterações nas metas e consultas sobre trechos da cadeia. Em uma consulta $(l,r,x)$ , somente os participantes $l,l+1,\ldots,r$ atuam: o primeiro recebe $x$ , e cada um aplica a regra acima ao valor recebido do anterior. Informe o valor enviado pelo participante . Consultas não alteram metas nem deixam valores guardados.

Input

A primeira linha contém $n,q$ ( $1\le n,q\le200\,000$ ). A segunda contém $a_1,\ldots,a_n$ (). Cada uma das próximas linhas tem um dos formatos:

Output

Para cada consulta de tipo 2, imprima o valor final em uma linha.

Samples

Sample 1

Input

Output

0
4
4

Na primeira consulta os repasses são 3, 5 e 0. Depois da alteração, os mesmos participantes enviam 3, 0 e 4.