Маленький Q любит положительные большие целые числа в системе счисления k, но не все из них. Он не любит целые числа с нулями, включая ведущие нули. Кроме того, он внимательно относится к количеству вхождений каждой цифры. Формально его предпочтения можно описать как двоичную матрицу g1..k-1,0..n, где для каждой цифры i * от *1 до k - 1, если gi,j = 0, то ему не нравятся целые числа, которые содержат ровно j копий цифры i. Он также не может допустить любую цифру, которая встречается более n раз. Целое число должно содержать хотя бы одну цифру.

Предпочтения Маленького Q меняются каждый день. Всего имеется m дней, в день i значение gui,vi переворачивается (0 становится 1 и 1 становится 0). Пусть cnt(i) обозначает количество больших целых чисел, которые нравятся Маленькому Q после i - го дня изменения, а cnt(0) обозначает ответ до всех изменений. Ваша задача - вычислить следующее значение:

Входные данные

Первая строка содержит три целых числа k, n и m: основу, верхнюю границу и количество дней (3 ≤ k ≤ 10, 1 ≤ n ≤ 1.4 * 104, 1 ≤ m ≤ 200). В следующих k - 1 строках строка i содержит n + 1 целых чисел gi,0, gi,1, ..., gi,n (0 ≤ gi,j ≤ 1). Вместе они задают исходную матрицу g. Далее следуют m строк, i-ая строка содержит два целых числа ui и vi означающих что в i-ый день значение gui,vi переворачивается (1 ≤ ui ≤ k - 1, 0 ≤ vi ≤ n).

Выходные данные

Выведите одно целое число: ответ к задаче.