## Bubble Cup V8 A Fibonotci

View as PDF

Points: 25
Time limit: 3.0s
Memory limit: 64M

Problem type

Fibonotci sequence is an integer recursive sequence defined by the recurrence relation

with

.

Sequence is infinite and almost cyclic sequence with a cycle of length . A sequence is almost cyclic with a cycle of length iff , for , except for a finite number of values , for which .

Following is an example of an almost cyclic sequence with a cycle of length .

Notice that the only value of for which the equality does not hold is ( and ).

You are given and all the values of sequence for which .

Find .

#### Input Specification

The first line contains two numbers and . The second line contains a single number . The third line contains numbers separated by spaces, that represent the first numbers of the sequence . The fourth line contains a single number , the number of values of sequence for which . Each of the following lines contains two integers and , indicating that and .

#### Output Specification

Output should contain a single integer equal to .

#### Constraints

• , for
• All values are integers

#### Example input

10 8
3
1 2 1
2
7 3
5 4

#### Example output

4