Description

给定三个排列 $a,b,c$，$m$ 次询问一个 $x$，求 $\sum\limits_{i=x}^n \sum\limits_{j=c[\gcd(b_x,b_i)]}^n[\gcd(b_x,b_i) \mid a_j]$，其中 $[a\mid b]=\begin{cases}1&& a\mid b\\0 && a\nmid b\end{cases}$，其中 $a\mid b$ 表示 $b$ 是 $a$ 倍数，$a\nmid b$ 表示 $b$ 不是 $a$ 的倍数。

排列是指一个不重不漏地包含 $[1,n]$ 的每一个正整数的一个整数序列。

Format

Input

第一行输入两个正整数 $n,m(1\le n,m\le 10^5)$ 分别表示排列大小和询问次数。

第二行 $n$ 个正整数表示排列 $a$。

第三行 $n$ 个正整数表示排列 $b$。

第四行 $n$ 个正整数表示排列 $c$。

接下来 $m$ 行，每行一个正整数 $x(1\le x\le n)$ 表示询问。

Output

输出共 $m$ 行，对于每次询问输出一行一个整数表示结果。

Samples

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

12
12
2
1
6

Limitation

1s, 1024KiB for each test case.