Bit reversing - MarisaOJ: Marisa Online Judge

Given a binary matrix

$A$ of

$n$ rows and

$m$ columns. You can do the following operation on the matrix: - Select a row or a column and reverse every numbers on that row or column (.i.e

$1$ turn into

$0$ , and

$0$ turn into

$1$ ). You are given

$q$ queries of form

$(a, b, c, d)$ . Determine if the submatrix with upper-left corner at

$(a, b)$ and lower-right corner at

$(c, d)$ can be transformed into a matrix full of

$0$ by applying the above operation? ### Input - The first line contains 3 integers

$n, m, q$ . - The next

$n$ lines, each line contains a binary string of length

$m$ . - The next

$q$ lines, each line contains 4 integers

$a, b, c, d$ , a query. ### Output - For each query, print

$YES$ if the submatrix can be transformed into a matrix full of

$0$ , otherwise print

$NO$ . ### Constraints -

$1 \le n, m \le 500$ . -

$1 \le q \le 10^5$ . -

$1 \le a, c \le n$ . -

$1 \le b, d \le m$ . ### Example Input:

$3 3 3 101 001 110 2 1 3 2 2 2 3 3 1 1 2 3$

Output:

$YES YES NO$

Topic

Hashing

Rating

1400

Solution (0)

Solution