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. 
#include <bits/stdc++.h>
 
template <typename T> void setmax(T& a, T b) { if (b > a) a = b; }
template <typename T> void setmin(T& a, T b) { if (b < a) a = b; }
 
template <typename T> struct range_val {
	T lo, hi;
	range_val() : lo(), hi( ){}
	range_val(T lo_, T hi_) : lo(lo_), hi(hi_) {}
 
	friend std::istream& operator >> (std::istream& i, range_val& v) { return i >> v.lo >> v.hi; }
	friend std::ostream& operator << (std::ostream& o, range_val v) { return o << v.lo << '-' << v.hi; }
 
	friend bool operator == (range_val a, range_val b) { return a.lo == b.lo && a.hi == b.hi; }
 
	explicit operator bool() const { return lo <= hi; }
 
	range_val operator + () const { return range_val(lo, hi); }
	range_val operator - () const { return range_val(-hi, -lo); }
	friend range_val operator + (range_val a, range_val b) { return range_val(a.lo + b.lo, a.hi + b.hi); }
	friend range_val operator - (range_val a, range_val b) { return a + (-b); }
 
	range_val& operator &= (const range_val& o) { setmax(lo, o.lo); setmin(hi, o.hi); return *this; }
	friend range_val operator & (range_val a, range_val b) { return range_val(max(a.lo, b.lo), min(a.hi, b.hi)); }
};
 
int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
 
	int T; cin >> T;
	while (T--) {
		int N; cin >> N;
		vector<range_val<int64_t>> X(N); for (auto& a : X) cin >> a;
		vector<range_val<int64_t>> Y(N-1); for (auto& a : Y) cin >> a;
		vector<range_val<int64_t>> Z(N-2); for (auto& a : Z) cin >> a;
		cout << ([&]() -> bool {
			for (int z = 0; true; z++) {
				if (z > 60) return false;
				auto old_X = X;
				auto old_Y = Y;
				auto old_Z = Z;
				for(int i = 0; i <= N-2; i++){
					Y[i] &= X[i+1] - X[i];		
					if(i >= 1) Y[i] &= Y[i-1] + Z[i-1];		
					X[i+1] &= X[i] + Y[i];
					if(i <= N-3) Z[i] &= Y[i+1] - Y[i];
				}
				for(int i = N-2; i >= 0; i--){
					Y[i] &= X[i+1] - X[i];		
					if(i <= N-3) Y[i] &= Y[i+1] - Z[i];		
					X[i] &= X[i+1] - Y[i];
					if(i >= 1) Z[i-1] &= Y[i] - Y[i-1];
				}
 
				if (X == old_X && Y == old_Y && Z == old_Z) break;
 
				for (auto& v : X) if (!v) return false;
				for (auto& v : Y) if (!v) return false;
				for (auto& v : Z) if (!v) return false;
			}
 
			return true;
		}() ? "YES" : "NO") << '\n';
	}
 
	return 0;
}