Centre for Gifted Education - Hanoi university of Technology

Xét các bài toán tìm kiếm, nếu như dùng phương pháp tìm kiếm tuần tự thì sẽ rất mất nhiều thời gian. Ta tiếp cận với 1 phương pháp mới đó là tìm kiếm nhị phân (Tiếng anh: Binary search)

Xét bài toán:

Cho 1 dãy gồm n phần tử: A₁, A₂, ... A_n-1, A_n. Các phần tử được sắp xếp theo thứ tự tăng dần. Cần kiểm tra xem 1 khoá x=key cho trước có tồn tại trong dãy 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
1
3
5
7
9
10
100
9
1000
6

Output:
1
0
0

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