Fibonotci sequence is an integer recursive sequence defined by the recurrence relation F n = s n - 1·F n - 1 + s n - 2·F n - 2 with F 0 = 0, F 1 = 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 s i , 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 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 .

输入描述:

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 ≤ 500000 ≤ K ≤ 10181 ≤ P ≤ 1091 ≤ si ≤ 109, for all i = 0, 1, ...N - 1N ≤ j ≤ 10181 ≤ v ≤ 109 All values are integers

输出描述:

Output should contain a single integer equal to .