Fly Around the World

After hearing the story of Dr. Zhang, Wowo decides to plan his own flight around the world.

He already chose n checkpoints in the world map. Due to the landform and the clouds, he cannot fly too high or too low. Formally, let b_i be the height of Wowo's aircraft at checkpoint i, x_i^-≤ b_i≤ x_i^+ should be satisfied for all integers i between 1 and n, where x_i^- and x_i^+ are given integers.

The angle of Wowo's aircraft is also limited. For example, it cannot make a 90-degree climb. Formally, y_i^-≤ b_i-b_{i-1}≤ y_i^+ should be satisfied for all integers i between 2 and n, where y_i^- and y_i^+ are given integers.

The final limitation is the speed of angling up or angling down. An aircraft should change its angle slowly for safety concerns. Formally, z_i^- ≤ (b_i - b_{i-1}) - (b_{i-1} - b_{i-2}) ≤ z_i^+ should be satisfied for all integers i between 3 and n, where z_i^- and z_i^+ are given integers.

Taking all these into consideration, Wowo finds that the heights at checkpoints are too hard for him to choose. Please help Wowo decide whether there exists a sequence of real numbers b_1, …, b_n satisfying all the contraints above.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 66 666). Description of the test cases follows.

The first line of each test case contains a single integer n (3 ≤ n ≤ 100 000).

The i-th of the next n lines contains two integers x_i^-, x_i^+ (-10^8≤ x_i^-≤ x_i^+≤ 10^8) denoting the lower and upper bound of b_i.

The i-th of the next n-1 lines contains two integers y_{i+1}^-, y_{i+1}^+ (-10^8≤ y_{i+1}^-≤ y_{i+1}^+≤ 10^8) denoting the lower and upper bound of b_{i+1}-b_i.

The i-th of the next n-2 lines contains two integers z_{i+2}^-, z_{i+2}^+ (-10^8≤ z_{i+2}^-≤ z_{i+2}^+≤ 10^8) denoting the lower and upper bound of (b_{i+2}-b_{i+1}) - (b_{i+1}-b_i).

It is guaranteed that the sum of n over all test cases does not exceed 200 000.

It is guaranteed that relaxing every constraint by 10^{-6} (i.e., decrease x_i^-, y_i^-, z_i^- by 10^{-6} and increase x_i^+, y_i^+, z_i^+ by 10^{-6}) will not change the answer.

Output

For each test case, output YES if a sequence b_1,…, b_n satisfying the constraints exists and NO otherwise. The sequence b_1,…, b_n is not required.

Example

Input

4 3 0 1 0 1 0 1 1 1 1 1 -100 100 3 -967 541 -500 834 -724 669 -858 978 -964 962 -645 705 4 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 4 0 0 33 34 65 66 100 100 0 100 0 100 0 100 0 0 0 0

Output

NO YES YES NO

Note

In the first test case, all b_i's are in [0,1]. Because of the constraints 1=y_2^-≤ b_2-b_1≤ y_2^+=1, b_2-b_1 must be 1. So b_2=1 and b_1=0 must hold. Then by 1=y_3^-≤ b_3-b_2≤ y_3^+=1, b_3 equals 2. This contradicts the constraint of b_3≤ 1. So no solution exists.

In the second test case, we can let all b_i's be 0.

In the third test case, one possible solution is b_1=0, b_2=1/3, b_3=2/3, b_4=1.

inputFormat

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 66 666). Description of the test cases follows.

The first line of each test case contains a single integer n (3 ≤ n ≤ 100 000).

The i-th of the next n lines contains two integers x_i^-, x_i^+ (-10^8≤ x_i^-≤ x_i^+≤ 10^8) denoting the lower and upper bound of b_i.

The i-th of the next n-1 lines contains two integers y_{i+1}^-, y_{i+1}^+ (-10^8≤ y_{i+1}^-≤ y_{i+1}^+≤ 10^8) denoting the lower and upper bound of b_{i+1}-b_i.

The i-th of the next n-2 lines contains two integers z_{i+2}^-, z_{i+2}^+ (-10^8≤ z_{i+2}^-≤ z_{i+2}^+≤ 10^8) denoting the lower and upper bound of (b_{i+2}-b_{i+1}) - (b_{i+1}-b_i).

It is guaranteed that the sum of n over all test cases does not exceed 200 000.

It is guaranteed that relaxing every constraint by 10^{-6} (i.e., decrease x_i^-, y_i^-, z_i^- by 10^{-6} and increase x_i^+, y_i^+, z_i^+ by 10^{-6}) will not change the answer.

outputFormat

Output

For each test case, output YES if a sequence b_1,…, b_n satisfying the constraints exists and NO otherwise. The sequence b_1,…, b_n is not required.

Example

Input

4 3 0 1 0 1 0 1 1 1 1 1 -100 100 3 -967 541 -500 834 -724 669 -858 978 -964 962 -645 705 4 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 4 0 0 33 34 65 66 100 100 0 100 0 100 0 100 0 0 0 0

Output

NO YES YES NO

Note

In the first test case, all b_i's are in [0,1]. Because of the constraints 1=y_2^-≤ b_2-b_1≤ y_2^+=1, b_2-b_1 must be 1. So b_2=1 and b_1=0 must hold. Then by 1=y_3^-≤ b_3-b_2≤ y_3^+=1, b_3 equals 2. This contradicts the constraint of b_3≤ 1. So no solution exists.

In the second test case, we can let all b_i's be 0.

In the third test case, one possible solution is b_1=0, b_2=1/3, b_3=2/3, b_4=1.

样例

4
3
0 1
0 1
0 1
1 1
1 1
-100 100
3
-967 541
-500 834
-724 669
-858 978
-964 962
-645 705
4
0 0
0 1
0 1
1 1
0 1
0 1
0 1
0 0
0 0
4
0 0
33 34
65 66
100 100
0 100
0 100
0 100
0 0
0 0

NO
YES
YES
NO

</p>