该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小红有 $n$ 个包，每个包的容量是 $b_i$。

小红有$m$ 次操作，分两种：

$1.$ 向第 $l\sim r$ 个包内放入价值为 $w$ 的物品

$2.$ 查询第 $x$ 个包内物品价值之和。

如果放入的时候背包已满，则扔掉最早加入的物品。

输入格式

第一行两个整数 $n,m$

接下来一行 $n$ 个整数 $b_1\sim b_n$

接下来 $m$ 行：

如果 $opt=1$ ，则输入 $l,r,w$。

如果 $opt=0$，则输入 $x$。

输出格式

每次 $opt=0$ 输入一行一个答案。

Samples

5 5
4 1 2 6 3
1 1 5 3
1 2 4 7
0 2
1 3 5 8
0 3

7
15

提示

对于 $30\%$ 的数据：$1\leq n,m\leq 1000$

对于额外 $30\%$ 的数据：$1\leq b_i\leq 5$

对于 $100\%$ 的数据：$1\leq n,m,b_i,w\leq 10^6$，$1\leq l\leq r\leq n$，$1\leq x\leq n$