Highway from Hell

To get to Griffith Park, P-22 has to cross several freeways. Freeways in LA can have as many as 62 lanes, so crossing them is dangerous. Cars drive at different speeds, and if one hits P-22, he is dead. Write a program that decides whether a proposed crossing strategy lets P-22 survive. If it does not, the program reports the first time step at which he is hit, so he can improve the plan.

We model P-22 and each car as a $1 \times 1$ square with its edges excluded, so mathematically the square is $(0, 1) \times (0, 1)$. Every coordinate given is the bottom left corner of its square. P-22 starts at $(0, 0)$ and must reach $(0, L + 1)$, where $L$ is the number of lanes. Lane $i$ spans the y-coordinates from $i$ to $i + 1$. Lanes $0$ and $L + 1$ lie just outside the traffic.

In each time step, P-22 moves exactly one lane up or down, or stays put. He cannot cross more than one lane in a step, and he never moves left or right. The strategy is a string of '+', '-', and '0' characters. The character at position $t$ says what P-22 does from time $t$ to time $t + 1$: '+' moves him one lane up, '-' one lane down, and '0' keeps him in place. All strategies are legal. They never move below lane 0 or above lane $L + 1$, and if P-22 survives, he reaches lane $L + 1$ exactly at the final step. He never reaches lane $L + 1$ earlier, and he does not step back onto the freeway after crossing it.

Each car stays in its lane and drives at a constant speed. When P-22 crosses a lane, he partly occupies both the lane he leaves and the lane he enters, so cars in either lane can hit him. He is not hit by a car in another lane while he waits in one lane, because the edges are excluded.

The first line contains $1 \le K \le 100$, the number of data sets. Each data set starts with a line holding two integers $n$ and $L$, where $0 \le n \le 1000$ is the number of cars and $1 \le L \le 100$ is the number of lanes. Next come $n$ lines, each with an integer $\ell_i$ and two floating point numbers $s_i$ and $v_i$. Here $\ell_i$ is the lane of car $i$, $s_i$ is its position along the x-axis at time 0, and $v_i > 0$ is its speed, meaning how far it moves in one time step. The last line of the data set is P-22's strategy, a string of at most 1000 characters made of '+', '-', and '0'.

You do not need to worry about cars crashing into each other.

For each data set, print a line reading Data Set x:, where $x$ is the data set number. On the next line, print success if P-22 reaches the other side. Otherwise, print the first integer time step during which P-22 is hit by a car. Print a blank line after each data set.