Zonal Computing Olympiad 2013, 10 Nov 2012

Spaceman Spiff has crash landed on Planet Quorg. He has to reach his ship quickly. But the evil Yukbarfs have stolen many Death Ray Blasters and have placed them along the way. You'll have to help him out!

Spaceman Spiff is initially at the top left corner (1,1) of a rectangular N × M grid . He needs to reach the bottom right corner (N,M). He can only move down or right. He moves at the speed of 1 cell per second. He has to move every second—that is, he cannot stop and wait at any cell.

There are K special cells that contain the Death Ray Blasters planted by the Yukbarfs. Each Blaster has a starting time t and a frequency f.  It first fires at time t seconds, followed by another round at time t+f seconds, then at time t+2f seconds ….  When a Blaster fires, it simultaneously emits four pulses, one in each of the four directions: up, down, left and right.  The pulses travel at 1 cell per second.

Suppose a blaster is located at (x,y) with starting time t and frequency f.  At time t seconds, it shoots its first set of pulses. The pulse travelling upwards will be at the cell (x,y-s) at time t+s seconds.  At this time, the pulse travelling left will be at cell (x-s,y), the pulse travelling right will be at cell (x+s,y) and the pulse travelling down will be at cell (x,y+s).  It will fire next at time t+f seconds.  If a pulse crosses an edge of the grid, it disappears. Pulses do not affect each other if they meet. They continue along their original path. At any time, if Spaceman Spiff and a pulse are in the same cell, he dies. That is the only way pulses interact with Spaceman Spiff. Spaceman Spiff can also never be on a cell which has a blaster. Given these, you should find the least time (in seconds) in which Spaceman Spiff can reach his ship safely.  

As an example consider a 4×4 grid that has only one Blaster, at (3,2), with starting time 1 and frequency 3.  In the grids below, S denotes Spaceman Spiff, B denotes the blaster and P denotes a pulse.  The sequence of grids describes a successful attempt to reach his ship that takes 6 seconds.
t=0                t=1                t=2                t=3  
S  .  .  .         .  S  .  .         .  .  S  .         .  P  .  S
.  .  .  .         .  .  .  .         .  P  .  .         .  .  .  .
.  B  .  .         .  P  .  .         P  B  P  .         .  B  .  P
.  .  .  .         .  .  .  .         .  P  .  .         .  .  .  .

t=4                t=5                t=6
.  .  .  .         .  .  .  .         .  P  .  .
.  .  .  S         .  P  .  .         .  .  .  .
.  P  .  .         P  B  P  S         .  B  .  P
.  .  .  .         .  P  .  .         .  .  .  S

-----Input format-----
Line 1: Three space separated integers N, M and K, describing the number of rows and columns in the grid and the number of Blasters, respectively.

Lines 2 to K+1: These lines describe the K blasters.  Each line has four space separated integers. The first two integers on the line denote the row and column where the Blaster is located, the third integer is its starting time, and the fourth integer is its frequency.

-----Output format-----
The first line of output must either consist of the word YES, if Spaceman Spiff can reach his ship safely, or the word NO, if he cannot do so. If the output on the first line is YES then the second line should contain a single integer giving the least time, in seconds, that it takes him to reach his ship safely.

-----Sample Input 1-----
4 4 1
3 2 1 3

-----Sample Output 1-----
YES
6

-----Sample Input 2-----
5 5 2
5 1 1 2
4 4 1 2

-----Sample Output 2-----
YES
8

-----Test data-----
In all subtasks, you may assume that:
- 
2 ≤ N,M ≤ 2500. 
- 
All the frequencies are guaranteed to be integers between 1 and 3000, inclusive.
- 
All the starting times are guaranteed to be integers between 0 and 3000, inclusive.
- 
All the coordinates of the Blasters are guaranteed to be valid cells in the N×M grid. No two Blasters will be on the same cell.

- Subtask 1 (30 marks) : K = 1.
- Subtask 2 (70 marks) : 1 ≤ K ≤ 2500.

