import sys
read = sys.stdin.readline

n = int(read())
A = list(map(int, read().split()))
A.sort()
m = int(read())
num = list(map(int, read().split()))


def binsearch(x):
    if x > A[-1] or x < A[0]:
        return 0
    if x == A[-1] or x == A[0]:
        return 1
    l, r = 0, n-1
    while l <= r:
        mid = (l+r)//2
        if A[mid] == x:
            return 1
        elif A[mid] < x:
            l = mid+1
        else:
            r = mid-1
    return 0

    # 이렇게 while문 다 돌고 나서도 x를 찾지 못한 경우에
    # 0을 return해줘야 하는데 이걸 생각못했었다.
for i in num:
    print(binsearch(i))

import sys
read = sys.stdin.readline
from collections import deque
n, m, fuel = map(int, read().split())

MAP = list(list(map(int, read().split())) for _ in range(n))

a, b = list(map(int, read().split()))
start = [a-1, b-1] #택시의 최초 출발지점

pas = dict() #손님들의 위치에 따른 목적지 저장
checkpas = dict() #손님을 이미 태웠는지 아닌지 판별
for _ in range(m):
    a, b, c, d = map(int, read().split())
    pas[(a-1, b-1)] = (c-1, d-1)
    checkpas[(a-1, b-1)] = True

dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]

#최단거리의 손님 탐색
def findPAS(start):
    check = list(list(True for _ in range(n)) for _ in range(n))
    point = deque([start])
    far = 0

    same_far = []
    #원래 deque를 정렬시키는 방식으로 같은거리에 있는 손님들 중 행이 최소이거나,
    #열이 최소인 손님을 찾았는데, 매번 정렬하는 것이 시간을 많이 소비하게
    #하는 원인인것 같아서 이렇게 변경해 보았다.

    while point:

        term = len(point)

        for _ in range(term):
            a, b = point.popleft()
            check[a][b] = False

            if (a, b) in pas and checkpas[(a, b)]:
                same_far.append([far, (a, b)])

            for x, y in zip(dx, dy):
                ax, by = a+x, b+y

                if 0 <= ax < n and 0 <= by < n and MAP[ax][by] == 0 and check[ax][by]:
                    point.append([ax, by])
        #for문이 끝날 때 마다 거리 1씩 추가
        far += 1
        #가는 도중에 연료가 떨어지면 break후 -1출력
        if far > fuel: break
        # 같은 거리의 손님들 중 최소행, 최소열을 가지는 손님 식별
        if same_far:
            same_far.sort(key=lambda x: (x[1][0], x[1][1]))
            return same_far[0]

    print(-1)
    sys.exit()
    return

#손님의 목적지까지 거리 계산
def takePAS(a, b):
    check = list(list(True for _ in range(n)) for _ in range(n))
    c, d = pas[(a, b)]
    point = deque([[a, b]])
    far = 0
    while point:
        term = len(point)
        for _ in range(term):
            a, b = point.popleft()
            check[a][b] = False
            if c == a and d == b:
                return far
            for x, y in zip(dx, dy):
                ax, by = a+x, b+y
                if 0 <= ax < n and 0 <= by < n and MAP[ax][by] == 0 and check[ax][by]:
                    point.append([ax, by])
        far += 1
        #가는 도중에 연료가 떨어지면 break후 -1출력
        if len_From+far > fuel:
            break
    print(-1)
    sys.exit()
    return

for _ in range(m):
#len_From: 현재 위치(start)부터 손님까지 거리
#len_To: 손님(point)으로 부터 목적지 까지 거리
    len_From, point = findPAS(start)
    len_To = takePAS(point[0], point[1])

    if fuel < len_From+len_To:
        print(-1)
        sys.exit()

    fuel = fuel-len_From+len_To

    start = pas[point[0], point[1]]
    checkpas[(point[0], point[1])] = False

print(fuel)