Robotic Class

Baby volcano is now at a robotic class. In this class, babies are required to program a special control system of a robot. This control system has a real-valued control variable $x$, which captures the behavior of this robot. In addition, this control system could be abstracted as an acyclic directed graph, with $n$ node, the nodes are indexed from $1$ to $n$. In this graph, the node $n$ has no output edge, termed as the output node. Moreover, for each vertex $t,1\leq t<n$, there is a number $k_t$, a set of $integer$-$valued$ limits $a_{t,0}<a_{t,1}<a_{t,2}<\cdots<a_{t,k_{t}-1}<a_{t,k_t}:=+\infty$, and a set of $integer$-$valued$ coefficients, bias and destinations $c_{t,0},b_{t,0},d_{t,0} ,c_{t,1},b_{t,1},d_{t,1},c_{t,2},b_{t,2},d_{t,2}\cdots,c_{t,k_t},b_{t,k_t},d_{t,k_t}$. For every $t$ and $i, 0\leq i\leq k_t$, $-1\leq c_{t,i}\leq 1$.

To use this system to control the robot, the user follows the steps below:

1. Choose $x_0$ and initialize $x:=x_0$, then choose some node $s_0$ and set the currect node $t:=s_0$
2. If $t$ is the output node$(t=n)$, then output $x_{out}:=x$, else go to step 3.
3. The user finds the smallest $i$ such that $a_{t,i}\geq x$(Note that $i$ always exists), then transform $x:=c_{t,i}\times x+b_{t,i}$, and set $t:=d_{t,i}$, and go back to step 2.

Note that for every fixed $s_0$, the output value $x_{out}$ is a function with respect to the initial value $x_0\in \mathbb R$, we call this function $C_{s_0}(x_0)$.

To precisely control the robot, it is required that for every initial node $s_0$, $C_{s_0}(x_0)$ is continuous with respect to $x_0$.

A function $f(x),x\in \mathbb R$ is continuous with respect to $x$ iff
$$\forall x\in \mathbb R,\forall \epsilon>0,\exists \delta>0,\forall x'\in \mathbb R, (|x-x'|\leq \delta \implies |f(x)-f(x')|\leq \epsilon)$$

You need to verify this requirement is satisfied or not. In other words, if for every initial node $s_0$, $C_{s_0}(x_0)$ is continuous with respect to $x_0$, you should output ''YES''. If there exists some node $s^*$ such that $C_{s^*}(x_0)$ is not continuous, you should output ''NO''.

In the first line there is one integer $T$, denotes the number of test cases.

The rest of input has $T$ part, each part corresponds to a test case.

For each part, in the first line there is a number $n$, denotes the number of nodes.

In the next $n-1$ lines, the $i$-th line starts with $k_i$, follows with $4k_i+3$ integers, they are $c_{i,0},b_{i,0},d_{i,0},a_{i,0},c_{i,1},b_{i,1},d_{i,1},a_{i,1},\cdots, a_{i,k_i-1},c_{i,k_i},b_{i,k_i},d_{i,k_i}$.

It guarantees that $1\leq T\leq 100$,
and in a single test cases,
$1\leq n\leq 500$,
$1\leq \sum{k_i}\leq 2000$,
$-1\leq c_{i,j}\leq 1$,
$-10^6\leq b_{i,j}\leq 10^6$,
$-10^9\leq a_{i,j}\leq 10^9$,
$i+1\leq d_{i,j}\leq n$.
And it guarantees that $a_{i,j-1}<a_{i,j}$ for every $1\leq j< k_i$.

For each test case, you should firstly output ''Case #t: ''(without quotes), where $t$ is the index of this test case, then if for every initial node $s_0$, $C_{s_0}(x_0)$ is continuous with respect to $x_0$, you should output ''YES''. If there exists some node $s^*$ such that $C_{s^*}(x_0)$ is not continuous, you should output ''NO''.

3
4
1 1 1 2 -4 -1 -7 3
0 -1 -2 4
0 1 4 4
4
1 1 1 2 -4 -1 -7 3
0 -1 -3 4
0 1 4 4
1

Case #1: YES
Case #2: NO
Case #3: YES

2020中国大学生程序设计竞赛（CCPC） - 网络选拔赛