Mike được cho một mảng gồm n phần tử nguyên dương và anh ta được sử dụng một số (hoặc không cần sử dụng ) thao tác cắt mảng.
Để thực hiện thao tác, ta gọi phần tử lớn nhất và nhỏ nhất của mảng là Max và Min.
Đặt Mid = [ ( Max + Min ) / 2 ], ta sẽ chia mảng thành 2 mảng con. Với mảng thứ nhất gồm các số trong mảng trước đó không lớn hơn Mid, ngược lại mảng thứ hai gồm các số lớn hơn Mid. Khi có được mảng con thì Mike chỉ được phép giữ 1 mảng và bỏ đi vinh viễn mảng còn lại. Mảng được giữ xem như là mảng hiện tại đang xét và có thể thực hiện thao tác cắt nếu muốn.
Với q truy vấn gồm các số x[i], hãy kiểm tra xem với 1 mảng ban đầu đã có cùng với thao tác cắt , thì Mike có thể tạo 1 mảng nào có tổng các phần tử bằng x[i] được hay không ?
Đầu vào:
- Dòng đầu tiên là 2 số nguyên dương n,q (n,q <= 2*105).
- Dòng tiếp theo là n số nguyên dương a[i] (0 <= a[i] <= 106).
- q dòng tiếp theo là số nguyên dương x[i] (0 <= x[i] <= 1012).
Đầu ra:
- In ra q dòng , với dòng thứ i, Mike có thể tạo được 1 mảng có tổng bằng x[i] thì in ra "Yes" , ngược lại in ra "No".
Input: 5 3 3 1 5 4 2 12 9 3 Output: No Yes Yes Giải thích : - Mike không thể tạo mảng có tổng các phần tử bằng 12. - Sau thao tác cắt thứ nhất Mike có 2 mảng [3,1,2] và [5,4]. Mike giữ lại mảng thứ hai sẽ có tổng là 9. - Sau thao tác cắt thứ nhất Mike chọn mảng [3,1,2] và ở thao tác cắt thứ 2 sẽ có hai mảng là [3] và [1,2], Mike có thể chọn 1 trong 2 mảng để có tổng là 3.