G. MEDSUM - Tổng trung vị

Cho dãy số không giảm , mỗi dãy gồm số nguyên (dãy số được gọi là không giảm nếu mỗi phần tử đứng sau là lớn hơn hoặc bằng phần tử đứng trước). Xét hai dãy và , ta gọi dãy gộp (ký hiệu là ) của hai dãy là dãy gồm tất cả phần tử của hai dãy được sắp xếp theo thứ tự không giảm và phần tử đứng ở vị trí thứ trong dãy gộp được gọi là phần tử trung vị của nó.

Ví dụ: Xét hai dãy số . Khi đó dãy gộp từ hai dãy đã cho là có phần tử trung vị là .

Yêu cầu: Tính tổng của tất cả các phần tử trung vị của tất cả các dãy gộp với .

Dữ liệu vào:

• Dòng đầu tiên chứa hai số và ;
• Dòng thứ trong số dòng tiếp theo chứa số nguyên là các phần tử của dãy thứ trong số dãy đã cho. Giả thiết là các phần tử của các dãy số là các số nguyên có trị tuyệt đối không vượt quá . Hai số liên tiếp trên cùng một dòng trong file dữ liệu được ghi cách nhau bởi ít nhất một dấu cách.

Dữ liệu ra:

• Ghi ra một số là (là phần dư trong phép chia cho ), trong đó là tổng của tất cả các phần tử trung vị của tất cả các dãy gộp với .

Giới hạn:

• số test ứng với số điểm thoả mãn: .
• số test còn lại không có ràng buộc gì thêm.

Ví dụ:

Dữ liệu vào:

3 6
1 2 3 4 5 6
3 4 5 6 7 8
0 0 1 1 2 2

Dữ liệu ra:

8