2023 年 “图森未来杯” 全国高校程序设计网络邀请赛

F. 龟速飞行棋

单点时限: 1.0 sec

内存限制: 256 MB

Cuber QQ 喜欢和 Quber CC 玩飞行棋,但是他总是没 Quber CC 跑得快。所以他打算发明一种新的飞行棋,称为”龟速飞行棋”。

这种新型的飞行棋在一个长条形棋盘上进行。棋盘上有 $n$ 个格子排成一列。游戏开始时一枚棋子放置在最左边的格子上,接下来两名玩家将轮流移动这枚棋子。格子共有三类,根据棋子当前所在的格子类型,玩家接下来可以把棋子往右移动一格(类型 1),或者往右移动两格(类型 2),或者既能往右移一格也能往右移两格(类型 3),最后不能移动棋子的玩家失败。

Cuber QQ 精心设计了棋盘上每个格子的类型,但是仍然总是输给 Quber CC。Cuber QQ 觉得问题在于现在的棋盘还是太长了。他想把棋盘裁掉一部分,只留下前 $k$ 个格子。他想问问你,如果只保留前 $k$ 个格子,先手一方将必胜还是必败。Cuber QQ 可能会给你多个询问。

输入格式

第一行包含一个整数 $n$($1\le n\le 2\times 10^5$),表示棋盘上的格子数量。

第二行包含 $n$ 个整数 $t_1,t_2,\cdots,t_n$,$t_i$($1\le t_i\le 3$)表示第 $i$ 个格子的类型。

第三行包含一个整数 $T$($1\le T\le n$),表示询问个数。

接下来的 $T$ 行,每行包含一个整数 $k$($1\le k\le n$),表示询问如果只保留前 $k$ 个格子,先手一方将必胜还是必败。

输出格式

输出共 $T$ 行,每行包含一个整数 0 或 1 表示一次询问的答案。0 表示先手必败,1 表示先手必胜。

样例

Input
5
1 1 1 1 1
5
1
2
3
4
5
Output
0
1
0
1
0
Input
5
3 3 3 3 3
3
1
3
5
Output
0
1
1