题目描述

D 君是潜伏在 Mars 星的间谍，D 君携带着从母星带来的扰乱神器，用于扰乱 Mars 星的晶体防御序列。Mars 星的晶体防御序列由 $2^n$ 块晶体组成，第 $i$ 块晶体的能量为 $p_i$。

晶体防御序列的扰乱度定义为序列中的逆序对数，即满足 $i<j$ 且 $p_i>p_j$ 的下标对 $(i,j)$ 的数量。

由于 Mars 星的晶体存在自适应能力，如果某个固定的防御序列持续过久，该序列的扰乱度就不再对晶体防御序列造成威胁了。因此 D 君对 Mars 星的晶体防御序列进行了 $m$ 次扰乱。第 $i$ 次扰乱用三个整数 $q_i,l_i,r_i$ 表示：

1. 将当前晶体防御序列从左到右分为 $2^{q_i}$ 个连续的块，每块包含 $2^{n-q_i}$ 块晶体，块从 $1$ 开始编号。
2. 选择第 $l_i$ 到第 $r_i$ 个块。
3. 分别将每个被选中的块内部的晶体顺序翻转，被选中块之间的先后顺序不变。

每次操作都在上一次操作得到的序列上进行。D 君想知道每次扰乱操作后，整个晶体防御序列的扰乱度。

输入格式

从文件 dr.in 中读入数据。

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

第二行包含 $2^n$ 个整数 $p_1,p_2,\ldots,p_{2^n}$，表示初始晶体防御序列。

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

输出格式

输出到文件 dr.out 中。

输出 $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

样例 1 解释

第一次操作将序列分成两个长度为 $4$ 的块，翻转第一个块后得到 $3,3,3,7,8,6,5,3$，逆序对数为 $9$。

第二次操作将当前序列分成四个长度为 $2$ 的块，翻转第二个块后得到 $3,3,7,3,8,6,5,3$，逆序对数为 $10$。

样例 2

见选手目录下的 dr/dr2.in 与 dr/dr2.ans。

该样例满足第 $3\sim4$ 个测试点的限制，其中 $n=10,m=1000$。

样例 3

见选手目录下的 dr/dr3.in 与 dr/dr3.ans。

该样例满足第 $5\sim8$ 个测试点的限制，其中 $n=20,m=10^5$，每次操作选择全部块。

样例 4

见选手目录下的 dr/dr4.in 与 dr/dr4.ans。

该样例满足第 $9\sim12$ 个测试点的限制，其中 $n=20,m=10^5$，每次操作只选择一个块。

样例 5

见选手目录下的 dr/dr5.in 与 dr/dr5.ans。

该样例满足第 $13\sim20$ 个测试点的限制，其中 $n=20,m=10^5$。

数据范围

对于所有测试数据，保证：

• $1\le n\le20$，$1\le m\le10^5$。
• $1\le p_i\le2^n$。
• $0\le q_i<n$，$1\le l_i\le r_i\le2^{q_i}$。

本题共有 $20$ 个测试点，每个测试点 $5$ 分，各测试点独立计分。

测试点编号	$n\le$	$m\le$	特殊性质
$1\sim2$	$5$	$10$	无
$3\sim4$	$10$	$1000$
$5\sim8$	$20$	$10^5$	每次操作均满足 $l_i=1,r_i=2^{q_i}$
$9\sim12$			每次操作均满足 $l_i=r_i$
$13\sim20$			无