背景

海边有家很受欢迎的小书店，门口有一整面“明信片墙”。店主会把来自世界各地的明信片按一排排格框贴好，游客可以站在墙前给心仪的明信片拍照或换位。为了让陈列不至于“审美疲劳”，店主会不时把某些成组的格框整体翻转（就像把一截相片胶卷拿下来倒过来再贴回去），让墙面的视觉效果焕然一新。

这面墙一共有 $2^n$ 个相邻格框，从左到右第 $i$ 个格框里放着一张明信片，标有一个整数标签 $p_i$（可把它理解为“颜色深浅值”“到店日期序号”之类的朴素编号）。 我们把整面墙的“凌乱度”定义为这一排明信片标签的逆序对数量：也就是满足 $i<j$ 且 $p_i>p_j$ 的有序对 $(i,j)$ 的个数。凌乱度越高，墙面看起来越“打破常规”。

接下来会发生 $m$ 次操作。每次操作店主会按如下方式翻动一段段“整齐的小截”：

• 先把整排明信片平均分成 $2^{q_i}$ 段，每一段长度都是 $2^{\,n-q_i}$；把这些段从左到右编号为第 $1$ 段、第 $2$ 段、……
• 选择从第 $l_i$ 段到第 $r_i$ 段这片连续区域；
• 对这一片区域里的每一段，都把段内的明信片顺序整体翻转（就像把一小截拿下来反过来再贴回去）。

店主想知道：每做完一次上述操作后，整面明信片墙的凌乱度是多少？

输入格式

• 第一行：两个正整数 $n, m$。
• 第二行：$2^n$ 个整数 $p_1, p_2, \dots, p_{2^n}$，表示初始的明信片标签序列。
• 接下来 $m$ 行：每行三个非负整数 $q_i, l_i, r_i$，表示一次操作，含义如上。

输出格式

输出 $m$ 行。第 $i$ 行是第 $i$ 次操作完成后整排明信片的凌乱度（逆序对数量）。

样例

样例输入 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

数据范围与提示

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