### PROBLEM LINK:

**Author:** Kevin Atienza

**Testers:** Sergey Kulik and Vasya Antoniuk

**Translators:** Vasya Antoniuk (Russian), Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)

**Editorialist:** Kevin Atienza

### DIFFICULTY:

Simple

### PREREQUISITES:

Modulo operation

### PROBLEM:

Is it possible to cut an R\times C rectangular cake into pieces with areas M, K and J? You are only allowed to cut parallel to the sides, and pieces must remain rectangular with integer sides.

### QUICK EXPLANATION:

- If RC \not= M + K + J, the answer is
`No`

, - else, if M, K and J are divisible by R, the answer is
`Yes`

, - else, if M, K and J are divisible by C, the answer is
`Yes`

, - else, if M is divisible by R and K is divisible by (C - M/R), the answer is
`Yes`

, - else, if K is divisible by R and J is divisible by (C - K/R), the answer is
`Yes`

, - else, if J is divisible by R and M is divisible by (C - J/R), the answer is
`Yes`

, - else, if M is divisible by C and K is divisible by (R - M/C), the answer is
`Yes`

, - else, if K is divisible by C and J is divisible by (R - K/C), the answer is
`Yes`

, - else, if J is divisible by C and M is divisible by (R - J/C), the answer is
`Yes`

, - otherwise, the answer is
`No`

.

The first line checks whether the area is exactly what’s needed.

The second and third line checks for two horizontal or two vertical cuts.

The fourth to ninth lines check for one horizontal and one vertical cut.

### EXPLANATION

First, for a cut to be possible, it must be the case that M + K + J constitutes the total area of the rectangle. But the total area is RC, so if RC \not= M + K + J, then the answer is immediately `No`

. Thus, in the following, we can assume that RC = M + K + J.

Each cut splits one piece into two pieces, so that means we must perform exactly two cuts. The first cut splits the whole cake into two pieces. The second cut splits one of the pieces into two again. This means that, after the first cut, one of the pieces must have an area of exactly M, K or J. In other words, it must split the whole cake into two pieces of areas (M,K+J), (K,J+M) or (J,M+K).

When is it possible to cut an R\times C piece into two pieces with areas (A,B)? Well, you can cut either horizontally or vertically.

- If you cut horizontally, then the pieces will have dimensions r_1\times C and r_2\times C, where r_1 + r_2 = R. Thus, the following must be true: A = r_1C and B = r_2C. In other words, A and B must be divisible by C.
- If you cut horizontally, then the pieces will have dimensions R\times c_1 and R\times c_2, where c_1 + c_2 = C. Thus, the following must be true: A = Rc_1 and B = Rc_2. In other words, A and B must be divisible by R.

After that, we must split one of the pieces into two parts again, with specific areas. But since we know the dimensions of the piece, this is basically the same problem as above! Therefore, we now have all the tools required to write a complete solution.

We’ll describe it with Python. First, let’s write a function that performs the procedure above:

```
def possible_splits(R,C,A,B):
# returns all possible dimensions of the second piece if we split an
# R*C rectangle into pieces with areas A and B
dimensions = []
if A % C == 0 and B % C == 0:
r2 = B / C
dimension = (r2,C)
dimensions.append(dimension)
if A % R == 0 and B % R == 0:
c2 = B / R
dimension = (R,c2)
dimensions.append(dimension)
return dimensions
```

With this function, we can now answer a query:

```
def query(R, C, M, K, J):
if R*C != M + K + J: # wrong area
return False
# try three possibilities
for r, c in possible_splits(R, C, M, K+J):
if possible_splits(r, c, K, J):
return True
for r, c in possible_splits(R, C, K, J+M):
if possible_splits(r, c, J, M):
return True
for r, c in possible_splits(R, C, J, M+K):
if possible_splits(r, c, M, K):
return True
# nothing worked
return False
```

This first checks if RC = M + K + J, and if true, tries out all three possible initial splits: (M,K+J), (K,J+M) or (J,M+K). After that, we can simply call the `query`

function to print the answers!

```
for cas in xrange(input()):
R, C, M, K, J = map(int, raw_input().strip().split())
print 'Yes' if query(R, C, M, K, J) else 'No'
```

Here is a more compact version:

```
def possible_splits(R,C,A):
B = R*C - A
if A % C == 0 and B % C == 0: yield B / C, C
if A % R == 0 and B % R == 0: yield R, B / R
def query(R, C, M, K, J):
if R*C != M + K + J: # wrong area
return False
# try three possibilities
for A, B in [(M, K), (K, J), (J, M)]:
for r, c in possible_splits(R, C, A):
if any(possible_splits(r, c, B)):
return True
# nothing worked
return False
```

The changes here are:

- We made use of Python’s
`yield`

statement to not have to collect the dimensions in a`dimensions`

array. - We removed the
`B`

parameter in`possible_splits`

, because it can be extracted from the other parameters from the equation RC = A + B.

### Time Complexity:

O(1)