Attendance Check

Time limit0.1sMemory limit1024 MB

Summary

Given sleeping students, Q sent codes, and M ranges, count numbers in each range that get no code from any divisor or multiple among the senders.

Level: Medium6 of 10
Topics: Number theory, Prefix sum, Implementation, Array
Solved: No attempts yet

Problem

Because of the coronavirus, University H is holding its lectures online. Jihwan, who has been assigned as the teaching assistant, wants to change how attendance is checked.

Students receive entrance numbers from 3 to N + 2 in the order they connect.

When Jihwan sends an attendance code to a student, that student sends the attendance code to the students whose entrance numbers are multiples of their own, so that those students can be counted as present in the lecture.

However, the K students who are asleep do not submit the attendance code, and they do not send it to any other students.

Jihwan repeats the action of sending an attendance code to one randomly chosen student Q times, and then, to organize the attendance book, he wants to find the number of students who were not marked present among the students with entrance numbers in a given range.

Write a program for Jihwan, who is busy handling so many people!

Input

The first line gives the number of students N, the number of sleeping students K, the number of students to whom Jihwan sends the attendance code Q, and the number of ranges to be given M. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000)

The second and third lines give the entrance numbers of the K sleeping students and the entrance numbers of the Q students who receive the attendance code, respectively.

From the fourth line, M lines follow, each giving a range S, E separated by a space. (3 ≤ S < E ≤ N + 2)

Output

Over M lines, print the number of students who were not marked present for each range.

Examples2

Example 1
Input
```
10 1 3 1
7
3 5 7
3 12
```
Expected output
```
4
```

Example 2

Input

50 4 5 1
24 15 27 43
3 4 6 20 25
3 52

Expected output