Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Fibonotci

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFibonotci sequence is an integer recursive sequence defined by the recurrence relation

Sequence *s* is an infinite and almost cyclic sequence with a cycle of length *N*. A sequence *s* is called almost cyclic with a cycle of length *N* if , for *i* ≥ *N*, except for a finite number of values *s*_{i}, for which (*i* ≥ *N*).

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

Notice that the only value of *s* for which the equality does not hold is *s*_{6} (*s*_{6} = 7 and *s*_{2} = 8). You are given *s*_{0}, *s*_{1}, ...*s*_{N - 1} and all the values of sequence *s* for which (*i* ≥ *N*).

Find .

Input

The first line contains two numbers *K* and *P*. The second line contains a single number *N*. The third line contains *N* numbers separated by spaces, that represent the first *N* numbers of the sequence *s*. The fourth line contains a single number *M*, the number of values of sequence *s* for which . Each of the following *M* lines contains two numbers *j* and *v*, indicating that and *s*_{j} = *v*. All j-s are distinct.

- 1 ≤
*N*,*M*≤ 50000 - 0 ≤
*K*≤ 10^{18} - 1 ≤
*P*≤ 10^{9} - 1 ≤
*s*_{i}≤ 10^{9}, for all*i*= 0, 1, ...*N*- 1 -
*N*≤*j*≤ 10^{18} - 1 ≤
*v*≤ 10^{9} - All values are integers

Output

Output should contain a single integer equal to .

Examples

Input

10 8

3

1 2 1

2

7 3

5 4

Output

4

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2019 18:09:41 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|