题目描述

J君正在研究量子信息的纠缠。 具体来说，J君有一个初始为空的信息集。 她会进行$m$次操作，有时，她会向信息集内加入一个长度不超过L的数字串（一个数字串为一个仅由$0$到$9$组成的非空字符串），有时她会给出一个数字串，询问这个数字串是否包含在她的信息集中，有时她会选取两个长度不超过$L$的数字串，使它们在信息集内互相纠缠。 两个数字串$A$和$B$互相纠缠表示，对于信息集中的任意串$A+C$，需满足$B+C$也在信息集中，对于信息集中的任意串$B+D$，需满足$A+D$也在信息集中（其中$+$代表字符串顺序连接，$C、D$可能是空串)，因此一次纠缠操作可能导致若干个数字串 (可能为无穷多个) 被加入信息集中。 由于两个数字串的纠缠是一种状态，在纠缠后的任何时刻都需满足以上性质，因此第一次纠缠操作之后的任何添加操作都可能导致大于$1$个(可能为无穷多个)数字串被加入信息集。 你需要做的就是回答 J 君的所有询问。

输入

第一行包含一个正整数$m$，代表操作数。 接下来$m$行，每行可能有以下形式： “$1\;s$”表示将数字串$s$加入信息集中。 “$2\;s$”表示询问数字串$s$是否在信息集中。 “$3\;a\;b$”表示使数字串$a$和$b$互相纠缠。

输出

对于每一个2操作，如果询问串不在集合中，请输出一行一个整数$0$，否则输出一行一个整数$1$。

输入样例

11
1 123
2 123
2 0
3 12 13
1 124
2 133
2 134
2 13
3 1 11
2 111
2 11111111111111111111111124

输出样例

1
0
1
1
0	
0
1	

提示

【数据规模和约定】

测试点	m≤	c≤	其它
1	$10^5$	2050	不含操作3
2			所有串中只会出现字符0
3	500	200	信息集中元素有限
4		500
5
6	$10^5$	2050
7	500	500	N/A
8	2000	2050
9	$10^5$		保证所有1操作和所有3操作都在2操作前面
10			N/A

100%的数据满足$m≤10^5，c≤2050，S≤8×10^6，L≤50，P≡m(\bmod 10)$。 其中$c$代表操作$1$和操作$3$次数之和，$S$代表询问字符串的总长度。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。