Tin học trẻ C - Vòng Khu vực miền Nam 2020

Trên quảng trường trung tâm thành phố, người ta đặt một bảng quảng cáo điện tử hình vuông kích thước \(10^9 \times 10^9\) được chia làm lưới ô vuông đơn vị. Các hàng của bảng đánh số từ \(1\) tới \(10^9\) từ trên xuống dưới và các cột của bảng đánh số từ \(1\) tới \(10^9\) từ trái qua phải. Ô nằm trên giao của hàng \(i\) và cột \(j\) gọi là ô (\(i,j\)).

Có \(n\) hãng đăng kí quảng cáo đánh số từ \(1\) tới \(n\), hãng thứ \(i\) đăng kí quảng cáo trong một cửa sổ hình chữ nhật có cạnh song song với cạnh bảng, hình chữ nhật này có ô ở góc trên bên trái là ô \((a_i,b_i)\) và ô ở góc dưới bên phải là ô \((c_i,d_i)\). Trên cửa sổ, hãng có thể chiếu lên bảng những đoạn video giới thiệu sản phẩm của mình.

Khi hiện lên bảng, cửa sổ quảng cáo của một số hãng có thể giao nhau làm ảnh hưởng tới sự chú ý của người xem, người ta muốn thống kê số cặp (\(i,j\)) với \(1 \le i < j \le n\) mà cửa sổ quảng cáo của hai hãng \(i\) và \(j\) có chung ít nhất một ô, để từ đó thông báo cho các hãng có kế hoạch thay đổi vị trí và kích thước cửa sổ của mình cho phù hợp.

Yêu cầu: Hãy xác định số lượng những cặp (\(i,j\)) với \(1 \le i < j \le n\) mà cửa sổ quảng cáo của hai hãng \(i\) và \(j\) có chung ít nhất một ô.

Input

• Dòng đầu chứa số nguyên dương \(T \le 1000\) là số bộ dữ liệu.
• \(T\) nhóm dòng tiếp theo, mỗi nhóm dòng miêu tả một test:
  • Dòng đầu của nhóm chứa số nguyên dương \(n \le 2 \times 10^5\).
  • \(n\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên dương \(a_i,b_i,c_i,d_i\) cách nhau bởi dấu cách (\(1 \le a_i \le c_i \le 10^9, 1 \le b_i \le d_i \le 10^9\)).
• Tổng các giá trị \(n\) trong tất cả các test không vượt quá \(2 \times 10^5\).

Output

• Gồm \(T\) dòng, ứng với mỗi bộ dữ liệu, đưa ra một số nguyên duy nhất trên một dòng là số lượng những cặp (\(i,j\)) với \(1 \le i < j \le n\) mà cửa sổ quảng cáo của hai hãng \(i\) và \(j\) có chung ít nhất một ô.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n = 2\).
• Subtask \(2\) (\(15\%\) số điểm): \(n \le 10^3, T \le 50\).
• Subtask \(3\) (\(30\%\) số điểm): \(1 \le a_i \le c_i \le 100, 1 \le b_i \le d_i \le 100\).
• Subtask \(4\) (\(35\%\) số điểm): không có ràng buộc gì thêm.

Example

2
2
1 1 2 2
2 2 3 3
5
1 3 2 5
2 2 6 3
2 6 7 9
3 5 6 10
6 3 7 7

1
5

Một cửa hàng đồ chơi mới nhập về \(n\) chiếc ô tô và \(n\) bộ xếp hình mới, \(n\) chiếc ô tô được trưng bày thành một hàng ngang và được đánh số từ \(1\) tới \(n\) từ trái qua phải, tương tự, \(n\) bộ xếp hình cũng được trưng bày thành một hàng ngang và được đánh số từ \(1\) tới \(n\) từ trái qua phải. Giá của chiếc ô tô thứ \(i\) (\(1 \le i \le n\)) là \(a_i\) đồng, giá của bộ xếp hình thứ \(j\) (\(1 \le j \le n\)) là \(b_j\) đồng.

Trường mẫu giáo XYZ quyết định mua ô tô và bộ xếp hình từ cửa hàng đồ chơi để làm phong phú thêm kho đồ chơi của nhà trường. Sau khi thực hiện khảo sát đối với \(m\) trẻ trong trường, nhà trường biết rằng trẻ thứ \(k\) (\(1 \le k \le m\)) rất thích chiếc ô tô \(x_k\) (\(1 \le x_k \le n\)) hoặc bộ xếp hình \(y_k\) (\(1 \le y_k \le n\)). Tuy nhiên, cửa hàng đồ chơi chỉ đồng ý bán cho nhà trường những chiếc ô tô nằm liên tiếp trong hàng và những bộ xếp hình nằm liên tiếp trong hàng.

Yêu cầu: Hãy xác định số tiền ít nhất để mua đồ chơi mà trẻ nào cũng có món đồ chơi mình thích.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) là số lượng ô tô và số lượng bộ xếp hình.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) (\(a_i \le 10^9\)) là giá của \(n\) chiếc ô tô.
• Dòng thứ ba chứa \(n\) số nguyên dương \(b_1,b_2,...,b_n\) (\(b_i \le 10^9\)) là giá của \(n\) bộ xếp hình.
• Dòng thứ tư chứa số nguyên dương \(m\) là số lượng trẻ của trường mẫu giáo.
• Tiếp theo là \(m\) dòng, dòng thứ \(k\) (\(1 \le k \le m\)) chứa hai số nguyên dương \(x_k\) và \(y_k\) (\(1 \le x_k,y_k \le n\)).

Output

• Một số là số tiền ít nhất để mua đồ chơi thỏa mãn yêu cầu.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \le 10, m \le 10\).
• Subtask \(2\) (\(10\%\) số điểm): \(n \le 100, m \le 2 \times 10^5\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 500, m \le 2 \times 10^5\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 2000, m \le 2 \times 10^5\).
• Subtask \(5\) (\(40\%\) số điểm): \(n \le 2 \times 10^5, m \le 2 \times 10^5\).

Example

4
9 1 1 9
9 9 9 1
3
2 1
3 1
4 4

3

4
1 1 1 1
6 7 8 9
3
1 2
2 2
3 2

3