G. Photograph
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Graduation season is approaching and it's time to take commemorative photos.

There are $$$n$$$ students in Bob's class, each assigned with a unique student number from $$$1$$$ to $$$n$$$, where the height of the student numbered $$$i$$$ is $$$h_i$$$. They want to take photos at the school gate and $$$q$$$ more memorable places. For each place, students will arrive in a known order, and, as they hope for more personal engagement, once a student arrived they take a new photo so that $$$n$$$ photos will be taken. After finishing all the $$$n$$$ photos at the place, students will go back to their dorms and set up a new time for the next place.

To make the queue orderly, every time students have to stand in a row in ascending order of their student numbers when taking a new photo, and the orderliness of the photo is defined as the sum of the squares of the height differences between every two neighbouring students in the row. Your task is to, for each place, calculate the sum of the orderlinesses of all the $$$n$$$ photos that are taken there.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n \leq 10^5, 0 \leq q \leq 100)$$$, indicating the number of students and the number of memorable places.

The second line contains $$$n$$$ integers indicating the heights of students, the $$$i$$$-th of which is $$$h_i$$$ $$$(1 \leq h_i \leq 10^4)$$$.

The third line contains $$$n$$$ pairwise distinct integers $$$p_1, p_2, \ldots, p_n$$$, ranged from $$$1$$$ to $$$n$$$, representing the student numbers in the order of their attendance at the school gate.

In the next $$$q$$$ lines, the $$$i$$$-th line contains an integer $$$k$$$ $$$(0 \leq k \le 10^9)$$$, which says that the order of attendance for students at the $$$(i + 1)$$$-th place is rescheduled from the previous order by shifting left $$$(k + lastans)$$$ times, where the $$$lastans$$$ is the sum of the orderlinesses of the $$$n$$$ photos taken at the $$$i$$$-th place.

Note that the order $$$p_1, p_2, \ldots, p_{n - 1}, p_n$$$ after shifting left once will turn to the new order $$$p_2, p_3, \ldots, p_n, p_1$$$.

Output

Output $$$(q + 1)$$$ lines, where the $$$i$$$-th line contains an integer representing the sum of the orderlinesses of the $$$n$$$ photos taken at the $$$i$$$-th place.

Example
Input
5 4
1 2 3 4 5
1 2 3 4 5
6
6
8
10
Output
10
10
13
21
36
Note

For the sample case, the order of students' attendance at each place are listed as follows:

$$$[1, 2, 3, 4, 5]$$$ $$$\to [2, 3, 4, 5, 1]$$$ $$$\to [3, 4, 5, 1, 2]$$$ $$$\to [4, 5, 1, 2, 3]$$$ $$$\to [5, 1, 2, 3, 4]$$$.