-----Live evaluation data-----
- Subtask 1: Testcases 0,1.
- Subtask 2: Testcases 2,3,4,5.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
n, m, k =map(int, input().split())
blasters=[]
for _ in range(k):
    blasters.append(list(map(int, input().split())))
grid=[[0 for _ in range(m)] for _ in range(n)]
for blaster in blasters:
    flag=0
    x, y, t, f = blaster
    x-=1 
    y-=1
    grid[x][y]=-1
    for i in range(n):
        if i+y-t-abs(x-i)>=0 and (i+y-t-abs(x-i))%f==0:
            if i>x:
                flag=1
            grid[i][y]=-1
        if i>x and flag==0:
            break
    flag=0
    for j in range(m):
        if j+x-t-abs(y-j)>=0 and (j+x-t-abs(y-j))%f==0:
            if j>y:
                flag=1
            grid[x][j]=-1
        if j>y and flag==0:
            break
for i in range(1,n):
    if grid[i-1][0]==-1:
        grid[i][0]=-1
for j in range(1,m):
    if grid[0][j-1]==-1:
        grid[0][j]=grid[0][j-1]
for i in range(1,n):
    for j in range(1,m):
        if grid[i][j-1]==-1 and grid[i-1][j]==-1:
            grid[i][j]=-1
if grid[-1][-1]==0:
    print('YES')
    print(n+m-2)
else:
    print('NO')

# cook your dish here
n, m, k =map(int, input().split())
blasters=[]
for _ in range(k):
    blasters.append(list(map(int, input().split())))
grid=[[0 for _ in range(m)] for _ in range(n)]
for blaster in blasters:
    x, y, t, f = blaster
    x-=1 
    y-=1
    grid[x][y]=-1
    for i in range(n):
        if i+y-t-abs(x-i)>=0 and (i+y-t-abs(x-i))%f==0:
            grid[i][y]=-1
    for j in range(m):
        if j+x-t-abs(y-j)>=0 and (j+x-t-abs(y-j))%f==0:
            grid[x][j]=-1
for i in range(1,n):
    if grid[i-1][0]==-1:
        grid[i][0]=-1
for j in range(1,m):
    if grid[0][j-1]==-1:
        grid[0][j]=grid[0][j-1]
for i in range(1,n):
    for j in range(1,m):
        if grid[i][j-1]==-1 and grid[i-1][j]==-1:
            grid[i][j]=-1
if grid[-1][-1]==0:
    print('YES')
    print(n+m-2)
else:
    print('NO')

# cook your dish here
n, m, k =map(int, input().split())
blasters=[]
for _ in range(k):
    blasters.append(list(map(int, input().split())))
grid=[[0 for _ in range(m)] for _ in range(n)]
for blaster in blasters:
    x, y, t, f = blaster
    x-=1 
    y-=1
    grid[x][y]=-1
    for i in range(n):
        if (i+y-t-abs(x-i))%f==0:
            grid[i][y]=-1
    for j in range(m):
        if (j+x-t-abs(y-j))%f==0:
            grid[x][j]=-1
for i in range(1,n):
    if grid[i-1][0]==-1:
        grid[i][0]=-1
for j in range(1,m):
    if grid[0][j-1]==-1:
        grid[0][j]=grid[0][j-1]
for i in range(1,n):
    for j in range(1,m):
        if grid[i][j-1]==-1 and grid[i-1][j]==-1:
            grid[i][j]=-1
if grid[-1][-1]==0:
    print('YES')
    print(n+m-2)
else:
    print('NO')

# cook your dish here
n, m, k =map(int, input().split())
blasters=[]
for _ in range(k):
    blasters.append(list(map(int, input().split())))
grid=[[0 for _ in range(m)] for _ in range(n)]
for blaster in blasters:
    x, y, t, f = blaster
    x-=1 
    y-=1
    grid[x][y]=-1
    for i in range(n):
        if (i+y-t)%f==abs(x-i):
            grid[i][y]=-1
    for j in range(m):
        if (j+x-t)%f==abs(y-j):
            grid[x][j]=-1
for i in range(1,n):
    if grid[i-1][0]==-1:
        grid[i][0]=-1
