Dây đèn

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

24-25 HSG9 HANOI

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Để trang trí Tết, Nam treo một dây đèn gồm $N$ bóng đèn, được đánh số từ $1$ đến $N$ , từ trái sang phải. Mỗi bóng đèn khi bật sẽ có hai màu vàng hoặc đỏ. Dây đèn được nhúng một mã lệnh cho phép nhận một số tự nhiên $X$ . Khi đó, màu của bóng đèn thứ $X$ và các bóng đèn cách bóng đèn thứ $X$ không quá $K$ bóng đèn sẽ đều đổi từ vàng thành đỏ hoặc ngược lại.

Ban đầu các bóng đèn đều có màu vàng. Để dây đèn trông đẹp mắt, Nam đã lập trình để điều khiển màu của các bóng đèn. Chương trình của Nam có $M$ dòng lệnh, mỗi dòng lệnh tương ứng với một lần gọi mã lệnh của dây đèn. Vì số lượng bóng đèn quá lớn, sau khi lập trình xong, Nam muốn kiểm tra ngẫu nhiên màu một số bóng đèn xem có đúng như ý tưởng ban đầu không.

Cho các số tự nhiên $X$ là tham số của $M$ dòng lệnh trong chương trình của Nam. Hãy lập trình để trả lời $Q$ câu hỏi tương ứng với các lần kiểm tra của Nam. Biết rằng mỗi câu hỏi chứa một số nguyên dương $P$ để xác định xem bóng đèn thứ $P$ trong dây đèn có màu vàng hay đỏ.

Dữ liệu vào

Dòng đầu tiên gồm bốn số nguyên dương lần lượt là $N$ , $M$ , $Q$ , $K$ ( $1 \leq N \leq 10^{9}$ ; $1 \leq M \leq 10^{5}$ ; $1 \leq Q \leq 10^{5}$ ; $0 \leq K \leq N$ ).
Dòng thứ hai gồm $M$ số nguyên dương $X_{i}$ mô tả tham số của lệnh thứ $i$ ( $1 \leq X_{i} \leq N$ ).
Dòng thứ ba gồm $Q$ số nguyên dương $P_{i}$ mô tả câu hỏi thứ $i$ ( $1 \leq P_{i} \leq N$ ).

Dữ liệu ra

Gồm $Q$ dòng, dòng thứ $i$ là câu trả lời cho câu hỏi thứ $i$ . Nếu bóng đèn tại vị trí $P_{i}$ đang có màu vàng thì ghi ra ký tự V, ngược lại ghi ra ký tự D.

Ràng buộc

$1 \leq N \leq 10^{9}$
$1 \leq M \leq 10^{5}$
$1 \leq Q \leq 10^{5}$
$0 \leq K \leq N$
60% số test: $N, M, Q \leq 10^{3}$
20% số test: $N, M \leq 10^{5}$
20% số test: không có ràng buộc gì thêm.

Ví dụ

Input	Output	Giải thích
7 2 4 1 3 5 2 7 4 5	D V V D	Sau lần gọi mã lệnh thứ nhất ( $X = 3$ ), các bóng trong dây đèn có màu là: $V, D, D, D, V, V, V$ . Sau lần gọi mã lệnh thứ hai ( $X = 5$ ), các bóng đèn có màu là: $V, D, D, V, D, D, V$ .

Bình luận

Không có bình luận tại thời điểm này.