Centre for Gifted Education - Hanoi university of Technology

Các thuật toán tìm kiếm đều dựa vào việc so sánh giá trị khoá (Key) của phần tử cần tìm với các giá trị khoá trong tập các phần tử, thao tác này

Phụ thuộc kích thước của tập các phần tử

Thời gian tìm kiếm không nhanh do phải thực hiện nhiều phép so sánh có thể không cần thiết ( O(n), O(logn), …)

Liệu có phương pháp lưu trữ nào cho phép thực hiện tìm kiếm với hiệu suất cao hơn không ( < O(log N) ). Câu trả lời là có.

Ta xét bảng băm với các thao tác:

• Khởi tạo (Initialize)

• Kiểm tra rỗng (Empty)

• Lấy kích thước của bảng băm (Size)

• Tìm kiếm (Search)

• Thêm mới phần tử (Insert)

• Loại bỏ (Remove)

• Sao chép (Copy)

• Duyệt (Traverse)

Dùng bảng băm giải bài toán đã xét ở phần tìm kiếm nhị phân:

Cho 1 dãy gồm n phần tử: A₁, A₂, ... A_n-1, A_n. Kiểm tra xem 1 khoá x=key cho trước có tồn tại trong dãy A hay không.

Input

Dòng 1: ghi 2 số nguyên n, m,.

n dòng tiếp theo: Mỗi dòng ghi 1 số nguyên A_i.

m dòng tiếp theo: Mỗi dòng ghi 1 khoá key

Output

Gồm m dòng: ứng với mỗi dòng ghi 1/0 tương ứng với khoá key có/không có trong dãy A.

Example

Input:
7 3
5
3
1
7
9
100
10
9
1000
6

Output:
1
0
0

Giới hạn:
1 <= n <= 106
1 <= m <= 106
|Ai| < 231