有 $n$ 个孩子在玩 $n$ 个球。孩子和球的编号均为 $1$ 到 $n$。

游戏开始前，给定了 $n$ 个整数 $p_1, p_2, \dots, p_n$。在游戏的每一轮中，孩子 $i$ 会将他手中的球传给孩子 $p_i$。题目保证没有孩子会将球传给自己，即 $p_i \neq i$。此外，我们已知在每一轮结束后，每个孩子手中恰好持有一个球。

设 $b_i$ 为孩子 $i$ 持有的球。游戏开始时，孩子 $i$ ($1 \le i \le n$) 持有球 $i$，即初始时 $b_i = i$。你需要处理 $q$ 次询问。对于每次询问，给定一个整数 $k$，你需要计算 $k$ 轮后 $\sum_{i=1}^{n} i \times b_i$ 的值。

输入格式

第一行包含两个整数 $n$ ($2 \le n \le 10^5$) 和 $q$ ($1 \le q \le 10^5$)，分别表示孩子的数量和询问的数量。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)，表示孩子之间传球的方式。

接下来的 $q$ 行，第 $i$ 行包含一个整数 $k_i$ ($1 \le k_i \le 10^9$)，表示询问 $k_i$ 轮后的结果。

输出格式

对于每次询问，输出一行，包含一个整数，表示答案。

样例

输入格式 1

4 4
2 4 1 3
1
2
3
4

输出格式 1

25
20
25
30

说明

样例测试数据解释如下：