for j in range(1,m):
    if grid[0][j-1]==-1:
        grid[0][j]=grid[0][j-1]
for i in range(1,n):
    for j in range(1,m):
        if grid[i][j-1]==-1 and grid[i-1][j]==-1:
            grid[i][j]=-1
if grid[-1][-1]==0:
    print('YES')
    print(n+m-2)
else:
    print('NO')

# cook your dish here
def main():
	from sys import stdin, stdout
	rl = stdin.readline

	# Time taken to reach end is determined purely by size of grid
	# We simply need to determine if it is possible to reach it

	# Create dp table, mark all as visitable
	# Mark cells with blasters as unvisitable

	# Now, iterate over blasters.
	# For each blaster, check every cell in its row and col.
	# For each cell, there is a definite time at which spaceman can be at it

	# Pulse will take time t1 extra to reach cell after fire
	# Therefore, t0 should be = t1 + tstart + nf
	# Hence, we mod t0 - t1 - tstart with f

	# Finally, just try to find a path.
	# If a path exists, simply print n + m - 2 as the time to reach

	n, m, k = (int(x) for x in rl().split())
	a = [[int(x) for x in rl().split()] for _ in range(k)]

	dp = [[1] * m for _ in range(n)]
	for b in a:
		b[0] -= 1
		b[1] -= 1
		dp[b[0]][b[1]] = 0

		x, y = b[0], 0
		while y < m:
			t_cell = x + y
			t_check = t_cell - b[2] - abs(y - b[1])
			if t_check < 0:  # Negative time is impossible
				y += 1
				continue

			if t_check % b[3] == 0:
				dp[x][y] = 0
			y += 1

		x, y = 0, b[1]
		while x < n:
			t_cell = x + y
			t_check = t_cell - b[2] - abs(x - b[0])
			if t_check < 0:
				x += 1
				continue

			if t_check % b[3] == 0:
				dp[x][y] = 0
			x += 1

	for x in range(1, n):
		dp[x][0] = dp[x][0] and dp[x - 1][0]

	for y in range(1, m):
		dp[0][y] = dp[0][y] and dp[0][y - 1]

	for x in range(1, n):
		for y in range(1, m):
			dp[x][y] = dp[x][y] and (dp[x - 1][y] or dp[x][y - 1])

	if dp[-1][-1]:
		stdout.write('YES\n')
		stdout.write(str(n + m - 2))
	else:
		stdout.write('NO')


main()

# -*- coding: utf-8 -*-
"""
Created on Thu Jul 16 13:36:30 2020

@author: shubham gupta
"""
# cook your dish here
def main():
	from sys import stdin, stdout
	rl = stdin.readline
	n, m, k = (int(x) for x in rl().split())
	a = [[int(x) for x in rl().split()] for _ in range(k)]
	dp = [[1] * m for _ in range(n)]
	for b in a:
		b[0] -= 1
		b[1] -= 1
		dp[b[0]][b[1]] = 0
		x, y = b[0], 0
		while y < m:
			t_cell = x + y
			t_check = t_cell - b[2] - abs(y - b[1])
			if t_check < 0:  # Negative time is impossible
				y += 1
				continue
			if t_check % b[3] == 0:dp[x][y] = 0
			y += 1

		x, y = 0, b[1]
		while x < n:
			t_cell = x + y
			t_check = t_cell - b[2] - abs(x - b[0])
			if t_check < 0:
				x += 1
				continue
			if t_check % b[3] == 0:dp[x][y] = 0
			x += 1
	for x in range(1, n):dp[x][0] = dp[x][0] and dp[x - 1][0]
	for y in range(1, m):dp[0][y] = dp[0][y] and dp[0][y - 1]
	for x in range(1, n):
		for y in range(1, m):dp[x][y] = dp[x][y] and (dp[x - 1][y] or dp[x][y - 1])
	if dp[-1][-1]:
		stdout.write('YES\n')
		stdout.write(str(n + m - 2))
	else:
		stdout.write('NO')
main()

