Garden Planner

Emma is planning her garden and wants to optimize the use of space in her plot. The garden is modeled as an ( n \times m ) grid, where each cell is either available (denoted by '0') or blocked by an obstacle (denoted by '1'). She has ( q ) different types of plants, each requiring a rectangular block of contiguous available cells. Notably, each rectangular block can be rotated by (90^\circ) if necessary. The task is to determine whether Emma can place all the plant types in the garden without overlapping placements and only using available cells.

inputFormat

Input is read from standard input (stdin).
The first line contains three integers (n), (m), and (q) -- the number of rows, columns, and plant types respectively.
The next (n) lines each contain a string of length (m) representing a row of the garden (where '0' indicates an available cell and '1' indicates a blocked cell).
This is followed by (q) lines, each containing two integers that represent the required dimensions of the rectangle for each plant type.

outputFormat

Output a single line to standard output (stdout) containing either "YES" if it is possible to place all plants according to the rules, or "NO" if it is not.## sample

5 6 2
001000
000100
010000
000000
100010
2 3
3 2

YES