Employee Project Work Period Query

You are given a set of projects and employee work periods on those projects. Each project is active between a start and an end date, and each employee works on a project during a specified period. However, an employee's effective working period on a project is defined by the intersection of the project's active period and the employee's recorded work period.

Formally, for a project active from \(t_{start}\) to \(t_{end}\) and an employee's work period on that project from \(d_{start}\) to \(d_{end}\), the effective work period is \[ [\max(t_{start}, d_{start}),\; \min(t_{end}, d_{end})] \] An employee is considered working on a query date if the date lies within any of his/her effective work periods.

Your task is to process multiple query dates. For each query date, determine the list of unique employee IDs, sorted in lexicographical order, who are actively working (i.e. whose effective work period covers the query date). If no employee is active on that day, output an empty line.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

1. The first line contains two space-separated integers, P and W, where P is the number of projects and W is the number of employee work periods.
2. The next P lines each contain three values: project_id (a string), start_date (in YYYY-MM-DD format), and end_date (in YYYY-MM-DD format).
3. The following W lines each contain four values: employee_id (a string), project_id (a string), first_date (the start date of the work period in YYYY-MM-DD format), and last_date (the end date of the work period in YYYY-MM-DD format).
4. The next line contains a single integer, Q, the number of query dates.
5. The following Q lines each contain a query date (YYYY-MM-DD).

outputFormat

For each query date, output a single line to standard output (stdout) containing the sorted (in lexicographical order) unique employee IDs who are actively working on that date. Employee IDs should be separated by a single space. If no employees are active on the query date, output an empty line.

## sample

2 4
P1 2023-01-01 2023-12-31
P2 2024-01-01 2024-12-31
E1 P1 2023-01-10 2023-01-20
E2 P1 2023-01-15 2023-02-10
E3 P2 2024-03-01 2024-03-20
E1 P2 2024-01-05 2024-01-15
3
2023-01-15
2023-01-25
2024-01-10

E1 E2
E2
E1

</p>