Calculate Service Uptime

You are given the operational period of a service and a series of log events. Each query consists of a period specified by a start time and an end time, and an ordered list of log events. Each log event is represented by a timestamp and a status (either active or inactive). Your task is to compute the total uptime (in seconds) of the service during the given period, based on these logs.

The service is considered active during periods where an active event has started and not yet been ended by an inactive event, and inactive otherwise. Formally, if you denote the start time of a query as \( s \) and the end time as \( e \), then the uptime is calculated by summing all intervals \( [t_a, t_b] \) within \([s,e]\) during which the service was active.

Note that logs may occur before or after the queried period. Any active event occurring before the period should be considered if it carries over into the period. Similarly, events occurring after the period should be ignored except as needed to finalize an active interval that began inside the period.

inputFormat

The input is read from stdin and has the following format:

Q
s1 e1
N1
timestamp1.1 status1.1
...
timestamp1.N1 status1.N1
s2 e2
N2
timestamp2.1 status2.1
...
timestamp2.N2 status2.N2
...
sQ eQ
NQ
timestampQ.1 statusQ.1
...
timestampQ.NQ statusQ.NQ

Where:

• Q is the number of queries.
• For each query, s and e are the start and end times (in seconds since Unix epoch).
• N is the number of log entries for that query.
• Each log entry contains a timestamp (an integer) and a status (a string that is either active or inactive).

outputFormat

For each query, output a single integer on a new line representing the total uptime (in seconds) within the specified period. The output is printed to stdout.

## sample

2
1609459200 1609459800
5
1609459200 active
1609459500 inactive
1609459650 active
1609459800 inactive
1609470000 inactive
1609461000 1609461600
4
1609461000 inactive
1609461200 active
1609461400 inactive
1609461600 active

450
200

</p>