A matrix and XOR operation

2.9

29 votes
Dynamic Programming, Algorithms, Introduction to Dynamic Programming 1
Problem

You are given an N×M matrix S consisting of all 0s at the beginning. You can perform the following operations any number of times:

  1. You can perform the XOR operation on all the elements of a row by 1.
  2. You can perform the XOR operation on all the elements of a column by 1.

Your task is to determine if it is possible to get Ni=1Mi=1Sij=K by using the provided operations.

Input format

  • The first line consists of T denoting the number of test cases.
  • The first line of each test case contains three space-separated integers N, M, and K.

Output format

For each test case, print "Yes" if it is possible to get this equation. Otherwise, print "No" without quotes.

Constraints

1T10000

1N,M1000000

1K1e9

Ti=1N1000000

Sample Input
2
3 3 9
3 3 8
Sample Output
Yes
No
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For first test case it is possible if we apply operation number 1, 3 times on each row.

There is no way for second test case.

Editor Image

?