Fibonotci sequence is an integer recursive sequence defined by the recurrence relation
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 .
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 should contain a single integer equal to .
- , for
- All values are integers
10 8 3 1 2 1 2 7 3 5 4