All Tracks Algorithms String Algorithms Problem

Monk is playing with a Tree T rooted at node 1 consisting of N nodes. Each node has a digit written on it ranging from 0 to 9 inclusive. He has an interesting task for you as follows:

You are given a prime number K that is co-prime to \(10\) and Q queries to answer. In each query, you shall be given 2 numbers i and j. It is guaranteed that for each query, node i shall be an ancestor of node j or \(i = j\). Now, you need to report if the number formed by writing out the the digits from left to right of each node on the path from i to j inclusive, is divisible by K.

Writing out the digits from left to right implies that the digit written on node i shall be the most significant digit of the number thus formed, and the one written on node j shall be the least significant one. For more, refer to the sample explanation.

Can you do it ?

Input Format :

The first line contains 3 space separated integers denoting N, K and Q.

The next line contains N space separated integers. where the \(i^{th}\) integer is \(A[i]\) and denotes the digit written on node i.

The next line contains \(N-1\) space separated integers, where the \(i^{th}\) integer denotes the parent of node \(i+1\).

Each of the next Q lines contains 2 space separated integers, denoting the parameters of the \(i^{th}\) query.

Output Format :

For the \(i^{th}\) query, print "YES" (without quotes) if the number formed by the parameters of the \(i^{th}\) is divisible by K, else print "NO" (without quotes).

Constraints :

\( 1 \le N \le 2 \times 10^5 \)

\( 2 \le K \le 2 \times 10^7\). It is guaranteed that K is a prime number and is co-prime to \(10\)

\( 0 \le A[i] \le 9 \)

\( 1 \le Q \le 2 \times 10^5 \)

\( 1 \le parent[i] < i \)

Note :

The number thus formed may contain leading zeros.