Background

Yue closed the window and pulled the curtain.

Sure enough, she still could not remember.

She vaguely remembered doing something like this with someone.

She lay on her back, holding a wooden slip in her hand.

“How on earth can I have a ‘past’...”

She closed her eyes.

“The memories from before I was 6... how can I get them back?”

Problem Description

Yue is looking for her memories. Suddenly, she arrives on a tree with $n$ nodes. Each edge on the tree has its own edge weight, and each node has its own node weight.

“If I gather all my experiences together, can I fully restore them...”

Yue slowly walks from one node on the tree to another, but she finds nothing. However, she does not know that Qi has been watching the road she took from afar.

Qi notices that Yue, throughout the whole trip, never walked back along the same way. He wants to multiply together the edge weights of every edge Yue has walked through, but unfortunately he finds a number he has never seen in his life.

“Why would this happen?”

Qi thinks Yue appeared on the tree suddenly, so the starting node must be suspicious! He multiplies in the node weight of that initial node...

Suddenly, a red light of the higanbana (pinyin: bǐ àn huā) lights up! The world becomes quiet again.

Yue sees the words Qi left behind, but she cannot read any memories of the past from them. Now, you need to help her decide: if she gathers all her experiences together, can she fully restore the past? We say that one path of Yue can “restore the past” if and only if the product left by Qi is an integer.

Formal Statement

Given a tree with $n$ nodes and $q$ queries. Each query gives two integers $x,y$, asking whether the product of the edge weights on the simple path between endpoints $x$ and $y$ in the tree, multiplied by the node weight of node $x$, is an integer.

Input Format

The first line contains two positive integers $n$ and $q$, meaning the tree has $n$ nodes labeled $1\sim n$, and Yue walks $q$ paths on the tree.

The next line contains $n$ non-negative integers, where $a_i$ is the node weight of node $i$.

The next $n-1$ lines each contain two positive integers $u,v$ and a non-negative real number $w$, meaning there is an edge between $u$ and $v$ with edge weight $w$.

The next $q$ lines each contain two positive integers $x,y$, meaning Yue starts from node $x$ and walks to node $y$.

Output Format

For each query of Yue, output one string per line. If Yue can successfully restore her past, output Yes; otherwise output No.

5 3
1 2 3 4 5
1 2 0.1
2 3 0.20
3 4 0.5
2 5 0.99
1 5
1 4
4 3

No
No
Yes

Hint

Sample Explanation

From the input, we can obtain the following figure:

For the first query $(1,5)$, the edge weights Yue passes through are $0.1$ and $0.99$, and the node weight of the starting node $1$ is $1$. Since $1\times0.1\times0.99=0.099$ is not an integer, output No.

The same applies to the remaining two queries.

Constraints

This problem uses bundled testdata.

Special Property $\text{A}$: The tree is guaranteed to degenerate into a chain.

Special Property $\text{B}$: The tree is guaranteed to be generated randomly (that is, for each node, its parent is chosen at random).

Special Property $\text{C}$: $w\in\{0.1,0.3,0.5,0.7,0.9\}$ is guaranteed.

Special Property $\text{D}$: $w\in\{0.1,0.2,0.3,0.4,0.6,0.7,0.8,0.9\}$ is guaranteed.

Special Property $\text{E}$: $w\le2$ is guaranteed and $w$ has at most $1$ digit after the decimal point.

For $100\%$ of the data, $1\le n,q\le2\times10^5$, $0\le a_i\le10^9$, $0\le w\le10^4$, $1\le u,v,x,y\le n$, $x\ne y$, and $w$ has at most $4$ digits after the decimal point.

Translated by ChatGPT 5