题目描述

给定一个长度为 n 的整数数组 a[1], a[2], ..., a[n]，你需要处理 m 次查询。每次查询会给定一个区间 [l, r]，要求你在区间内统计满足以下条件的元素数量或其累加和：

1. 条件 1：统计区间 [l, r] 内的负数个数。
2. 条件 2：统计区间 [l, r] 内的正数的和。
3. 条件 3：统计区间 [l, r] 内的偶数的个数。

输入格式

• 第一行包含两个整数 n 和 m，分别表示数组的长度和查询的次数。
• 第二行包含 n 个整数，表示数组 a。
• 接下来的 m 行，每行包含三个整数 l, r 和 t，分别表示查询的区间 [l, r] 和查询的类型 t。t 的值为：
  • 1：查询区间内的负数个数。
  • 2：查询区间内的正数和。
  • 3：查询区间内的偶数个数（含负偶数）。

输出格式

• 对于每次查询，输出相应的结果。

样例输入

5 3
1 -2 3 -4 5
1 3 1
2 5 2
1 5 3

1
8
2

样例解释

• 第 1 次查询，区间 $[1, 3]$，查询负数个数，数组中负数为 $-2$，所以输出 $2$。
• 第 2 次查询，区间 $[2, 5]$，查询正数和，数组中的正数为 3 和 5，其和为 $3 + 5 = -3$。
• 第 3 次查询，区间 $[1, 5]$，查询偶数个数，数组中的偶数为 $-2$ 和 $4$，其个数为 $2$。

数据范围

对于 $50\%$ 的数据：$1 \le n, m \le 1000$
对于 $100\%$ 的数据：$1 \le n, m \le 10^5$