描述

小明在楼下种了一棵部分可持久化动态树,这棵树有n个节点,开始时没有边。而且这是一棵有根树,其中1号节点为根节点。

别忘了这是一棵动态树,每时每刻都是在变化的,所以你需要完成这样的操作。

操作0:连接u、v,使得v是u的父亲。保证这个操作前u没有父亲,并且u不是1,u≠v。

别忘了这是一个部分可持久化的数据结构,所以我们需要询问过去的信息。

操作1:查询第t次操作后(t=0时指开始时刻),u号节点的第k个祖先是几号节点。(u号节点的第0个祖先为自己,第1个祖先为fa[u],第2个祖先为fa[fa[u]]。)如果u没有第k个祖先,输出0。

操作2:查询第t次操作后(t=0时指开始时刻),u号节点的深度是多少。(如果u没有父亲,那么u的深度为0,否则为fa[u]的深度+1。)

以上保证t小于当前时刻。

为了保证这个数据结构是部分可持久化的,防止离线做法,我们会将部分输入文件加密,详细请看输入格式。

输入格式

第一行3个非负整数,n,m,b。n为节点数,m为操作数,b为加密的参数。

接下来有m行,每行可能有3或4个整数。

第一个整数为op',代表加密后的操作编号。真实的op = (op'+lastans*b) \% 3,那么我们接下来执行的操作就是操作op。lastans指上一次操作1或操作2输出的结果,如果之前没有操作1或操作2,那么lastans=0。

如果op=0,那么为操作0。后面有2个非负整数u',v',代表加密后的u,v参数。真实的u=(u'+lastans*b)\%n+1v=(v'+lastans*b)\%n+1

如果op=1,那么为操作1。后面有3个非负整数t',u',k',代表加密后的t,u,k。真实的t=(t'+lastans*b)\%mu=(u'+lastans*b)\%n+1k=(k'+lastans*b)\%n请注意k的加密方式,和u的加密方式不同。

如果op=2,那么为操作2。后面有2个非负整数t',u',代表加密后的t,u。真实的t=(t'+lastans*b)\%mu=(u'+lastans*b)\%n+1

输出格式

对于每个操作1和操作2,输出1行1个非负整数,表示这个操作的答案。

样例输入

5 10 7
0 1 0
1 1 1 1
2 0 3
0 5 0 4
1 3 2 1
2 2 1
2 1 4
1 8 2
2 6 4
1 0 2

样例输出

1
0
1
0
1
3

样例解释

操作解密后应该是:

0 2 1
1 1 2 1
0 3 1
1 2 3 1
1 3 3 1
0 5 4
0 4 2
2 5 5
2 6 5
2 7 5

数据范围与约定

保证文件中出现的所有数字(除n、m外)都为非负整数并且≤10000。

来源

原创