#P1718F. Burenka, an Array and Queries

    ID: 868 Type: RemoteJudge 3000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 10 Uploaded By: Tags>data structuresmathnumber theory*3300

Burenka, an Array and Queries

Description

Eugene got Burenka an array aa of length nn of integers from 11 to mm for her birthday. Burenka knows that Eugene really likes coprime integers (integers xx and yy such that they have only one common factor (equal to 11)) so she wants to to ask Eugene qq questions about the present.

Each time Burenka will choose a subsegment al,al+1,,ara_l, a_{l + 1}, \ldots, a_r of array aa, and compute the product of these numbers p=alal+1arp = a_l \cdot a_{l + 1} \cdot \ldots \cdot a_r. Then she will ask Eugene to count the number of integers between 11 and CC inclusive which are coprime with pp.

Help Eugene answer all the questions!

In the first line of input there are four integers nn, mm, CC, qq (1n,q1051 \leq n, q \leq 10^5, 1m21041 \leq m \leq 2\cdot 10^4, 1C1051 \leq C \leq 10^5) — the length of the array aa, the maximum possible value of aia_{i}, the value CC, and the number of queries.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1aim1 \leq a_{i} \leq m) — the array aa .

In the next qq lines the queries are given. Each query consists of two integers ll and rr (1lrn1 \leq l \leq r \leq n).

Print qq integers — the answers to Burenka's queries.

Input

In the first line of input there are four integers nn, mm, CC, qq (1n,q1051 \leq n, q \leq 10^5, 1m21041 \leq m \leq 2\cdot 10^4, 1C1051 \leq C \leq 10^5) — the length of the array aa, the maximum possible value of aia_{i}, the value CC, and the number of queries.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1aim1 \leq a_{i} \leq m) — the array aa .

In the next qq lines the queries are given. Each query consists of two integers ll and rr (1lrn1 \leq l \leq r \leq n).

Output

Print qq integers — the answers to Burenka's queries.

Sample Input 1

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

Sample Output 1

5
2
2

Note

Here's an explanation for the example:

  1. in the first query, the product is equal to 11, which is coprime with 1,2,3,4,51,2,3,4,5.
  2. in the second query, the product is equal to 1212, which is coprime with 11 and 55.
  3. in the third query, the product is equal to 1010, which is coprime with 11 and 33.