Bối cảnh
Các dự án thú vị đã kết thúc, hội trường chào đón buổi tiệc trà nghỉ giữa giờ. Mọi người trò chuyện về những khó khăn trong nghiên cứu khoa học và việc gửi bài báo: Tiểu T than thở rằng mỗi lần gửi bài xong đều phải rút lại để nộp lại, liên tục chỉnh sửa bài báo; trong khi đó, Tiểu S, với tư cách là người xét duyệt, cho biết mình luôn kiểm soát nghiêm ngặt khi xét duyệt, cố gắng loại bỏ các bản thảo trong tay nhiều nhất có thể.
Dựa trên cuộc trao đổi này, Tiểu T và Tiểu S nảy ra ý tưởng: Nếu gặp phải một người xét duyệt cực kỳ khắt khe, con đường xuất bản bài báo sẽ diễn ra như thế nào? Vì vậy, họ đã đề xuất một mô hình trò chơi. Trong mô hình này, hai bên lần lượt đóng vai tác giả và người xét duyệt, tham gia vào một trò chơi xoay quanh một hàng đợi xét duyệt dài. Trong hàng đợi có lẫn rất nhiều bản thảo của người khác, trong đó chỉ có một bài báo là do tác giả gửi. Tác giả hy vọng bài báo của mình sẽ được luân chuyển và mài giũa trong hàng đợi để nâng cao giá trị học thuật khi xuất bản; trong khi người xét duyệt sẽ kiểm tra nghiêm ngặt, tìm cơ hội để loại bỏ trực tiếp bài báo này, khiến tác giả không thu được gì.
Hàng đợi xét duyệt bao gồm $n$ bài báo, trong đó bài báo thứ $m$ là bài báo do tác giả gửi. Ban đầu, giá trị học thuật của bài báo này là 1.
Trò chơi bắt đầu bởi tác giả, sau đó hai bên luân phiên thực hiện. Trong mỗi lượt, người chơi thực hiện hành động phải thực hiện tuần tự các thao tác sau:
- Lấy ra $k$ bài báo từ đầu hàng đợi xét duyệt. Nếu số lượng bài báo còn lại trong hàng đợi ít hơn $k$, lấy ra tất cả số bài báo còn lại.
- Trong số các bài báo vừa lấy ra, chọn 0 hoặc 1 bài báo để xuất bản hoặc từ chối vĩnh viễn, tức là loại bỏ hoàn toàn bài báo đó khỏi hàng đợi.
- Chèn tất cả các bài báo chưa bị loại bỏ vào cuối hàng đợi xét duyệt theo thứ tự tùy ý. Vì hàng đợi xét duyệt là công khai, cả hai bên đều biết chính xác vị trí mới của mỗi bài báo sau khi chèn lại.
Điểm số cuối cùng của tác giả được quyết định bởi kết quả của bài báo mà họ đã gửi:
- Trong mỗi lượt, nếu bài báo đó không bị loại bỏ và được chèn lại vào cuối hàng đợi, giá trị học thuật của nó sẽ tăng thêm 1.
- Nếu tác giả chủ động loại bỏ bài báo đó trong một lượt thao tác, bài báo đó được xuất bản thành công, trò chơi kết thúc ngay lập tức và tác giả nhận được giá trị học thuật tại thời điểm đó.
- Nếu người xét duyệt loại bỏ bài báo đó trong một lượt thao tác, bài báo đó bị từ chối vĩnh viễn, trò chơi kết thúc ngay lập tức và tác giả nhận được 0 điểm.
Mục tiêu của tác giả là tối đa hóa điểm số, trong khi mục tiêu của người xét duyệt là tối thiểu hóa điểm số của tác giả.
Dữ liệu vào
Mỗi tệp kiểm thử chứa nhiều bộ dữ liệu. Dòng đầu tiên của đầu vào chứa một số nguyên dương $T$ ($1 \le T \le 50$), biểu thị số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu:
- Dòng đầu tiên chứa ba số nguyên dương $n, k, m$ ($1 \le n, k \le 10^9, 1 \le m \le n$), lần lượt biểu thị độ dài của hàng đợi xét duyệt, số lượng bài báo được lấy ra mỗi lần, và vị trí ban đầu của bài báo do tác giả gửi.
Dữ liệu ra
Đối với mỗi bộ dữ liệu, in ra một số nguyên trên một dòng, biểu thị điểm số cuối cùng của tác giả. Đặc biệt, nếu trò chơi không bao giờ kết thúc, hãy in ra $-1$.
Ví dụ
Dữ liệu vào 1
6 3 2 1 5 3 4 10 3 1 7 3 7 817247666 7237 327476688 610723117 332458760 292738094
Dữ liệu ra 1
2 0 2 4 3470 278264358