Dependency Management

Note: Python submissions should use Python 3.6 (PyPy 7.3), as submissions using Python 3.8 may not be fast enough to pass some subtasks.

You've decided to import two different software libraries into your project: $A$ and $B$. Library $A$ itself depends on $N$ other libraries, and similarly, library $B$ depends on $M$ other libraries. Some of library A's dependencies may also be a dependency for library B - that is, the two libraries may share some common dependencies.

Every library has one or more versions. Version numbers are integers, with higher values indicating that the version is newer. There are $V_A$ different versions of library $A$ and $V_B$ different versions of library $B$. The versions of $A$ are numbered from $0$ to $V_A-1$ and the versions of $B$ are numbered from $0$ to $V_B-1$. Each dependency of $A$ or $B$ also has a certain number of versions, although the version numbers for those libraries may not follow any specific pattern.

Each specific version of library $A$ or $B$ uses a specific version of each of its dependencies. For two versions of A and B to be compatible, they must both use the same versions for any dependencies they have in common. You want to find the compatible pair of versions that has the newest version of A possible.

Input

• The first line consists of the integers $N$, $M$, $V_A$, $V_B$ separated by spaces.
• The second line contains $N$ space-separated strings. Each one is the name of one of the dependencies of $A$.
• $V_A$ lines will follow, each corresponding to a version of library $A$, in order from $0$ to $V_A-1$. Each line contains $N$ space separated integers, representing the versions used for each dependency of $A$. The numbers are in the same order as the dependency names in the second line.
  
• The following line contains $M$ space-separated strings. Each one is the name of one of the dependencies of $B$.
• $V_B$ lines will follow, each corresponding to a version of library $B$, in order from $0$ to $V_B-1$. Each line contains $N$ space separated integers, representing the versions used for each dependency of $B$. The numbers are in the same order as the dependency names of $B$.

Output

Output the compatible pair of versions with the newest version of A possible. If there are multiple such pairs, break the tie by printing the pair with the newer version of B.

Constraints

For all subtasks:

• $1 \le N, M \le 10$
• $1 \le V_A, V_B \le 50,000$
• The name of each dependency will only contain alphabetical or numeric characters (a-z and 0-9), and will be at most 10 characters long.
• Each unique dependency has a unique name
• $A$ does not depend on $B$, and vice-versa
• There is at least one compatible pair of versions
• Each version number is a non-negative integer less than $1,000,000$

Subtasks

• Subtask 1 (+15%): $N = M = 1$, $V_A \le 500$, $V_B = 1$.
• Subtask 2 (+20%): $N = M = 1$, $V_A, V_B \le 500$.
• Subtask 3 (+30%): $V_A, V_B \le 500$.
• Subtask 4 (+35%): No further constraints apply.

Sample Explanations

Sample 1

In this case, library $A$ has 2 versions, with the latest being version 1, and library $B$ has a single version (version 0). Additionally, library $A$ only depends on the leftpad library, and library $B$ only depends on log4j. Therefore we don't have to worry about common dependencies, so we can just import that latest versions of both libraries (1 and 0 respectively).

Sample 2

Both $A$ and $B$ depend on numpy. Version 1 of $A$ requires numpy version 19. However, library $B$ always requires numpy version 14. Therefore, we must use version 0 of $A$ and version 0 of $B$, as their numpy versions match.

Sample 3

The shared dependencies in this case as grpc and junit. Version 1 of $A$ is the latest such version that has matching versions of grpc and junit with library $B$. Although both versions 1 and 2 of $B$ are compatible with version 1 of $A$, we choose version 2 of $B$ as it is the latest compatible one.

Note: Python submissions should use Python 3.6 (PyPy 7.3), as submissions using Python 3.8 may not be fast enough to pass some subtasks.