题目描述

Snuke 现在有 $1$ 克黄金和 $0$ 克白银。他将在接下来的 $N$ 天进行黄金和白银的交易。每天，他有两个选择：什么都不做，或者进行一次交易。如果他在第 $i$ 天进行交易（$1 \leq i \leq N$），则会发生以下情况。

• 如果交易之前他有 $x$ 克黄金，那么全部换成 $x \times A_i$ 克白银。另一方面，如果他有 $x$ 克白银，那么全部换成 $x / A_i$ 克黄金。

Snuke 的目标是最大化最后拥有的黄金数量。找出一种实现他目标的方式。

约束条件

• $2 \leq N \leq 200000$
• $1 \leq A_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出

按照以下格式输出答案：

$v_1$ $v_2$ $\cdots$ $v_N$

其中，$v_i$ 是表示第 $i$ 天行动的整数（$0 \leq v_i \leq 1$）。$v_i=0$ 表示什么都不做，$v_i=1$ 表示进行一次交易。如果有多个可能的解决方案，输出任何一个都被视为正确。

示例输入 1

3
3 5 2

示例输出 1

0 1 1

最佳行动序列如下。

• 第 $1$ 天：什么都不做。

• 第 $2$ 天：将 $1$ 克黄金换成 $5$ 克白银。

• 第 $3$ 天：将 $5$ 克白银换成 $2.5$ 克黄金。

示例输入 2

4
1 1 1 1

示例输出 2

0 0 0 0

例如，$(v_1,v_2,v_3,v_4)=(1,1,1,1)$ 也被认为是正确答案。

示例输入 3

10
426877385 186049196 624834740 836880476 19698398 709113743 436942115 436942115 436942115 503843678

示例输出 3

1 1 0 1 1 1 1 0 0 0