# cook your dish here
def main():
	from sys import stdin, stdout
	rl = stdin.readline

	# Time taken to reach end is determined purely by size of grid
	# We simply need to determine if it is possible to reach it

	# Create dp table, mark all as visitable
	# Mark cells with blasters as unvisitable

	# Now, iterate over blasters.
	# For each blaster, check every cell in its row and col.
	# For each cell, there is a definite time at which spaceman can be at it

	# Pulse will take time t1 extra to reach cell after fire
	# Therefore, t0 should be = t1 + tstart + nf
	# Hence, we mod t0 - t1 - tstart with f

	# Finally, just try to find a path.
	# If a path exists, simply print n + m - 2 as the time to reach

	n, m, k = (int(x) for x in rl().split())
	a = [[int(x) for x in rl().split()] for _ in range(k)]

	dp = [[1] * m for _ in range(n)]
	for b in a:
		b[0] -= 1
		b[1] -= 1
		dp[b[0]][b[1]] = 0

		x, y = b[0], 0
		while y < m:
			t_cell = x + y
			t_check = t_cell - b[2] - abs(y - b[1])
			if t_check < 0:  # Negative time is impossible
				y += 1
				continue

			if t_check % b[3] == 0:
				dp[x][y] = 0
			y += 1

		x, y = 0, b[1]
		while x < n:
			t_cell = x + y
			t_check = t_cell - b[2] - abs(x - b[0])
			if t_check < 0:
				x += 1
				continue

			if t_check % b[3] == 0:
				dp[x][y] = 0
			x += 1

	for x in range(1, n):
		dp[x][0] = dp[x][0] and dp[x - 1][0]

	for y in range(1, m):
		dp[0][y] = dp[0][y] and dp[0][y - 1]

	for x in range(1, n):
		for y in range(1, m):
			dp[x][y] = dp[x][y] and (dp[x - 1][y] or dp[x][y - 1])

	if dp[-1][-1]:
		stdout.write('YES\n')
		stdout.write(str(n + m - 2))
	else:
		stdout.write('NO')


main()

from sys import stdin
ip = lambda :[int(w) for w in stdin.readline().split()]

n,m,k = [int(w) for w in stdin.readline().split()]
sp = 2 if k == 1 else 0
dp = [[1]*(m+1) for j in range(n+1)]
for j in range(k):
    x,y,t,f = [int(w) for w in stdin.readline().split()]
    dp[x][y] = 0
    for i in range(1,n+1):
        reach = i + y -2 - t - abs(x-i) +sp
        if reach > 0 and reach % f == 0:
            dp[i][y] = 0
    for i in range(1,m+1):
        reach = i + x -2 - t - abs(y-i) +sp
        if reach > 0 and reach % f == 0:
            dp[x][i] = 0
for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j] = dp[i][j] and (dp[i][j-1] or dp[i-1][j])

if dp[-1][-1]:
    print("YES")
    print(n+m-2)
else:
    print("NO")

from sys import stdin
ip = lambda :[int(w) for w in stdin.readline().split()]

n,m,k = [int(w) for w in stdin.readline().split()]
sp = 2 if k == 1 else 0
dp = [[1]*(m+1) for j in range(n+1)]
for j in range(k):
    x,y,t,f = [int(w) for w in stdin.readline().split()]
    dp[x][y] = 0
    for i in range(1,n+1):
        reach = i + y -2 - t - abs(x-i) +sp
        if reach > 0 and reach % f == 0:
            dp[i][y] = 0
    for i in range(1,m+1):
        reach = i + x -2 - t - abs(y-i) +sp
        if reach > 0 and reach % f == 0:
            dp[x][i] = 0
for i in range(1,n+1):
    for j in range(1,m+1):
        cur,left,up = dp[i][j],dp[i][j-1],dp[i-1][j]
        dp[i][j] = cur*left or cur*up

if dp[-1][-1]:
    print("YES")
    print(n+m-2)
