冰冰的 GCD

题号：NC281984
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定三个排列 $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$ 以任意顺序排列。

输入描述:

第一行输入两个正整数  分别表示排列大小和询问次数。

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

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

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

接下来  行，每行一个正整数  表示询问。

输出描述:

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

示例1

输入

复制

输出

复制