Description

We describe this problem on a 2D plane. First, we list out some elements of the game.

• Player: Dino. We treat Dino as a point.
• Obstacle:
  • Cactus: A segment, whose endpoints are $(x_i',0)$ and $(x_i',h_i)$.
  • Bird: A segment, whose endpoints are $(x_i,d_i)$ and $(x_i,u_i)$.
• Game Over: The game ends, once the position of Dino coincides with any obstacle, including the both ends of the segments.
• Starting point: $(0,0)$ (origin).
• Endpoint: The position of Dino when the game ends. It is possible that the game has no endpoint, i.e. Dino can go forever.
• Score: The $x$-coordination of the endpoint. When there is no endpoint, the score is defined to be infinity.
• Jumping arguments: Positive integers $d,h$.
• Walking: Dino moves towards the positive direction of the $x$-axis when Dino is on the $x$-axis.
• Jumping: When Dino is on the $x$-axis, Dino can perform a jump. Take the point where Dino starts jumping as origin, the trajectory of jumping can be described as the following function:$$f(x) = \begin{cases} \displaystyle \frac{h}{d}x & x\in [0, d) \\ \displaystyle-\frac{h}{d}x+2h & x\in [d, 2d) \\ \end{cases}$$
  • Note that, we can infer that, it is possible to make the second jump immediately right after the first jump ends.
  • Note that, it is possible to make a jump at an arbitrary point with a real coordination (as long as it is on the $x$-axis), not necessarily at an integer point.

The figure below shows a jump where $d=2,h=6$.

In a round of game, starting from the origin, Dino moves towards the positive direction of $x$-axis. The goal is to maximize the score, that is, to bypass the obstacles, making himself move as far as possible.

At every instant, Dino can only do one thing: Walk, or jump. Dino can make a jump if and only if he is on the $x$-axis.

Formally, the behavior of Dino can be described as a sequence of length $(k+1)$ consisting of tuples of real numbers $[(x_0,t_0),(x_1,t_1),\cdots,(x_k,t_k)]$, where the following conditions holds:

• $x_0=0$;
• $t_i\in \{0,1\}$;
• $\forall 0\le i\lt k$, $x_i\lt x_{i+1}$;
• $t_i=1,i\lt k\implies x_{i+1}-x_i\ge 2d$; (You cannot make the second jump before the first jump ends)
• $\forall 0\le i\lt k$, $t_i=t_{i+1}\implies t_i=t_{i+1}=1$.

When $t_i=0$, we say Dino starts walking at $x_i$; Otherwise, when $t_i=1$, we say Dino starts jumping at $x_i$.

The game ends when the position of Dino coinsides with any obstacle. Let's say the position of Dino, at this moment, is the endpoint; and the score is the $x$-coordination of the endpoint.

There are $b$ birds and $c$ cacti. You are to calculate the maximum possible score that Dino can obtain. Specially, the score can be infinity.

For better understanding, see the figure in the sample description.

Input Format

The first line, an integer $T$ — the number of rounds.

For each round:

• The first line contains two positive integers $d,h$ — jumping arguments.
• The second line contains two integers $b,c$ — the number of birds and the number of cactus, respectively.
• The following $b$ lines contains three integers $x_i,u_i,d_i$ — the birds.
• The following $c$ lines contains three integers $x_i',h_i$ — the cacti.

Output Format

Output a line for each round, indicating the maximum possible score.

Specially, when the score is infinity, output a line containing Dino!.

2
1 3
1 2
1 2 1
2 2
3 2
1000000000 1000000000
1 0
114514 1919 810

3
Dino!

1
8 16
8 3
5 18 13
4 20 10
6 13 1
2 17 11
1 11 6
5 1 1
2 6 3
1 16 1
7 20
7 13
3 2

6

1
5 5
1 2
5 5 1
6 1
16 3

16

1
5 5
1 4
19 10 8
4 1
15 1
22 2
20 1

22

Hint

Explanation of sample $1$:

• For the first round, Dino can't bypass the second cactus, thus the answer is the $x$ coordination of the second cactus.
• For the second round, for example, Dino can bypass the only obstacle by starting jumping at origin.

A possible move of the first round is shown below, in which red segments denote the birds, green segments denote the cacti and pink segments denote Dino.

Contraints

• Subtask 1 (5 pts): $c=0$;
• Subtask 2 (5 pts): $b,c \le 10$;
• Subtask 3 (20 pts): $b=0$;
• Subtask 4 (20 pts): $1 \le d,h,x_{b_i},d_i,u_i,x_i',h_i \le 10^5$;
• Subtask 5 (40 pts): No further contraints.
• Subtask 6 (10 pts): No further contraints.

It is guaranteed that

• $1 \le T \le 10$;
• $0 \le b,c \le 2\times 10^4$;
• $1 \le d,h,x_{b_i},d_i,u_i,x_i',h_i\le 10^9$;
• $d_i\le u_i$.