D. The Red Herring Fallacy
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ammar and Ahmad decided to ask Obada to moderate a debate.

Ahmad (the affirmative team) is trying to prove that his algorithm "Matrix Bel Lotus" can solve any problem.

While Ammar (the opposing team) is going against his argument, Ammar needs your help.

Ahmad has some experience in debating, so Ammar needs to keep track of his debate tree and needs to know the lowest common ancestors of some nodes to support his arguments.

There are $$$n$$$ arguments in total, and the first argument is the main argument, while each other argument is either based on the main argument or another argument.

You will be given an array $$$a$$$ of $$$n$$$ elements, each element $$$a[i]$$$ which indicates that the argument number $$$i$$$ is based on the argument number $$$a[i]$$$.

Now, of course, Ahmad (an expert in debating) will try to juggle the arguments around and try to confuse Ammar by doing some updates on the array $$$a$$$, and occasionally Ammar will ask you some questions.

  • "$$$1$$$ $$$l$$$ $$$r$$$" : for every $$$l \le i \le r$$$ do $$$a[i]=max(1,a[a[i]])$$$
  • "$$$2$$$ $$$l$$$ $$$r$$$ $$$x$$$" : for every $$$l \le i \le r$$$ do $$$a[i] = max(1,a[i]-x)$$$
  • "$$$3$$$ $$$u$$$ $$$v$$$" : print $$$LCA(u,v)$$$
Input

The first line contains $$$tc$$$ $$$(1 \leq tc \leq 100)$$$ — the number of test cases.

The first line of each test case contains two integers $$$n,q$$$ $$$(2 \leq n \leq 10^5)$$$ $$$(1 \leq q \leq 10^5)$$$ — the number of arguments and the number of queries.

The next line contains $$$n$$$ integers that represent the array $$$a$$$ $$$(1 \le a[i] \lt i)$$$ except for $$$a[1] = -1$$$.

The following $$$q$$$ lines will be one of the following:

  • "$$$1$$$ $$$l$$$ $$$r$$$" $$$(2 \le l \le r \le n)$$$
  • "$$$2$$$ $$$l$$$ $$$r$$$ $$$x$$$" $$$(2 \le l \le r \le n)$$$ $$$(1 \le x \le n-1)$$$
  • "$$$3$$$ $$$u$$$ $$$v$$$" $$$(1 \le u,v \le n)$$$

It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$10^5$$$ , and the sum of $$$q$$$ over all testcases doesn't exceed $$$10^5$$$.

Output

For each query of type $$$3$$$, print the answer.

Example
Input
1
11 5
-1 1 1 2 2 3 3 4 4 5 5
3 8 10
2 7 10 2
3 10 6
1 10 11
3 11 5
Output
2
3
2
Note

Initially, the tree looks like this:

Then after the second query:

Then after the fourth query: