Bubble Cup 8 - Finals [Online Mirror] |
---|
Закончено |
Последовательность Фибоноччи — это целочисленная рекуррентная последовательность, определяемая следующим образом:
Последовательность s — это бесконечная и почти периодическая последовательность с периодом длины N. Здесь последовательность s называется почти периодической с периодом длины N, если , для i ≥ N, кроме конечного числа значений si, для которых (i ≥ N).
Далее следует пример почти периодической последовательности с периодом длины 4:
Обратите внимание, что единственное значение s, для которого не выполняется уравнение — это s6 (s6 = 7 и s2 = 8). Вам даны s0, s1, ...sN - 1 и все значения последовательности s, для которых (i ≥ N).
Найдите .
Первая строка содержит два целых числа, K и P. Во второй строке записано единственное число N. В третьей строке записано N чисел через пробелы, обозначающие первые N чисел последовательности s. В четвёртой строке записано единственное целое число M, количество значений в последовательности s, для которых . Каждая из последующих M строк содержит по два числа, j и v, обозначающих, что и sj = v. Все значения j различны.
Выведите единственное целое число, равное .
10 8
3
1 2 1
2
7 3
5 4
4
Название |
---|