## Bubble Cup V8 A Fibonotci

View as PDF

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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