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

Dựa trên ý tưởng của búp bê Nga Matrioska, công ty bánh Trung Thu có sản xuất những hộp bánh đặc biệt như sau: Trong một hộp bánh có thể chứa những hộp bánh nhỏ hơn, hộp bánh nhỏ nhất sẽ chứa bánh trung thu. Giả sử bánh trung thu là hộp bánh cấp \(0\) (bánh trung thu), hộp bánh cấp \(i\) (\(i \geq 1\)) sẽ chứa \(a_i\) hộp bánh cấp \(i-1\). Thấy ý tưởng rất độc đáo nên Bờm cũng đa mua một hộp bánh cấp \(N\) về để mở tiệc trung thu cho các bạn nhỏ.

Bờm muốn biết số lần mở hộp ít nhất để lấy được \(X\) chiếc bánh trung thu. Vì Bờm vẫn chưa biết có bao nhiêu bạn nhỏ tham gia tiệc trung thu nên để không tốn thời gian tính toán, Bờm sẽ chuẩn bị trước nhiều phương án.

Yêu cầu: Cho \(M\) phương án, với phương án thứ \(j\) (\(1 \le j \le M\)) cần \(X_j\) bánh trung thu, bạn hãy giúp Bờm tính xem cần ít nhất bao nhiêu lần mở hộp?

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \le N,M \le 3 \times 10^5\)) là cấp của hộp bánh của Bờm và số phương án cần tính toán.
• Dòng thứ hai chứa \(N\) số nguyên \(a_i\) (\(1 \le a_i \le 10^9, 1 \le i \le N\)) mô tả hộp bánh cấp \(i\) sẽ chứa \(a_i\) hộp bánh cấp \(i-1\).
• Dòng thứ ba chứa \(M\) số nguyên \(X_j\) (\(1 \le X_j \le 10^{12}, 1 \le j \le M\)) tương ứng với số bánh trung thu cần lấy ra trong mỗi phương án.

Output

• Gồm $M dòng, dòng thứ \(j\) in ra số lần mở hộp ít nhất để lấy được \(X_j\) bánh trung thu.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N,M \le 1000\).
• Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3 3
3 3 3
2 8 13

3
5
8

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