Thể thao ngoài trời

Sau buổi giao lưu giữa các đoàn, Ban tổ chức nhận thấy các thí sinh rất hào hứng với các trò chơi tập thể. Đây là một tín hiệu tốt trong bối cảnh điện thoại thông minh hay mạng xã hội đang ngày càng ảnh hưởng và làm thay đổi đến giới trẻ. Vì vậy, Ban tổ chức quyết định tổ chức một môn thể thao ngoài trời như sau:

Trên một mặt sân phẳng rộng, vẽ một lưới ô vuông kích thước $n\times n$. Các hàng của lưới đánh số từ $1$ đến $n$ từ trên xuống, các cột của lưới được đánh số từ $1$ đến $n$ từ trái sang. Ô nằm giao giữa hàng $i$ và cột $j$ được gọi là ô $(i,j)$.

Chọn một nhóm gồm $n$ thí sinh, xếp các thí sinh đứng vào các ô trên lưới sao cho mỗi hàng có đúng một thí sinh. Sau đó, mỗi thí sinh được phát một chiếc hộp có khối lượng là $m$ kg. Nhiệm vụ của nhóm tham gia như sau: mỗi thí sinh có thể di chuyển chiếc hộp của mình sang các ô cùng hàng để sau khoảng thời gian $5$ phút, khi quan sát lưới theo cột, mỗi cột chỉ có đúng một hộp.

Đây là một môn thể thao đòi hỏi thể lực cũng như sự tính toán hợp lí của nhóm. Nếu thể lực của thí sinh ở hàng $i$ là $s_i$ thì trong vòng $5$ phút, thí sinh đó có thể di chuyển chiếc hộp sang một ô khác cùng hàng cách ô cũ không quá $\lfloor \frac{s_i}{m}\rfloor$ (hoặc giữ nguyên hộp ở ô cũ); khoảng cách giữa hai ô $(i,j_1)$ và $(i,j_2)$ được tính bằng $|j_1-j_2|$. Nói cách khác, hộp ở hàng $i$ (ban đầu ở cột $v_i$) có thể kết thúc ở bất kỳ cột $j$ nào thỏa mãn $1\le j\le n$ và $|j-v_i|\le \lfloor \frac{s_i}{m}\rfloor$, kể cả khi khoảng cách đúng bằng $\lfloor \frac{s_i}{m}\rfloor$.

Yêu cầu: Cho biết vị trí đứng trên lưới và thể lực của từng thí sinh, với chiếc hộp có khối lượng $m$, hãy giúp Ban tổ chức trả lời câu hỏi có hay không tồn tại cách di chuyển các hộp để nhóm có thể di chuyển các chiếc hộp thỏa mãn yêu cầu.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$.
• Dòng thứ hai gồm $n$ số nguyên $v_1,v_2,\dots ,v_n$ ($1\le v_i\le n$), $v_i$ là vị trí cột mà thí sinh ở hàng $i$ đứng.
• Dòng thứ ba gồm $n$ số nguyên dương $s_1,s_2,\dots ,s_n$ ($s_i\le {10}^9$), $s_i$ là thể lực của thí sinh đứng ở hàng $i$.
• Dòng thứ tư là một số nguyên dương $Q$.
• Dòng cuối cùng gồm $Q$ số nguyên dương $m_1,m_2,\dots ,m_Q$ ($m_k\le {10}^9$) tương ứng $Q$ câu hỏi mà Ban tổ chức muốn biết có tồn tại hay không phương án di chuyển hộp thỏa mãn yêu cầu (câu hỏi thứ $k$ ứng với hộp có khối lượng $m_k$).

Dữ liệu ra

In ra $Q$ số nguyên trên một dòng, cách nhau bởi dấu cách; số thứ $k$ là câu trả lời cho câu hỏi $m_k$: in $1$ nếu tồn tại phương án và $0$ nếu không tồn tại.

Ràng buộc

• $1\le n\le {10}^5$, $1\le Q\le {10}^5$.
• $1\le v_i\le n$.
• $1\le s_i\le {10}^9$.
• $1\le m_k\le {10}^9$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $Q=1$, $n\le 10$.
• Subtask 2 ($20\%$ số điểm): $Q\le 10$, $n\le 10$.
• Subtask 3 ($10\%$ số điểm): $Q\le 10$, $n\le 20$.
• Subtask 4 ($20\%$ số điểm): $Q\le 10$, $n\le 200$.
• Subtask 5 ($10\%$ số điểm): $Q\le 10$, $n\le 2000$.
• Subtask 6 ($20\%$ số điểm): $Q,n\le {10}^5$.

Ví dụ