Wildcard routes: hints, no solution

A web router holds route patterns such as /users/*/orders. Every segment must match exactly, except a star, which stands for exactly one non-empty segment of the request. A request path never contains a star. A star never matches zero segments or several segments.

For each request, return the index (starting at 0) of the route that matches it. If several routes match, choose the one with the fewest stars, and if they still tie, the one that appears first in the list. Return -1 when no route matches. Paths start with a slash and have no trailing slash; the root path is a lone slash, which matches only itself.

Examples

Input

routes = ["/users/*/orders", "/users/me/orders", "/health"], requests = ["/users/me/orders", "/users/42/orders", "/health", "/users"]

Output

[1, 0, 2, -1]

Note

The exact route beats the star route; the star route handles user 42; /health is route 2; /users matches nothing.

Input

routes = ["/a/*/c", "/a/b/*"], requests = ["/a/b/c"]

Output

[0]

Note

Both routes have one star, so the earlier one wins.

Input

routes = ["/", "/*"], requests = ["/", "/a", "/a/b"]

Output

[0, 1, -1]

Note

The lone slash matches only the root route; a star needs one segment and never matches two.

Constraints

• 0 <= routes.length <= 30000 and 1 <= requests.length <= 30000
• Each path has at most 8 segments
• Segments are lowercase letters and digits; only route segments may be a single star

Hint 1: a nudge

When two routes both match a request, what tells you which one wins? Work out what should happen with /a/*/c and /a/b/* for the request /a/b/c.

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing