Find Clients Outside Provider Coverage

Given collections of healthcare providers and clients, along with a maximum allowed service distance maxDistance, return the IDs of every client who is not fully covered.

Each provider has:

• providerId: string
• specialties: string[]: the services that provider supplies
• location: [x, y]: the provider's position in a two-dimensional coordinate system

Each client has:

• clientId: string
• requirements: string[]: the services the client needs
• location: [x, y]: the client's position in a two-dimensional coordinate system

For points (x1, y1) and (x2, y2), calculate Euclidean distance as follows:

distance = sqrt((x1 - x2)^2 + (y1 - y2)^2)

A client's individual requirement is covered when there is at least one provider that satisfies both conditions:

1. The provider lists that service in specialties.
2. The provider is no farther than maxDistance from the client.

A client belongs in the result if any one of its requirements cannot be covered. Separate requirements for the same client may be fulfilled by separate providers. Providers and clients are allowed to share a location.

Example

Providers:
101, [ortho, cardio, pedi], [1, 2]
102, [pedi], [3, 4]
103, [ortho, cardio, pedi], [1, 8]
104, [ortho], [4, 2]
105, [ortho, pedi], [5, 1]

Clients:
201, [ortho, cardio], [4, 1]
202, [ortho], [3, 2]
203, [pedi], [5, 5]
204, [ortho, pedi], [2, 2]
205, [cardio], [3, 3]

maxDistance = 3

The result is:

[203]

Constraints

• 1 <= P, C <= 10^5, with P representing the provider count and C representing the client count
• Every specialties or requirements list contains between 1 and 20 entries
• Coordinates are finite-precision floating-point values
• 0 <= maxDistance <= 10^9

Example

Input:

5 5 3
101 ortho,cardio,pedi 1 2
102 pedi 3 4
103 ortho,cardio,pedi 1 8
104 ortho 4 2
105 ortho,pedi 5 1
201 ortho,cardio 4 1
202 ortho 3 2
203 pedi 5 5
204 ortho,pedi 2 2
205 cardio 3 3

Output:

203