题目描述

D 君是潜伏在 Mars 星的间谍，D 君携带着从母星带来的扰乱神器，用于扰乱 Mars 星的晶体防御序列。Mars 星的晶体防御序列由 $2^n$ 块晶体组成，第 $i$ 块晶体的能量为 $p_i$。晶体防御序列的扰乱度定义为序列中的逆序对数，由于 Mars 星的晶体存在自适应能力，如果某个固定的防御序列持续过久，该序列的扰乱度就不再对晶体防御序列造成威胁了。因此 D 君对 Mars 星的晶体防御序列进行了 $m$ 次扰乱，第 $i$ 次扰乱可以用 $q_i, l_i, r_i$ 表示：

• 将晶体防御序列分为 $2^{q_i}$ 个大小为 $2^{n-q_i}$ 的块。
• 选择第 $l_i$ 到第 $r_i$ 个块。
• 对于每个选择的块, 将其翻转。

D 君想知道每次扰乱操作后, 整个晶体防御序列的扰乱度。

输入格式

第一行为两个正整数 $n, m$。

第二行 $2^n$ 个整数 $p_1, p_2, \cdots p_{2^n}$，为给定的晶体防御序列。

接下来 $m$ 行，每行 3 个非负整数 $q_i, l_i, r_i$，表示一次扰乱操作。

输出格式

$m$ 行，每行一个整数，为每次操作后晶体防御序列的扰乱度。

样例

样例输入1

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

样例输出1

9
10
8
7
15
14
8
14
12
17

样例2

c.in
c.out

数据范围与提示

对于所有数据，$1 \leq n \leq 20, 1 \leq p_i \leq 2^n, 1 \leq m \leq 10^5, 0 \leq q_i < n, 1 \leq l_i \leq r_i \leq 2^{q_i}$