Fibonotci sequence is an integer recursive sequence defined by the recurrence relation Fn=sn-1 \cdot Fn-1+sn-2 \cdot Fn-2 with F0=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 \ge N, except for a finite number of values si, for which (i \ge 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 \ge 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 \le N,M \le 50000 0 \le K \le 1018 1 \le P \le 109 1 \le si \le 109, for all i=0,1,...N-1 N \le j \le 1018 1 \le v \le 109 All values are integers

Output Output should contain a single integer equal to .