当前没有测试数据。

Description

给定三个排列 $a,b,c$，$m$ 次询问一个 $x$，求 $g(f(x))$。

对于 $f(x)$，若排列 $b$ 中第 $x$ 个元素之后不存在满足 $\gcd(b_i,b_x)\neq 1$ 的 $b_i$（$i>x$），则 $f(x)=b_x$。 反之 $f(x)$ 的值为排列 $b$ 中第 $x$ 个元素之后第一个满足 $\gcd(b_i,b_x)\neq 1$ 的 $\gcd(b_x,b_i)$。

对于 $g(x)$，$g(x)=\sum\limits_{i=c[x]}^n[x\mid a_i]$。

其中 $[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$ 的倍数。

长度为 $n$ 的排列是一个由 $n$ 个不同整数组成的数组，这些整数从 $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

3
0
1
1
0