URL Router Matching

In web backend development, one important component is the router. A router is defined by a path pattern that maps URL requests to actions. A URL request has the form:

/segment1/segment2/.../segmentk

or

/segment1/segment2/.../segmentk?parameter_list

When a request reaches the server, only the part before the '?' is considered for routing. In the router pattern, each segment can be a literal string or a dynamic token. A dynamic token is denoted by a colon followed by a name (for example, :handle). For each dynamic token, a regular expression is provided that specifies the allowed format for that segment.

When matching, the router pattern is split by '/' into segments. For a literal segment, an exact match is required. For a dynamic token, the corresponding segment in the URL must match the regex provided. If the number of segments does not match, or if any segment fails to match its required format, the request is considered to not match the router.

If a request matches, the extracted values for all dynamic tokens are passed to the corresponding action. The extracted values are output in the order they appear in the router pattern, separated by a single space. If there are no dynamic tokens, output an empty line.

Regex Grammar Note: The provided regular expressions follow a simplified grammar. In particular, when using quantifiers, they are given in the form \( \{lower,upper\} \) where lower and upper are non-negative integers with \(upper\) being either an integer (\(\leq 20\)) or omitted (meaning no upper bound). Other constructs include literal characters, character classes such as [a-z] (which matches any lowercase letter), and alternation using the | symbol. In your implementation, you may use built‐in regex libraries to perform full matching (i.e. the entire string must match the pattern).

inputFormat

The input consists of several parts:

1. A line containing the router pattern string. The pattern is a URL path beginning with a '/' and consists of segments separated by '/'. A segment that begins with ':' denotes a dynamic token.
2. A line containing an integer K representing the number of dynamic tokens in the pattern.
3. K lines follow. Each line contains a dynamic token name (without the ':') and its regular expression (using the simplified grammar described above), separated by a space.
4. A line containing an integer Q representing the number of URL requests.
5. Q lines follow. Each line is a URL request. Note that if the request contains a '?' character, only the part before '?' should be considered for matching.

outputFormat

For each of the Q requests, output one line:

• If the request matches the router pattern, output the extracted values of the dynamic tokens in the order they appear, separated by a single space. If there is no dynamic token, output an empty line.
• If the request does not match, output 404 (without quotes).

sample

/user/:handle/show
1
handle [a-z]+
4
/user/testuser/show
/user/testuser/show?avatar=true
/user/12345/show
/user/test/user/show

testuser
testuser
404
404