Đề bài

Đại dịch COVID-19 khiến thế giới bất ngờ theo nhiều cách. Gần như chỉ sau một đêm, mọi người trên khắp thế giới phải thích nghi với lối sống mới, chủ yếu được định hình bởi các biện pháp phòng ngừa do chính quyền địa phương ban hành nhằm ngăn chặn và kiểm soát sự lây lan của dịch bệnh.

Để chuẩn bị tốt hơn cho khả năng xa xôi rằng một đợt dịch nghiêm trọng hơn sẽ xảy ra trong tương lai, Viện Y tế Công cộng Quốc gia Croatia quyết định thành lập nhiều bộ phận nghiên cứu. Mục tiêu chính của các bộ phận này là xây dựng những quy trình hiệu quả giúp người dân nhanh chóng tuân thủ một biện pháp phòng ngừa mới.

Alenka làm việc tại một bộ phận như vậy. Cô đang nghiên cứu tình huống một nhóm người đứng trên một đường thẳng, chẳng hạn trước một bưu điện, rồi một quy định an toàn mới đột ngột có hiệu lực: khoảng cách giữa hai người bất kỳ phải ít nhất là \(D\).

Alenka đã xây dựng một ứng dụng cho phép người dùng nhập khoảng cách \(D\) và vị trí của \(N\) người dưới dạng các tọa độ trên một đường thẳng. Ứng dụng vẽ lại tình huống và tính thời gian nhỏ nhất tính bằng giây, ký hiệu là \(t_{opt}\), để cả nhóm đạt được một cách sắp xếp thỏa mãn quy định. Ứng dụng giả sử mọi người lập tức bắt đầu sắp xếp lại vị trí một cách tối ưu và tất cả đều di chuyển với cùng vận tốc không đổi là một đơn vị mỗi giây.

Alenka muốn bổ sung tính năng cho phép người dùng thêm \(M\) người vào nhóm bằng cách chạm lên đường thẳng để chỉ định vị trí của họ. Sau mỗi lần chạm, tức là sau mỗi người mới được thêm vào, ứng dụng phải tính lại \(t_{opt}\).

Hãy giúp Alenka cài đặt tính năng này.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(D\).

Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\), là vị trí của \(N\) người ban đầu. Nếu \(N=0\), dòng này rỗng.

Dòng thứ ba chứa \(M\) số nguyên \(b_1,b_2,\ldots,b_M\), là vị trí của \(M\) người được thêm vào.

Dữ liệu ra

In \(M\) số trên một dòng. Số thứ \(i\) là giá trị \(t_{opt}\) khi nhóm gồm \(N+i\) người tại các vị trí

Mỗi số phải được in ở dạng thập phân không có chữ số 0 thừa ở cuối. Ví dụ, hãy in 1.23 thay vì 1.2300, và in 123 thay vì 123. hoặc 123.0. Có thể chứng minh rằng mọi đáp án đều có biểu diễn thập phân hữu hạn.

Ràng buộc

Trong tất cả các subtask:

• \(1\le D\le 10^9\).
• \(1\le a_i\le 10^9\).
• \(1\le b_i\le 10^9\).

Phân nhóm

• Subtask 1 (10 điểm): \(0\le N\le 2\,000\), \(1\le M\le 10\).
• Subtask 2 (14 điểm): \(0\le N\le 200\,000\), \(1\le M\le 10\).
• Subtask 3 (35 điểm): \(N=0\), \(1\le M\le 200\,000\) và \(b_1\le b_2\le\cdots\le b_M\).
• Subtask 4 (41 điểm): \(N=0\), \(1\le M\le 200\,000\).

Ví dụ

2 1 2
1 3
2

1

0 5 3

1 2 3 4 5

0 1 2 3 4

3 3 3
3 3 3
3 3 3

4.5 6 7.5