5119: Fibonotci
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
A. Fibonotci
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Fibonotci sequence is an integer recursive sequence defined by the recurrence relation
Fn=sn-1·Fn-1+sn-2·Fn-2 withF0=0,F1=1 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 si, for which 
(i≥N).
Following is an example of an almost cyclic sequence with a cycle of length 4:
s = (5,3,8,11,5,3,7,11,5,3,8,11,…) Notice that the only value of s for which the equality
does not hold is s6 (s6=7 and s2=8). You are given s0,s1,...sN-1 and all the values of sequence s for which (i≥N).
Find
.
Fn=sn-1·Fn-1+sn-2·Fn-2 withF0=0,F1=1 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 si, for which (i≥N). Following is an example of an almost cyclic sequence with a cycle of length 4:
s = (5,3,8,11,5,3,7,11,5,3,8,11,…) Notice that the only value of s for which the equality
does not hold is s6 (s6=7 and s2=8). You are given s0,s1,...sN-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 sj=v. All j-s are distinct. - 1≤N,M≤50000
- 0≤K≤1018
- 1≤P≤109
- 1≤si≤109, for all i=0,1,...N-1
- N≤j≤1018
- 1≤v≤109
- 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
输入样例 复制
输出样例 复制