eolymp
bolt
Try our new interface for solving problems
Problems

Little Q and Big Integers

Little Q and Big Integers

Time limit 1 second
Memory limit 128 MiB

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:

prb9285.gif

Input data

The first line contains three integers k, n and m: the base, the upper limit and the number of days (3k10, 1n1.4 * 10^4, 1m200). In the next k - 1 lines, line i contains n + 1 integers g[i,0], g[i,1], ..., g[i,n] (0g[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 (1u[i]k - 1, 0v[i]n).

Output data

Print a single integer: the answer to the problem.

Examples

Input example #1
3 2 2
101
010
1 1
1 2
Output example #1
13
Source 2017 Petrozavodsk, Summer, Songyang Chen Contest 1, August 21, Problem A