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`

## Comments