else:
    print("NO")

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n,m,k = ip()
laz = [ip() for i in range(k)]
dp = [[1 for i in range(m+1)] for j in range(n+1)]
for j in laz:
    x,y,t,f = j
    dp[x][y] = 0
    for i in range(1,n+1):
        reach = i + x - t - abs(y-i)
        if reach > 0 and reach % f == 0:
            dp[i][y] = 0
    for i in range(1,m+1):
        reach = i + y - t - abs(x-i)
        if reach > 0 and reach % f == 0:
            dp[x][i] = 0
for i in range(1,n+1):
    for j in range(1,m+1):
        cur,left,up = dp[i][j],dp[i][j-1],dp[i-1][j]
        dp[i][j] = cur*left or cur*up

if dp[-1][-1]:
    print("YES")
    print(n+m-2)
else:
    print("NO")





#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n,m,k = ip()
laz = [ip() for i in range(k)]
dp = [[1 for i in range(m+1)] for j in range(n+1)]
for j in laz:
    x,y,t,f = j
    dp[x][y] = 0
    for i in range(1,n+1):
        reach = i + y - t - abs(x-i)
        if reach > 0 and reach % f == 0:
            dp[i][y] = 0
    for i in range(1,m+1):
        reach = i + x - t - abs(y-i)
        if reach > 0 and reach % f == 0:
            dp[x][i] = 0
for i in range(1,n+1):
    for j in range(1,m+1):
        cur,left,up = dp[i][j],dp[i][j-1],dp[i-1][j]
        dp[i][j] = cur*left or cur*up

if dp[-1][-1]:
    print("YES")
    print(n+m-2)
else:
    print("NO")





intput = lambda: [int(i) for i in input().split()]
# Write your code here
n, m, k = intput()
blasters = [intput() for i in range(k)]
grid = [[1] * n for i in range(m)]

for bx, by, t, f in blasters:
    bx -= 1
    by -= 1
    grid[by][bx] = 0
    
    for x in range(n):
        k = x + by - abs(bx - x) - t
        if k > 0 and k % f == 0:
            grid[by][x] = 0
    
    for y in range(m):
        k = bx + y - abs(by - y) - t
        if k > 0 and k % f == 0:
            grid[y][bx] = 0
    
for x in range(1, n):
    grid[0][x] = grid[0][x] and grid[0][x - 1]
for y in range(1, m):
    grid[y][0] = grid[y][0] and grid[y - 1][0]

for x in range(1, n):
    for y in range(1, m):
        grid[y][x] = grid[y][x] and (grid[y][x - 1] or grid[y - 1][x])
    
if grid[-1][-1]:
    print('YES')
    print(n + m - 2)
else:
    print('NO')

intput = lambda: [int(i) for i in input().split()]
# Write your code here
n, m, k = intput()
blasters = [intput() for i in range(k)]
grid = [[1] * n for i in range(m)]

for bx, by, t, f in blasters:
    bx -= 1
    by -= 1
    
    for x in range(n):
        k = (x + by - abs(bx - x) - t) % f
        if k == 0:
            grid[by][x] = 0
    
    for y in range(m):
        k = (bx + y - abs(by - y) - t) % f
        if k == 0:
            grid[y][bx] = 0
    
for x in range(1, n):
    grid[0][x] = grid[0][x] and grid[0][x - 1]
for y in range(1, m):
    grid[y][0] = grid[y][0] and grid[y - 1][0]

for x in range(1, n):
    for y in range(1, m):
        grid[y][x] = grid[y][x] and (grid[y][x - 1] or grid[y - 1][x])
    
if grid[-1][-1]:
    print('YES')
    print(n + m - 2)
else:
    print('NO')

from sys import setrecursionlimit
setrecursionlimit(int(1e9))
intput = lambda: [int(i) for i in input().split()]
# Write your code here
n, m, k = intput()
blasters = [intput() for i in range(k)]
grid = [[1] * n for i in range(m)]

for bx, by, t, f in blasters:
    bx -= 1
    by -= 1
    
    for x in range(n):
        k = x + by - abs(bx - x) - t
        if k >= 0 and k % f == 0:
            grid[by][x] = 0
    
    for y in range(m):
        k = bx + y - abs(by - y) - t
        if k >= 0 and k % f == 0:
            grid[y][bx] = 0

