Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

Dependency Management

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 2.6 seconds

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 seperated by spaces.
  • The second line contains N space-seperated 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 seperated 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-seperated 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 seperated integers, representing the versions used for each dependency of B. The numbers are in the same order as the dependency names of B.

Output

Ouput 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.

  • Sample Input 1

    1 1 2 1
    log4j
    14
    19
    leftpad
    12
    

    Sample Output 1

    1 0
    
  • Sample Input 2

    1 1 2 1
    numpy
    14
    19
    numpy
    14
    

    Sample Output 2

    0 0
    
  • Sample Input 3

    3 3 4 3
    apache grpc junit
    1 8 3
    2 9 3
    3 11 4
    4 13 4
    spring grpc junit
    5 8 3
    6 9 3
    7 9 3
    

    Sample Output 3

    1 2