Wilbur the pig now wants to play with strings. He has found an n by m table consisting only of the digits from 0 to 9 where the rows are numbered 1 to n and the columns are numbered 1 to m. Wilbur starts at some square and makes certain moves. If he is at square (x, y) and the digit d (0 ≤ d ≤ 9) is written at position (x, y), then he must move to the square (x + ad, y + bd), if that square lies within the table, and he stays in the square (x, y) otherwise. Before Wilbur makes a move, he can choose whether or not to write the digit written in this square on the white board. All digits written on the whiteboard form some string. Every time a new digit is written, it goes to the end of the current string.

Wilbur has q strings that he is worried about. For each string si, Wilbur wants to know whether there exists a starting position (x, y) so that by making finitely many moves, Wilbur can end up with the string si written on the white board.

Input

The first line of the input consists of three integers n, m, and q (1 ≤ n, m, q ≤ 200) — the dimensions of the table and the number of strings to process, respectively.

Each of the next n lines contains m digits from 0 and 9 giving the table itself.

Then follow 10 lines. The i-th of them contains the values ai - 1 and bi - 1 ( - 200 ≤ ai, bi ≤ 200), i.e. the vector that Wilbur uses to make a move from the square with a digit i - 1 in it.

There are q lines that follow. The i-th of them will contain a string si consisting only of digits from 0 to 9. It is guaranteed that the total length of these q strings won't exceed 1 000 000.

Output

For each of the q strings, print "YES" if Wilbur can choose x and y in order to finish with this string after some finite number of moves. If it's impossible, than print "NO" for the corresponding string.

Examples

Input

1 1 2
0
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
0000000000000
2413423432432


Output

YES
NO


Input

4 2 5
01
23
45
67
0 1
0 -1
0 1
0 -1
0 1
0 -1
0 1
0 -1
0 1
0 -1
0000000000
010101011101
32232232322
44343222342444324
6767


Output

YES
YES
YES
NO
YES

Note

