Little Q and Big Integers
Little Q likes positive big integers in base k notation, but not all of them. He doesn't like integers with zeroes, including leading zeroes. Additionally, he is particular about the number of occurrences of each digit. Formally, his preferences can be described as a binary matrix g[1..k-1,0..n], where for every digit i from 1 to k - 1, if g[i,j] = 0, he doesn't like integers which contain exactly j copies of digit i. He also can't accept any digit appearing more than n times. The integer must contain at least one digit.
Little Q's taste changes every day. There are m days in total, and on day i, the value g[ui,vi] is flipped (0 becomes 1 and 1 becomes 0). Let cnt(i) denote the number of big integers which Little Q likes after i-th day's change, and cnt(0) denote the answer before all changes. Your task is to calculate the following:
Input
The first line contains three integers k, n and m: the base, the upper limit and the number of days (3 ≤ k ≤ 10, 1 ≤ n ≤ 1.4 * 10^4, 1 ≤ m ≤ 200). In the next k - 1 lines, line i contains n + 1 integers g[i,0], g[i,1], ..., g[i,n] (0 ≤ g[i,j] ≤ 1). Together they provide the initial matrix g. After that follow m lines, i-th line contains two integers u[i] and v[i] which mean that on i-th day, the value g[ui,vi] is flipped (1 ≤ u[i] ≤ k - 1, 0 ≤ v[i] ≤ n).
Output
Print a single integer: the answer to the problem.