406011: GYM102218 D Dynamic Network

Recently, a startup by a group of students has become more popular and there are plans for expanded offices. Bryan got an internship in this company and his task is to manage its internal network.

The company will acquire some computers over time. Initially, there is only a computer with $$$id=1$$$. When a new computer is added to the network, it's directly connected to a computer with $$$id=p$$$. The $$$id$$$ of the new computer is the minimum positive integer that has not been used as the $$$id$$$ of any other computer.

To determine the performance of the internal network, Bryan is required to answer several queries about what is the minimum number of computers through which a message must go if it is sent from computer with $$$id=u$$$ to computer with $$$id=v$$$ (start and end are also counted). Also, when a new computer is added, Bryan has to determine this number for a message sent from the new computer to the computer with $$$id=1$$$, since it is the most important computer. The computers have enough information to determine the optimum way to send a message to another computer.

Since there could be many computers in the network, Bryan needs your help to write a program that answers the queries. Note that the queries are encoded.

The first line contains an integer $$$Q$$$ ($$$1 \leq Q \leq 2*10^5$$$) $$$-$$$ the number of queries.

Each of the next $$$Q$$$ line describes a query. It contains a integer $$$t$$$ ($$$t \in [1,2]$$$) $$$-$$$ the type of query.

The queries will be encoded. Let $$$last$$$ be the answer for the last query answered and let $$$curr$$$ be the number of computers connected in the network so far. Initially $$$last=0$$$ and $$$curr=1$$$.

• If $$$t=1$$$, then one integer $$$p'$$$ follows ($$$0 \leq p' \leq 2*10^5$$$). Set $$$p=(p'+last)\%curr+1$$$. It means that a new computer is connected to the computer with $$$id=p$$$. Increase the value of $$$curr$$$ by one.
• If $$$t=2$$$, then two integers $$$u'$$$ and $$$v'$$$ follow ($$$0 \leq u', v' \leq 2*10^5$$$). Set $$$u=(u'+last)\%curr+1$$$ and $$$v=(v'+last)\%curr+1$$$. It means that a message is sent from computer $$$u$$$ to computer $$$v$$$.

If the query is of type $$$1$$$, print the number of computers through which a message must go if it is sent from the new computer to computer with $$$id = 1$$$.

Otherwise print the amount of computers through which the message must go if it is sent from computer $$$u$$$ to computer $$$v$$$.

7
1 0
1 2
1 2
1 2
2 0 4
2 1 2
2 2 1

2
2
3
3
4
2
3

6
1 1
2 1 2
1 0
1 1
2 0 3
2 2 2

2
2
2
2
3
1

In the first sample, the new computers are connected as follows

• Add new computer with $$$id=2$$$ and connect it to computer with $$$id=1$$$.
• Add new computer with $$$id=3$$$ and connect it to computer with $$$id=1$$$.
• Add new computer with $$$id=4$$$ and connect it to computer with $$$id=2$$$.
• Add new computer with $$$id=5$$$ and connect it to computer with $$$id=2$$$.

And actual queries of the second type are:

• $$$u=4$$$ and $$$v=3$$$
• $$$u=1$$$ and $$$v=2$$$
• $$$u=5$$$ and $$$v=4$$$