#1009. MEDIAN - Số trung vị

Số trung vị cua một dãy số là một số tách giữa nửa lớn hơn và nửa bé hơn của một dãy số. Nó là giá trị giữa trong một dãy số, mà số các số nằm trên hay dưới con số đó là bằng nhau.

Để tìm số trung vị của một danh sách hữu hạn các số, ta xếp tăng dần tất cả các số trong dãy, rồi lấy giá trị nằm giữa danh sách nếu số phần tử là số lẻ. Nếu số phần tử là số chẵn, người ta thường lấy trung bình của hai giá trị nằm giữa.

Thành phố T lúc nãy đã phát triển hơn. Thành phố lúc này có dãy số. Dãy phố thứ có tòa nhà. Tòa thứ trong dãy nhà thứ lúc này có người sinh sống.

Người xưa có câu “Lao động là vinh quang”. Để thực hiện câu nói này, ngài thị trưởng đã lập lên một kế hoạch cho mọi người nhằm đưa thành phố phát triển lên một tầm cao mới. Kế hoạch diễn ra trong tuần, mỗi tuần ngài sẽ chọn hai dãy nhà bất kì để giao nhiệm vụ cho mọi người trong hai dãy nhà đó thực hiện. Nhưng vì mỗi dãy nhà sẽ có số lượng người dân khác nhau nên không thể giao cùng số lượng nhiệm vụ được. Thay vào đó để công bằng hơn ngài quyết định số lượng nhiệm vụ sẽ là lần số trung vị của dãy số được kết hợp từ hai dãy nhà được chọn.

Bạn được ngài thị trưởng tin tưởng giao cho danh sách tuần đó. Bạn hãy tìm số lượng nhiệm vụ cần thiết phải giao từng tuần.

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên dương và lần lượt là số lượng dãy nhà hiện đang có trong thành phố và danh sách số tuần của kế hoạch.
• dòng tiếp theo mỗi dòng gồm một số và số tự nhiên đã được sắp xếp, số thứ đại diện cho số lượng người dân đang ở trong tòa nhà thứ
• dòng tiếp theo mỗi dòng gồm hai số tự nhiên và là dãy nhà thứ và .

Dữ liệu ra:

• Gồm dòng, mỗi dòng là số lượng nhiệm vụ cần giao trong tuần đó.

Ví dụ:

Dữ liệu vào:

5 3
2 1 3 
1 2
2 1 2
2 3 4
6 1 1 1 1 3 5
1 2
3 4
1 5

Dữ liệu ra:

4
5
2

Giới hạn:

• số test có
• số test khác có