Mr. BG, a popular math teacher at school, is preparing his classroom for the new semester. While playing think music in his head, he decides to create a seating plan. He believes that the optimal seating arrangement is the key to a productive and harmonious learning environment. His classroom is arranged in a rectangular grid of desks.

This semester, he wants to arrange students based on their social dynamics. He has collected data on which students are friends and which are rivals. He also has a list of students who are known to be disruptive if seated too close to one another.

His goal is to find the maximum possible number of “satisfied” friendship pairs he can achieve while adhering to his rules.

A friendship pair is satisfied if the two friends are seated in adjacent desks (up, down, left, or right).

Problem

You are given the dimensions of the classroom, a list of students, and their relationships. For reference, the students will be numbered 1 to N based on the order they appear in the input.  

The arrangement must follow these strict rules:

• Rivals: No two students who are rivals can be seated in adjacent desks.
• Disruptive Students: No two students who are marked as disruptive can be seated in adjacent desks.

If no arrangement can satisfy the strict rules, the output should be Impossible.

Input

The input will be provided in the following format:

• The first line contains two space-separated integers, R and C, representing the number of rows and columns of desks.
• The second line contains a single integer, N, the number of students.
• The next N lines each contain a student's name and a status (GOODBOY or DISRUPTIVE). These correspond to Student 1, Student 2 ... Student N in the order they are listed.
• The next line contains a single integer, F, the number of friendship pairs.
• The next F lines each contain two space-separated student names, identifying a friendship between two of the numbered students.
• The next line contains a single integer, V, the number of rivalry pairs.
• The next V lines each contain two space-separated student names, identifying a rivalry between two of the numbered students.

Output

If a valid arrangement exists, print a single integer: the maximum number of satisfied friendship pairs.

Otherwise print: Impossible

Constraints

• 1 ≤ R, C ≤ 4
• 1 ≤ N ≤ R × C
• 0 ≤ F ≤ N × (N - 1) / 2
• 0 ≤ V ≤ N × (N - 1) / 2
• Student names will be unique, consist of alphanumeric characters, and have a length between 1 and 10.

Example

Input:
2 2
4
Yij GOODBOY
Johnson DISRUPTIVE
Adam DISRUPTIVE
Marcus GOODBOY
2
Yij Johnson
Adam Marcus
1
Yij Adam

Output:
1

Explanation

We cannot place Yij and Adam adjacent, due to their rivalry.

We also cannot place Johnson and Adam adjacent, because both are disruptive.

The best valid configuration satisfies 1 friendship (either Yij–Johnson or Adam–Marcus), without violating any rules.