在 Bubbleland 中,一群特殊编程部队获得了一项绝密工作,以计算一种新的未知病毒可能感染的人数。该州人口为 $$$n$$$ ,每天都会有关于人与人之间新接触的新信息。特殊编程力量的工作是计算某个人在过去 $$$k$$$ 天内有多少联系人。
新病毒的潜伏期为 $$$k$$$ 天,在此之后人们认为不具有传染性。由于这种新病毒极其危险,政府将过去 $$$k$$$ 天内直接或间接接触过的每个人都标记为可疑,无论接触顺序如何。
这种病毒很奇怪,人们无法获得持久的免疫力。
您需要帮助特殊编程力量计算给定人员的可疑人数(与给定人员接触过的人数)。
开头 $$$n$$$ 有 3 个给定输入,其中 $$$n$$$ 是人口,$$$q$$$ 查询数量,$$$k$$$ 病毒潜伏时间(以天为单位)。每个查询都是以下三种类型之一:
1. ($$$x$$$, $$$y$$$) 人 $$$x$$$ 和人 $$$y$$$ 于当天相遇 ($$$x \neq y$$$)。
2. ($$$z$$$) 返回与$$$z$$$接触的人数,算上他自己。
3. 当日结束时移至第二天。
输入
输入的第一行包含三个整数 $$$n$$$ ($$$1 \le n\le 10^5$$$) 该州的人数、$$$q$$$ ($$$1 \le q\le 5×10^5$$$) 查询数量和 $$$k$$$ ($$$1 \le k\le 10^5$$$) 病毒潜伏时间天。
接下来的 $$$q$$$ 行均以整数 $$$t$$$ ($$$1 \le t\le 3$$$) 开头,表示查询的类型。
第一种类型 ($$$x \neq y$$$) 的查询中跟随一对整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$)。
第二种类型的查询中跟随一个整数$$$i$$$ ($$$1 \le i\le n$$$)。
第三类查询没有以下号码。
输出
对于第二种类型的查询,在单独的行上打印当前与给定人员联系的人数。
示例
输入 #1
5 12 1 1 1 2 1 1 3 1 3 4 2 4 2 5 3 2 1 1 1 2 1 3 2 2 1 3 2 1
输出 #1
4 1 1 3 1
输入 #2
5 12 2 1 1 2 1 1 3 1 3 4 2 4 2 5 3 2 1 1 1 2 1 3 2 2 1 3 2 1
输出 #2
4 1 4 4 3
输入 #3
10 25 2 1 9 3 2 5 1 1 3 1 3 1 2 2 1 8 3 1 5 6 3 1 9 2 1 8 3 2 9 1 3 1 2 5 1 6 4 3 3 2 4 3 1 10 9 1 1 7 3 2 2 3 1 5 6 1 1 4
输出 #3
1 1 5 2 1 1
注意
注意$$$1$$$和$$$2$$$第一天和第二天$$$1$$$和$$$3$$$是否有联系,$$$k$$$>$$$1$$$$$$3$$$的联系人数为$$$3$$$(人:1,2,3)。