Problem D
2-Dimensional Indexing

When reverse engineering a complex application one powerful method is tracing. Unfortunately, depending on what information is collected, tracing can produce an immense quantity of data. In general, trace data consist of a list of observations, each with an ID, memory address, length, starting time, and ending time. For example, observations might include information about modules dynamically loaded by an application: in this case the ID would identify the module, the address the module’s base address, the length the size of the module as loaded in memory, and the starting and ending time would indicate when it was loaded and, if applicable, when it was unloaded. Similarly other kinds of trace data, such as execution breakpoints, can be encoded as observations.

Traces are usually generated as a program executes, and so the ending time of an observation is usually unknown at the observation’s starting time. Therefore observations are recorded as pairs of events, with each event marking either the start or end of an observation. Events are captured in order of time; depending on the duration of an observation, its End event may be far separated from its corresponding Start event.

Perhaps the most obvious way for a user to inspect and manually analyze the observations is to plot them as boxes on screen, using one axis for time and the other for memory. The user can then zoom and pan. For this to be a fluid and responsive experience, the observations currently visible in the current viewport need to be queried and painted on the screen quickly.

Task

You will read in a list of observations and a list of queries. Each query describes the user’s viewport as a rectangle in the time-memory plane. Only some observations are visible in that viewport (intersect with the viewport rectangle in at least one point). Since the number of observations visible within a viewport may be too large to render in a useful way, if there are more than $20$ observations in the viewport, then only the observations with the $20$ smallest ID values should be painted.

Note that all starting and ending times and addresses are inclusive. An observation is visible in the viewport even if it intersects the viewport only at its edge or corner.

Implement an algorithm that computes how many observations are visible for each query, and gives the IDs of the observations that should be painted.

Input

The first line of input has two positive integers $N$ and $Q$, the number of observation events and the number of queries, respectively. Each of the next $N$ lines takes one of two forms:

• $i$ Start $t$ $x$ $L$

• $i$ End $t$

where Start and End are string literals, $i$ ($0\leq i<2^{64}$) is the base-$10$ ID of an observation, $t$ ($0\leq t < 2^{64}$) is a base-$10$ timestamp, $x$ is a non-negative hexadecimal address prefixed with 0x, and $L$ is a positive base-$10$ length such that $x+L<2^{64}$. There is exactly one Start and End event for each observation ID, and every End event is preceded by a Start event earlier in the list of events with the same ID. Timestamps are nondecreasing.

Each of the next $Q$ lines starts with the string literal Query followed by $4$ space-separated values $t_1$, $t_2$ ($0\leq t_1 < t_2 < 2^{64}$), the base-$10$ start and end times for the query, and $x_1$, $x_2$ ($0\leq x_1<x_2 < 2^{64}$) the hexadecimal addresses beginning with 0x.

All letters in hexadecimal strings are lowercase and do not have leading zeros after the 0x prefix.

For all test cases, $1 \leq N, Q \leq 2\, 000$, $L < 2^{16}$. No observation will span a time range greater than $2^{16}$. The starting time and addresses of all observations are chosen uniformly at random from the range $[0, 2^{64})$.

Output

Output $Q$ lines giving the number of visible observations and the IDs of the observations to render in the viewport for each query. Each output line must start with a base-$10$ integer $k$, the number of observations in the viewport for the query. If $k$ is greater than $20$ then output the $20$ smallest ID values of observations in the viewport in ascending order. If $k$ is less than or equal to $20$ then output the $20$ smallest ID values of observations in the viewport in ascending order.

6 5
0 Start 100 0x00400000 8192
1 Start 104 0x00601234 4
1 End 104
2 Start 120 0x7fff0000 4096
0 End 130
2 End 130
Query 0 10 0x00000000 0x00000fff
Query 0 100 0x00000000 0x003fffff
Query 100 110 0x00400000 0x0040000f
Query 100 120 0x00401000 0x00601fff
Query 100 140 0x00402000 0x80001fff

0
0
1 0
2 0 1
2 1 2