Coloring Solution Codeforces Educational Round 144
A matrix of size beautiful if the sum in every contiguous submatrix of size is exactly , i. e. every “square” of size contains exactly two ‘s and exactly two ‘s., such that each cell of it contains either or , is considered
You are given a matrix of size. Initially each cell of this matrix is empty. Let’s denote the cell on the intersection of the -th row and the -th column as . You have to process the queries of three types:
- — clear the cell , if there was a number in it;
- overwriting the number that was there previously (if any); — write the number in the cell ,
- overwriting the number that was there previously (if any). — write the number in the cell ,
After each query, print the number of ways to fill the empty cells of the matrix so that the resulting matrix is beautiful. Since the answers can be large, print them modulo .
The first line contains three integers, and ( ; ) — the number of rows in the matrix, the number of columns, and the number of queries, respectively.
Thenlines follow, the -th of them contains three integers , , ( ; ; ) — the parameters for the -th query.
For each query, print one integer — the number of ways to fill the empty cells of the matrix after the respective query, taken modulo.
2 2 7 1 1 1 1 2 1 2 1 1 1 1 0 1 2 -1 2 1 -1 1 1 -1
3 1 0 1 2 3 6