Database

In a company, there are N employees, and among them, there are M "supervisor-subordinate" relationships. An employee can have multiple supervisors and subordinates, but there is no cycle of "supervisor-subordinate" connections that starts and ends with the same employee.

Access to the corporate database is controlled by a system of rights. At any moment, it is clear whether each employee has access rights to the database. Initially, when the database was set up, no one had access rights. Over time, access rights are modified through the following operations:

1. The administrator grants access rights to employee X.

2. The administrator revokes access rights from employee X.

3. Employee X begins sharing access rights with all direct subordinates.

4. Employee X begins sharing access rights with all direct subordinates. Then, for each direct subordinate of employee X, operation 4 is performed.

5. Employee X stops sharing access rights with all direct subordinates.

Employee X has access rights to the corporate database if at least one of the following conditions is satisfied:

1. The last operation by the Administrator concerning employee X was granting them rights.

2. At least one of the direct supervisors, who currently has rights, shares access rights with them.

Note: If an employee shares access rights with their subordinates and then loses their own rights, they continue to share rights with their subordinates. However, the subordinates cannot gain rights from this until the employee regains access rights. (Refer to the second example in the explanation).

Write a program that, given a sequence of operations modifying access rights to the corporate database, determines for each employee whether they will have access rights after executing this sequence of operations.

For the given sequence of operations, the following constraints apply: For each employee, operations 1 and 2 do not appear consecutively. Operations 3 and 4 do not occur when the employee does not have access rights at that time. Operation 5 does not occur when the employee is not sharing rights with their subordinates.

Input

The first line contains two integers: the number of employees N (1 ≤ N ≤ 10000) and the number of "supervisor-subordinate" connections M (1 ≤ M ≤ 50000). The next M lines each contain two natural numbers X and Y (1 ≤ X, Y ≤ N), indicating that X is the direct supervisor of Y. The following line contains the number K (1 ≤ K ≤ 20000) - the number of operations modifying rights. The subsequent K lines each contain two natural numbers T and X (1 ≤ T ≤ 5, 1 ≤ X ≤ N) - the type of operation and the employee number it applies to, respectively.

Output

The output should be a single line containing N integers, separated by spaces. The i-th number is 1 if the i-th employee has access rights after executing the given commands, or 0 if they do not.

Explanation for Example 1

1. The 1st employee receives access rights from the administrator.

2. The 1st employee starts sharing access rights with the 2nd and 3rd employees. Consequently, the 2nd shares with the 4th, and the 3rd shares with the 4th and 5th employees.

3. The 2nd employee receives access rights from the administrator.

4. The 1st employee stops sharing access rights with the 2nd and 3rd employees. As a result, the 3rd employee loses access rights, but the 2nd employee does not, as they have access rights from the administrator. The 4th employee also retains access rights because the 2nd employee has rights and shares them. The 5th employee loses rights because the 3rd employee, although sharing rights, does not currently have them.

Explanation for Example 2

1. The 1st employee receives access rights from the administrator.

2. The 1st employee starts sharing access rights with the 2nd employee. The 2nd employee receives rights because the 1st has rights and shares them.

3. The administrator revokes rights from the 1st employee. The 2nd employee also loses rights because the 1st, although sharing rights, does not currently have them.

4. The 1st employee receives access rights from the administrator. The 2nd employee receives rights because the 1st employee currently has rights and shares them.

Examples