You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

校园小径的积水监测

Description

校园里有一条长为 n 米的直形小径，小径被等分为 n 个 1 米长的路段，每个路段有一个初始的积水深度 (a_i)（单位：厘米，(1 <= i <= n)）。 接下来会有 m 次操作，每次操作分为两种类型：更新操作：格式为 "1 l r v"，表示给第 l 到第 r 个路段的积水深度各增加 v 厘米（(1 <= l <= r <=n)，v 为整数，可正可负）。查询操作：格式为 "2 l r"，表示查询第 l 到第 r 个路段的积水深度总和（(1 <= l <= r <= n)）。由于近期降雨频繁，操作次数可能较多，需要你设计一个高效的程序来处理这些操作。

Input

第一行包含两个整数 n 和 m（(1 <= n, m<=10^5)）。第二行包含 n 个整数 (a_1, a_2, \ldots, a_n)（(0 \leq a_i \leq 10^3)）。接下来 m 行，每行描述一次操作，格式如题目所述

Output

对于每个查询操作，输出对应的积水深度总和。

Limitation

1s, 1024KiB for each test case. 提示 直接模拟每次更新和查询操作可能会超时，建议使用前缀和的优化技巧（如差分法）。