Migrated from Lutece 3110 逆转摄影

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：链表

是时候，让我们的大律师——成步堂龙一，和他一路以来遇到的朋友们拍照留念了。

成步堂共有包括他自己在内的 $n$ 名朋友需要拍照，其中第 $i$ 个人的身份编号为 $i$，身高为 $h_i$。

他们计划将在 $q$ 个不同的有纪念意义的地方拍照。在每一个地方，所有人将会按照某个顺序依次到达。

具体地，我们用一个长度为 $n$ 的排列 $\{p_n\}$ 来描述在某个地点的拍照情况，它表示身份编号为 $p_1$ 的人第一个到达，身份编号为 $p_2$ 的人第二个到达，依此类推。

每当有人来到拍照场所时，他们便会拍下一张新的照片，这就意味着在某个场所，一共会拍下 $n$ 张不同的照片。

为了使拍照时的队列更有序，他们规定在每次拍照时，当前到达的所有人必须按照身份编号顺序从小到大站成一排。

同时定义一张照片的 无序度 为其中相邻两人间身高差的平方之和，现在成步堂想要知道在每个拍照场所，他们拍下的 $n$ 张照片的 无序度 之和是多少。

请你帮他快速地算出上述问题的答案，不然这位刺猬头先生就要再喝一杯“混调第 102 号”了。

Input

输入的第一行包括两个正整数 $n,q$，分别表示需要拍照的人数以及不同的拍照地点数。

第二行包括一个长为 $n$ 的序列 $\{h_n\}$，其中 $h_i$ 为身份编号为 $i$ 的人的身高。

第三行包括一个长为 $n$ 的排列 $\{p_n\}$，表示初始时人们的到达顺序（意义如题目描述中所述）。

在接下来的 $q$ 行中，每一行有一个正整数 $k$，表示在该拍照地点，人们的到达顺序 $\{p_n\}$ 相较于上一次进行了循环左移 $k$ 次的操作。

注意一个排列 $p_1,p_2,\cdots,p_{n-1},p_n$ 循环左移一次后得到的排列为 $p_2,p_3,\cdots,p_n,p_1$，循环左移 $k$ 次同理。

Output

输出共包括 $q$ 行，每行一个整数，表示在每个拍照地点，拍下的所有照片的 无序度 之和。

Samples

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

10
10
21

Constraints

$1\le n\le 1\times 10^5,1\le q\le 200,1\le h_i\le 10^4,1\le k\le 10^9$

Resources

2024 UESTC ICPC Training for Data Structures