In the first sample, there is a 1 by 1 table consisting of the only digit 0. The only move that can be made is staying on the square. The first string can be written on the white board by writing 0 repeatedly. The second string cannot be written as there is no 2 on the table.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Reader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.util.LinkedList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Ruins He
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    TaskE solver = new TaskE();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskE {
    private static final int CHARSET_SIZE = 10;
    private int[] visited;
    private Graph graph;
    private int[] bbcMask;
    private int[][] mp;
    private int n;
    private int r;
    private int c;
    private List<Integer>[] ropes;
    private char[] s;

    @SuppressWarnings("unchecked")
    public void solve(int testNumber, InputReader in, OutputWriter out) {
      r = in.nextInt();
      c = in.nextInt();
      int q = in.nextInt();
      mp = new int[r][c];
      for (int i = 0; i < r; i++) {
        char[] s = in.nextChars();
        for (int j = 0; j < c; j++) mp[i][j] = s[j] - '0';
      }
      int[] a = new int[CHARSET_SIZE];
      int[] b = new int[CHARSET_SIZE];
      for (int i = 0; i < CHARSET_SIZE; i++) {
        a[i] = in.nextInt();
        b[i] = in.nextInt();
      }
      n = r * c;
      graph = new Graph(n);
      for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
          int ni = i + a[mp[i][j]];
          int nj = j + b[mp[i][j]];
          if (ni >= 0 && ni < r && nj >= 0 && nj < c) graph.addEdge(ni * c + nj, i * c + j);
          else graph.addEdge(i * c + j, i * c + j);
        }
      }

      graph.buildDirectedBBC();
      bbcMask = new int[graph.getBBCCount()];
      for (int i = 0; i < n; i++) {
        if (graph.getBBCId(i) != -1) {
          bbcMask[graph.getBBCId(i)] |= 1 << mp[i / c][i % c];
        }
      }

      ropes = new List[graph.getBBCCount()];
      for (int i = 0; i < ropes.length; i++) ropes[i] = new LinkedList<>();
      for (int i = 0; i < n; i++) {
        if (graph.getBBCId(i) != -1) {
          for (int v : graph.adj(i)) {
            if (graph.getBBCId(v) == -1) ropes[graph.getBBCId(i)].add(v);
          }
        }
      }

      visited = new int[graph.getBBCCount()];
      for (int i = 0; i < q; i++) {
        s = in.nextChars();
        int[] first = new int[CHARSET_SIZE];
        Chars.reverse(s);
        Arrays.fill(visited, 0);
        Arrays.fill(first, -1);
        for (int j = 0; j < s.length; j++) {
          if (first[s[j] - '0'] == -1) first[s[j] - '0'] = j;
        }
        boolean ok = false;
        for (int j = 0; !ok && j < n; j++) {
          int bbcId = graph.getBBCId(j);
          if (bbcId != -1 && visited[bbcId] == 0) {
            visited[bbcId] = 1;
            int id = s.length;
            for (int k = 0; k < CHARSET_SIZE; k++) {
              if (first[k] != -1 && (bbcMask[bbcId] & (1 << k)) == 0) {
                id = Math.min(id, first[k]);
              }
            }
            ok = id == s.length;
            if (ok) break;
            for (int u : ropes[bbcId]) {
              if (query(id, u)) {
                ok = true;
                break;
              }
            }
          }
        }
        out.println(ok ? "YES" : "NO");
      }
    }

    private boolean query(int pos, int u) {
      if (s[pos] - '0' == mp[u / c][u % c]) pos++;
      if (pos == s.length) return true;
      for (int v : graph.adj(u))
        if (query(pos, v)) return true;
      return false;
    }

  }

  static class Graph {
    private final List<Integer>[] edges;
    public final int n;
    private int m = 0;
    private int[] id;
    private int[] low;
    private int[] visited;
    private Object bbc;
    private Object stack;
    private int K;
    private int top;
    private int bbcCount;

    @SuppressWarnings("unchecked")
    public Graph(int n) {
      this.n = n;
      this.edges = new List[n];
      for (int i = 0; i < n; i++) {
        edges[i] = new ArrayList<>();
      }
    }

    public void addEdge(int u, int v) {
      edges[u].add(v);
      m++;
    }

    public int adjSize(int u) {
      return edges[u].size();
    }

    public Iterable<Integer> adj(int u) {
      return edges[u];
    }

    @SuppressWarnings("unchecked")
    public int getBBCId(int node) {
      return ((int[]) bbc)[node];
    }

    public int getBBCCount() {
      return bbcCount;
    }

    public void buildDirectedBBC() {
      visited = new int[n];
      id = new int[n];
      low = new int[n];
      bbc = new int[n];
      stack = new int[n];
      bbcCount = 0;
      for (int i = 0; i < n; i++) {
        if (visited[i] == 0) {
          K = top = 0;
          dfsDirectedBBC(i);
        }
      }
    }

    private void dfsDirectedBBC(int u) {
      int uId;
      boolean selfLoop = false;
      visited[u] = 1;
      low[u] = id[u] = ++K;
      ((int[]) stack)[uId = top++] = u;
      for (int v : adj(u)) {
        selfLoop |= u == v;
        if (visited[v] == 0) {
          dfsDirectedBBC(v);
          low[u] = Math.min(low[u], low[v]);
        } else if (visited[v] == 1) {
          low[u] = Math.min(low[u], low[v]);
        }
      }
      if (low[u] == id[u]) {
        int v;
        boolean circle = selfLoop || top - uId > 1;
        do {
          v = ((int[]) stack)[--top];
          visited[v] = -1;
          ((int[]) bbc)[v] = circle ? bbcCount : -1;
        } while (u != v);
        if (circle) bbcCount++;
      }
    }


    public String toString() {
      StringBuilder stringBuilder = new StringBuilder();
      stringBuilder.append("graph with ").append(n).append(" nodes ");
      int res = 0;
      for (int i = 0; i < n; i++) res += adjSize(i);
      stringBuilder.append(res / 2).append(" edges\n");
      for (int u = 0; u < n; u++) {
        for (int v : adj(u)) {
          if (u < v) {
            stringBuilder.append(u).append(" ").append(v).append("\n");
          }
        }
      }
      return stringBuilder.toString();
    }

  }

  static class Chars {
    private Chars() {
    }

    public static void reverse(char[] s) {
      for (int i = 0, j = s.length - 1; i < j; i++, j--) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
      }
    }

  }

  static class OutputWriter {
    private final PrintWriter writer;

    private OutputWriter(Writer writer, boolean autoFlush) {
      this.writer = new PrintWriter(new BufferedWriter(writer, 32767), autoFlush);
    }

    public OutputWriter(Writer writer) {
      this(writer, true);
    }

    public OutputWriter(OutputStream outputStream) {
      this(new OutputStreamWriter(outputStream), false);
    }

    public OutputWriter println(String string) {
      writer.println(string);
      return this;
    }

    public void close() {
      writer.close();
    }

  }

  static class InputReader {
    public final BufferedReader reader;
    public StringTokenizer tokenizer = null;

    public InputReader(Reader reader) {
      this.reader = new BufferedReader(reader, 32767);
    }

    public InputReader(InputStream inputStream) {
      this(new InputStreamReader(inputStream));
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public char[] nextChars() {
      return next().toCharArray();
    }

  }
}

