#P1718F. Burenka, an Array and Queries
Burenka, an Array and Queries
Description
Eugene got Burenka an array of length of integers from to for her birthday. Burenka knows that Eugene really likes coprime integers (integers and such that they have only one common factor (equal to )) so she wants to to ask Eugene questions about the present.
Each time Burenka will choose a subsegment of array , and compute the product of these numbers . Then she will ask Eugene to count the number of integers between and inclusive which are coprime with .
Help Eugene answer all the questions!
In the first line of input there are four integers , , , (, , ) — the length of the array , the maximum possible value of , the value , and the number of queries.
The second line contains integers () — the array .
In the next lines the queries are given. Each query consists of two integers and ().
Print integers — the answers to Burenka's queries.
Input
In the first line of input there are four integers , , , (, , ) — the length of the array , the maximum possible value of , the value , and the number of queries.
The second line contains integers () — the array .
In the next lines the queries are given. Each query consists of two integers and ().
Output
Print integers — the answers to Burenka's queries.
Note
Here's an explanation for the example:
- in the first query, the product is equal to , which is coprime with .
- in the second query, the product is equal to , which is coprime with and .
- in the third query, the product is equal to , which is coprime with and .