Covid-19

To help prevent the spread of the coronavirus, it has been decided to identify contacts and require them to self-isolate.

Contacts are defined as those who have been near individuals infected with the coronavirus for at least 5 minutes.

Individuals who are not direct contacts but have been near contacts for at least 5 minutes are advised to undergo coronavirus testing.

Your task is to determine the list of individuals who need to self-isolate and the list of individuals who need to take a coronavirus test.

Input Data

The first line provides the total number of individuals N (3 ≤ N ≤ 1000).

The second line specifies the number M – the number of individuals infected with the coronavirus, followed by their list C[i] (1 ≤ i ≤ M).

The third line indicates the number K – the number of contact records.

The next K lines each describe a contact record with three integers: two individual numbers and the number of minutes they were in contact.

Output Data

On the first line, list in ascending order the numbers of individuals who need to self-isolate. On the second line, list in ascending order the numbers of individuals who need to take a coronavirus test.

Examples

Note

Based on the input data, individual 4 is infected with the coronavirus.

Since individual 4 was in contact with individual 3 for at least 5 minutes (6 minutes), individual 3 is considered a contact and must self-isolate.

Individuals 2 and 5 were in contact with individual 3 for at least 5 minutes (7 and 6 minutes respectively), so they are advised to undergo coronavirus testing.