题目描述

对有序数组进行二分查找，是一种性能卓越的算法。

现在给定一个升序数组 $a$，对于每个查询值 $key$，请判断该值是否在数组中出现。

• 如果存在，则输出 1
• 如果不存在，则输出 0

输入格式

第一行包含一个整数 $N$，表示数组长度。

第二行包含 $N$ 个整数 $a_1,a_2,\dots,a_N$（$N \le 300000$），保证数组为升序。

第三行包含一个整数 $T$，表示查询次数。

第四行包含 $T$ 个整数，表示每个查询的 $key$ 值（$T \le 300000$）。

输出格式

输出一行，共 $T$ 个整数：

• 若存在，输出 1
• 否则输出 0

结果之间用空格分隔。

输入输出样例

输入

3
-2 -2 1
3
-2 -2 -1

输出

1 1 0

数据范围

• $1 \le N, T \le 300000$
• 数组元素和查询值均在 int 范围内