Note

We have confirmed AC with PyPy3, but the same code got TLE when submitted with Python 3. Python users are recommended to submit with PyPy3.

Problem Statement

You are given an integer sequence $A_1, A_2, \dots, A_N$ of length $N$, a positive integer $P$ ( $P$ is not necessarily prime ), and $Q$ queries.
For the $i$-th query, determine whether it is possible to choose one or more elements from $A_{L_i}, A_{L_i + 1}, \dots, A_{R_i}$ so that the product of the chosen elements modulo $P$ equals $K_i$.

Input

$N \,\, Q \,\, P$
$A_1 \,\, A_2 \,\, \ldots \,\, A_N$
$L_1 \,\, R_1 \,\, K_1$
$L_2 \,\, R_2 \,\, K_2$
$\vdots$
$L_Q \,\, R_Q \,\, K_Q$

• $1 \leq N \leq 5000$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq P \leq 5000$
• $0 \leq A_i < P \,\, (1 \leq i \leq N)$
• $1 \leq L_i \leq R_i \leq N \,\, (1 \leq i \leq Q)$
• $0 \leq K_i < P \,\, (1 \leq i \leq Q)$
• All input values are integers.

Output

Print $Q$ lines in total.
On the $i$-th line, print Yes if it is possible to choose one or more elements from $A_{L_i}, A_{L_i + 1}, \dots, A_{R_i}$ so that the product of the chosen elements modulo $P$ equals $K_i$, and No otherwise.

Sample

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

Yes
No