Маленький Q и большие числа
Маленький Q любит положительные большие целые числа в системе счисления k, но не все из них. Он не любит целые числа с нулями, включая ведущие нули. Кроме того, он внимательно относится к количеству вхождений каждой цифры. Формально его предпочтения можно описать как двоичную матрицу g[1..k-1,0..n], где для каждой цифры **i ** от 1 до k - 1, если g[i,j] = 0, то ему не нравятся целые числа, которые содержат ровно j копий цифры i. Он также не может допустить любую цифру, которая встречается более n раз. Целое число должно содержать хотя бы одну цифру.
Предпочтения Маленького Q меняются каждый день. Всего имеется m дней, в день i значение g[ui,vi] переворачивается (0 становится 1 и 1 становится 0). Пусть cnt(i) обозначает количество больших целых чисел, которые нравятся Маленькому Q после i - го дня изменения, а cnt(0) обозначает ответ до всех изменений. Ваша задача - вычислить следующее значение:
Входные данные
Первая строка содержит три целых числа k, n и m: основу, верхнюю границу и количество дней (3 ≤ k ≤ 10, 1 ≤ n ≤ 1.4 * 10^4, 1 ≤ m ≤ 200). В следующих k - 1 строках строка i содержит n + 1 целых чисел g[i,0], g[i,1], ..., g[i,n] (0 ≤ g[i,j] ≤ 1). Вместе они задают исходную матрицу g. Далее следуют m строк, i-ая строка содержит два целых числа u[i] и v[i] означающих что в i-ый день значение g[ui,vi] переворачивается (1 ≤ u[i] ≤ k - 1, 0 ≤ v[i] ≤ n).
Выходные данные
Выведите одно целое число: ответ к задаче.