# 2021 年东华大学金马程序设计联赛

E. A Similar Game
PDF 题面可用

This question is similar to Move The Numbers.

A permutation of size $2^n$ is an array of size $2^n$ such that each integer from $1$ to $2^n$ occurs exactly once in this array.

An inversion in a permutation $p$ is a pair of indices $(i, j)$ such that $i>j$ and $a_i\leq a_j$. For example, a permutation $[4, 1, 3, 2]$ contains $4$ inversions: $(2, 1), (3, 1), (4, 1), (4, 3)$.

You are given a permutation $a$ of size $2^n$ and $m$ queries to it. Each query is represented by one number $t(0\leq t\leq n)$ denoting that you have to reverse the segment $[1,2^t],[2^t+1,2\times 2^t],[2\times 2^t+1,3\times 2^t],\cdots,[2^n-2^t+1,2^n]$ of the permutation.

For example, if $a = [1, 2, 3, 4, 5, 6, 7, 8]$ and a query $t=1$ is applied, then the resulting permutation is $[2, 1, 4, 3, 6, 5, 8, 7]$.

After each query you have to answer the number of inversions.

### 输入格式

There are multiple test cases in this problem. $(T\leq 12)$

In each test case,The first line contains two integers $n$ and $m$.($2\leq n\leq 17, 3\leq m\leq 10000)$.

The second line contains $2^n$ integers $a_1,a_2,\cdots,a_{2^n}(1\leq a_i \leq 2^n)$ — the elements of the permutation. These integers are pairwise distinct.

The third line contains $m$ integers $t_1, t_2,\cdots,t_m (0\leq t_i\leq n)$.

### 输出格式

For each testcase print $m$ lines denoting the answer.

### 样例

Input
2 3
4 3 2 1
1 1 0
2 3
1 4 2 3
0 1 2

Output
4
6
6
2
4
2


NaN