Ironforge

$\space \space$*A finer blade has never been crafted by my hand. I only hope it does not come too late... A gryphon rider brought word to me only moments ago... ...King Terenas is dead, lads. Killed by Arthas' own hand. You have my condolences. And though they won't bring back your king... Perhaps this blade will administer some justice, return some semblance o' order to the turmoil that grips your kingdom. Terenas was a good man, wise and just. Know that the dwarves o' Ironforge will mourn his passing.*

$\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space $ *—— 《Birth of Ashbringer》*

The subway of Ironforge can been seen as a chain of $n \geq 2$ vertices. In other words, for each $i=1,2,3...n-1$, there is an edge between vertex $i$ and vertex $i+1$.

There is a number $a_i(1 \leq i\leq n)$ on vertex $i$ and a prime number $b_i(1\leq i < n)$ written on the edge between vertex $i$ and vertex $i+1$.

You may start a trip on some vertex with an empty bag. When you are on vertex $i$, you can put all prime factors of $a_i$ into your bag. You can walk through an edge with prime number $p$ written on it if and only if you already have $p$ in your bag. You are allowed to pass each vertex and each edge **multiple times**.

You need to answer $m$ queries. In each query you are given two numbers $x,y$. You need to answer whether you can reach vertex $y$ if you start your trip on vertex $x$ by the subway of Ironforge.

The input consists of multiple test cases.

The first line contains an integer $T\ (1\leq T\le 3)$ denoting the number of test cases.

For each test case, the first line contains two integers $n$ and $m$ $(2\leq n,m \leq 2\times 10^5)$, denoting the number of vertices and the number of queries.

The second line contains $n$ integers $a_i\ (1\leq i\leq n, 1 \leq a_i\leq 2\times 10^5)$.

The third line contains $n-1$ integers $b_i\ (1\leq i < n, 2 \leq b_i\leq 2\times 10^5)$.

Following $m$ lines describe the queries. Each line contains two integers $x,y\ (1\leq x,y\leq n)$.

For each query, output one line containing "Yes" if its possible to reach vertex $y$ from vertex $x$ and "No" otherwise.

1
5 5
7 1 6 6 14
7 2 3 2
1 2
1 4
3 5
5 1
3 1

Yes
No
Yes
Yes
Yes

2022“杭电杯”中国大学生算法设计超级联赛（8）