Farmer John đã chậm trễ trong việc sắp xếp hộp thư đến. Màn hình của ông được bố trí với một danh sách thư mục dọc ở bên trái và một danh sách email dọc ở bên phải. Có tổng cộng \(M\) thư mục, được đánh số \(1\ldots M\) (\(1\le M\le 10^4\)). Hộp thư đến hiện có \(N\) email được đánh số \(1\ldots N\) (\(1\le N\le 10^5\)); email thứ \(i\) cần được lưu vào thư mục \(f_i\) (\(1\le f_i\le M\)).

Màn hình của FJ khá nhỏ nên ông chỉ có thể xem đồng thời \(K\) (\(1\le K\le\min(N,M)\)) thư mục và \(K\) email. Ban đầu, màn hình hiển thị các thư mục \(1\ldots K\) ở bên trái và các email \(1\ldots K\) ở bên phải. Để truy cập những thư mục và email khác, ông phải cuộn qua từng danh sách tương ứng. Ví dụ, nếu cuộn xuống một vị trí trong danh sách thư mục, màn hình sẽ hiển thị các thư mục \(2\ldots K+1\); cuộn tiếp xuống một vị trí sẽ hiển thị các thư mục \(3\ldots K+2\). Khi FJ kéo một email vào một thư mục, email đó biến mất khỏi danh sách và những email đứng sau nó dịch lên một vị trí. Ví dụ, nếu các email \(1,2,3,4,5\) đang được hiển thị và FJ kéo email \(3\) vào đúng thư mục, danh sách email sẽ hiển thị \(1,2,4,5,6\). FJ chỉ có thể kéo một email vào đúng thư mục mà nó cần được lưu.

Đáng tiếc, con lăn chuột của FJ bị hỏng nên ông chỉ có thể cuộn xuống, không thể cuộn lên. Cách duy nhất để ông có thể phần nào cuộn lên là khi đang xem nhóm \(K\) email cuối cùng trong danh sách email và lưu một email trong số đó. Khi ấy, danh sách lại hiển thị \(K\) email cuối cùng chưa được lưu, về thực chất làm email trên cùng dịch lên một vị trí. Nếu còn ít hơn \(K\) email thì tất cả chúng đều được hiển thị.

Hãy giúp FJ xác định liệu ông có thể lưu tất cả email hay không.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 10\)), số trường hợp con trong tệp vào; tất cả đều phải được giải đúng để giải được tệp test này. Sau đó là \(T\) trường hợp con. Với mỗi trường hợp con, dòng đầu chứa \(M\), \(N\) và \(K\). Dòng tiếp theo chứa \(f_1\ldots f_N\).

Bảo đảm tổng \(M\) trên tất cả các trường hợp con không vượt quá \(10^4\), và tổng \(N\) trên tất cả các trường hợp con không vượt quá \(10^5\).

Dữ liệu ra

In \(T\) dòng, mỗi dòng chứa YES hoặc NO, cho biết FJ có thể lưu thành công tất cả email trong mỗi trường hợp con trong số \(T\) trường hợp hay không.

Phân nhóm

• Trong các tệp test 2–10, tổng \(M\) trên tất cả các trường hợp con không vượt quá \(10^3\).
• Trong các tệp test 11–12, không có ràng buộc bổ sung.

Ví dụ

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

YES
YES
NO
YES
YES
NO

Nguồn

USACO 2022 February Contest, Silver — Email Filing: https://usaco.org/index.php?page=viewproblem2&cpid=1208

Tác giả: Brian Dean.