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 × 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~, khoảng cách giữa hai ô ~(i,j_1)~ và ô ~(i,j_2)~ được tính bằng ~|j_1 − j_2|~.

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ố ~v_1, v_2, … , v_n~ là vị trí cột mà thí sinh ở hàng ~i~ đứng;
• Dòng thứ ba gồm ~n~ số ~s_1, s_2, … , s_n~ 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, … , m_Q~ 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.

Dữ liệu ra

• Gồm ~Q~ số nguyên trên một dòng, số thứ ~k~ là câu trả lời cho câu hỏi ~m_k~ trong file dữ liệu vào, ghi số ~1~ nếu tồn tại và ~0~ nếu không tồn tại.

Sample Input

3
1 2 1
5 5 2
2
5
3

Sample Output

1 1

Giới hạn

• Có 20% số test ứng với 20% số điểm của bài có ~Q = 1; n ≤ 10~;
• Có 20% số test khác ứng với 20% số điểm của bài có ~Q ≤ 10; n ≤ 10~;
• Có 10% số test khác ứng với 10% số điểm của bài có ~Q ≤ 10; n ≤ 20~;
• Có 20% số test khác ứng với 20% số điểm của bài có ~Q ≤ 10; n ≤ 200~;
• Có 10% số test khác ứng với 10% số điểm của bài có ~Q ≤ 10; n ≤ 2000~;
• Có 20% số test còn lại ứng với 20% số điểm của bài có ~Q, n ≤ 10^5~.

Nguồn: Trại hè Phương Nam năm 2019.