题目描述

Aki 最近在研究魔法咒语。每天他都会把听到的咒语记录下来，但他发现有些咒语会被反复念出。

现在给你一个按时间顺序记录的咒语列表，共有 $n$ 条字符串 $s_1,s_2,\dots,s_n$。

Aki 的记录规则如下：

• 当读入一个新咒语 $s_i$ 时，如果它 之前已经出现过（即存在某个 $j<i$ 使得 $s_j=s_i$），Aki 会在本行输出 1；
• 否则，说明它是第一次出现，Aki 会输出 0；
• 每读入一个咒语就立刻输出一次判断结果（共输出 $n$ 行）。

请你按 Aki 的规则输出所有结果。

输入格式

第一行输入一个整数 $n$。
接下来 $n$ 行，每行输入一个字符串 $s_i$。

• $1 \le n \le 10^5$
• $1 \le |s_i| \le 30$
• 字符串只包含英文字母（大小写敏感）和数字

输出格式

输出 $n$ 行。
第 $i$ 行输出一个整数，表示第 $i$ 个咒语是否重复：重复输出 1，否则输出 0。

6
fire
water
fire
wind
wind
fire

0
0
1
0
1
1