请你出一道结合dp和平衡树考察考生转换题目能力的信息学题目参考usaco金组

题目描述：

给定一个长度为n的数组a，初始时数组中的每个元素都为0。现在有q个操作，每个操作的形式为"1 x"或"2 l r"。

操作1：将a[x]的值加1。

操作2：求出区间[l, r]中每个位置的元素值的和，并输出。

现在，请你编写程序，根据给定的操作序列，输出每个操作2的结果。

输入格式： 第一行包含两个整数n和q，分别表示数组长度和操作数。 接下来q行，每行描述一个操作，格式为"1 x"或"2 l r"。

输出格式： 对于每个操作2，输出一个整数表示该操作的结果。

数据范围： 1 ≤ n, q ≤ 10^5 1 ≤ x ≤ n 1 ≤ l ≤ r ≤ n

示例： 输入： 5 5 1 1 1 2 2 1 2 1 3 2 1 5 输出： 0 1 4