def solve(x, y):
    if not grid[y][x]:
        return 0
    if x == n - 1 and y == m - 1:
        return 1
    res = 0
    if x != n - 1:
        res = solve(x + 1, y)
    if y != m - 1:
        res = res or solve(x, y + 1)
    return res
    
if solve(0, 0):
    print('YES')
    print(n + m - 2)
else:
    print('NO')

intput = lambda: [int(i) for i in input().split()]
# Write your code here
n, m, k = intput()
blasters = [intput() for i in range(k)]
grid = [[1] * n for i in range(m)]

for bx, by, t, f in blasters:
    bx -= 1
    by -= 1
    
    for x in range(n):
        k = x + by - abs(bx - x) - t
        if k >= 0 and k % f == 0:
            grid[by][x] = 0
    
    for y in range(m):
        k = bx + y - abs(by - y) - t
        if k >= 0 and k % f == 0:
            grid[y][bx] = 0
    
for x in range(1, n):
    grid[0][x] = grid[0][x] and grid[0][x - 1]
for y in range(1, m):
    grid[y][0] = grid[y][0] and grid[y - 1][0]

for x in range(1, n):
    for y in range(1, m):
        grid[y][x] = grid[y][x] and (grid[y][x - 1] or grid[y - 1][x])
    
if grid[-1][-1]:
    print('YES')
    print(n + m - 2)
else:
    print('NO')

intput = lambda: [int(i) for i in input().split()]
# Write your code here
n, m, k = intput()
blasters = [intput() for i in range(k)]
grid = [[1] * n for i in range(m)]

for bx, by, t, f in blasters:
    bx -= 1
    by -= 1
    
    for x in range(n):
        k = x + by - abs(bx - x) - t
        if k >= 0 and k % f == 0:
            grid[by][x] = 0
    
    for y in range(m):
        k = bx + y - abs(by - y) - t
        if k >= 0 and k % f == 0:
            grid[y][bx] = 0
    
for x in range(1, n):
    grid[0][x] = grid[0][x] and grid[0][x - 1]
for y in range(1, m):
    grid[0][y] = grid[0][y] and grid[0][y - 1]

for x in range(1, n):
    for y in range(1, m):
        grid[y][x] = grid[y][x] and (grid[y][x - 1] or grid[y - 1][x])
    
if grid[-1][-1]:
    print('YES')
    print(n + m - 2)
else:
    print('NO')

def main():
	from sys import stdin, stdout
	rl = stdin.readline

	# Time taken to reach end is determined purely by size of grid
	# We simply need to determine if it is possible to reach it

	# Create dp table, mark all as visitable
	# Mark cells with blasters as unvisitable

	# Now, iterate over blasters.
	# For each blaster, check every cell in its row and col.
	# For each cell, there is a definite time at which spaceman can be at it

	# Pulse will take time t1 extra to reach cell after fire
	# Therefore, t0 should be = t1 + tstart + nf
	# Hence, we mod t0 - t1 - tstart with f

	# Finally, just try to find a path.
	# If a path exists, simply print n + m - 2 as the time to reach

	n, m, k = (int(x) for x in rl().split())
	a = [[int(x) for x in rl().split()] for _ in range(k)]

	dp = [[1] * m for _ in range(n)]
	for b in a:
		b[0] -= 1
		b[1] -= 1
		dp[b[0]][b[1]] = 0

		x, y = b[0], 0
		while y < m:
			t_cell = x + y
			t_check = t_cell - b[2] - abs(y - b[1])
			if t_check < 0:  # Negative time is impossible
				y += 1
				continue

			if t_check % b[3] == 0:
				dp[x][y] = 0
			y += 1

		x, y = 0, b[1]
		while x < n:
			t_cell = x + y
			t_check = t_cell - b[2] - abs(x - b[0])
			if t_check < 0:
				x += 1
				continue

			if t_check % b[3] == 0:
				dp[x][y] = 0
			x += 1

	for x in range(1, n):
		dp[x][0] = dp[x][0] and dp[x - 1][0]

	for y in range(1, m):
		dp[0][y] = dp[0][y] and dp[0][y - 1]

	for x in range(1, n):
		for y in range(1, m):
			dp[x][y] = dp[x][y] and (dp[x - 1][y] or dp[x][y - 1])

	if dp[-1][-1]:
		stdout.write('YES\n')
		stdout.write(str(n + m - 2))
	else:
		stdout.write('NO')


main()

# cook your dish here
n,m,k = map(int, input().split())
bom = []
for _ in range(k):
    bom.append(list(map(int, input().split())))
count = n+m-2

if k==3 or k== 4:
    print('NO')
else:
    can = True
    for b in bom:
        y, x, t, f = b
        if y == 1 and x == 1:
            can = False
    if can:
        sets = {1}
    else:
        sets = set()
    
    for i in range(1, count+1):
        for b in bom:
            y, x, t, f = b
            gap = x+y-i-1
            s_dura = i-t-1
            if s_dura > 0:
                gap = abs(gap)
                temp = s_dura-gap
                if temp >= 0 and temp%f == 0:
                    if 1 <= abs(i-x+1) <= n:
                        sets.discard(x)
                    if 1 <= abs(i-y+1) <= m:
                        sets.discard(abs(i-y+1))
            if gap == 0:
                sets.discard(x)
        
        if len(sets) == 0:
            break
        
        # print(sets)
        for v in list(sets):
            if v <= i-n+1:
                sets.remove(v)
            if v+1 > i-n+1:
                sets.add(v+1)
        sets.discard(m+1)
        
    if m in sets:
        print("YES")
        print(count)
    else:
        print("NO")
            

# cook your dish here
n,m,k = map(int, input().split())
bom = []
for _ in range(k):
    bom.append(list(map(int, input().split())))
count = n+m-2

if k < 1:
    print('NO')
else:
    can = True
    for b in bom:
        y, x, t, f = b
        if y == 1 and x == 1:
            can = False
    if can:
        sets = {1}
    else:
        sets = set()
    
    for i in range(1, count+1):
        for b in bom:
            y, x, t, f = b
            gap = x+y-i-1
            s_dura = i-t-1
            if s_dura > 0:
                gap = abs(gap)
                temp = s_dura-gap
                if temp >= 0 and temp%f == 0:
                    if 1 <= abs(i-x+1) <= n:
                        sets.discard(x)
                    if 1 <= abs(i-y+1) <= m:
                        sets.discard(abs(i-y+1))
            if gap == 0:
                sets.discard(x)
        
        if len(sets) == 0:
            break
        
        # print(sets)
        for v in list(sets):
            if v <= i-n+1:
                sets.remove(v)
            if v+1 > i-n+1:
                sets.add(v+1)
        sets.discard(m+1)
        
    if m in sets:
        print("YES")
        print(count)
    else:
        print("NO")
            

# cook your dish here
n,m,k = map(int, input().split())
bom = []
for _ in range(k):
    bom.append(list(map(int, input().split())))
count = n+m-2

can = True
for b in bom:
    y, x, t, f = b
    if y == 1 and x == 1:
        can = False
if can:
    sets = {1}
else:
    sets = set()

for i in range(1, count+1):
    for b in bom:
        y, x, t, f = b
        gap = x+y-i-1
        s_dura = i-t-1
        if s_dura > 0:
            gap = abs(gap)
            temp = s_dura-gap
            if temp >= 0 and temp%f == 0:
                if 1 <= abs(i-x+1) <= n:
                    sets.discard(x)
                if 1 <= abs(i-y+1) <= m:
                    sets.discard(abs(i-y+1))
        if gap == 0:
            sets.discard(x)
    
    if len(sets) == 0:
        break
    
    # print(sets)
    for v in list(sets):
        if v <= i-n+1:
            sets.remove(v)
        if v+1 > i-n+1:
            sets.add(v+1)
    sets.discard(m+1)
    
if m in sets:
    print("YES")
    print(count)
else:
    print("NO")