Quake and Rebuild
Description
The Kingdom of Calamita was a small nation constantly plagued by natural disasters. The people built their villages and towns in the shades of the great Banyan tree that stood at the kingdom's center. Its massive roots provided stability to the land and the villagers always looked to it for guidance and protection.
The great tree is a rooted tree whose root is node $1$. For other node $i\ (i>1)$, its parent in the tree is $fa[i](1\le fa[i]<i)$ and there is an edge in between. There were two types of events that took place in the Kingdom of Calamita — quake and rebuild.
1. Quake: When a tremor hit the range $[l, r]$ with a magnitude of $d$, it caused the parent node of every node in that range to shift down by d. In other words, $\forall i \in [l, r],\ fa'[i] = max(1, fa[i]-d). $ The tree structure shifts after that.
2. Rebuild: During the rebuilding after some disasters, the villagers were seeking for economic recovery. To boost the economy, they set a list of nodes $[b_1, b_2,..., b_k]$ to become the new trade centers and decided to build some temporary transportation hubs to connect all of the new trade centers. Two trade centers are connected if and only if every node on the simple path between these two centers has been built with a temporary transportation hub on it. Obviously, the villagers were only interested in the minimal number of temporary transportation hubs to achieve the goal.
Over time there were $m$ such events — some quakes shook up the root system, and some rebuilding aimed at economic recovery.
For each rebuild plan, you need to help the villagers figure out the minimal number of temporary transportation hubs to make all trade centers connected.
Note that Two rebuild events are $\textbf{independent}$, i.e., the temporary transportation hubs will shut down after the previous rebuilding event, and if you want to use it again, you need to rebuild it.
The first line contains two integers $n,m\ (2\le n,m\le 2\times 10^5)$ respectively representing the number of nodes in the tree and the number of events.
The second line contains an integer $n-1$ integers, the $i$-th integer $fa[i+1]$ denotes the parent of node $i+1$.
The following $m$ lines describe the events.
For the quake, you are given four positive integers $1,l,r,d\ (2\le l\le r\le n, d\le n)$.
For the rebuilding, you are firstly given two positive integers $2$ and $k$, then following $k$ positive integers representing $b_1, b_2,...,b_k$. The list of node's indexes may coincide, you can just ignore the duplication and keep only one of the same indexes.
It's guaranteed that $\sum k \le 6\times 10^5$ across all rebuilding events.
For each rebuild event, you should output one line consisting one positive integer representing the minimal number of the temporary transportation hubs to make the trade centers connected.
Input
The first line contains two integers $n,m\ (2\le n,m\le 2\times 10^5)$ respectively representing the number of nodes in the tree and the number of events.
The second line contains an integer $n-1$ integers, the $i$-th integer $fa[i+1]$ denotes the parent of node $i+1$.
The following $m$ lines describe the events.
For the quake, you are given four positive integers $1,l,r,d\ (2\le l\le r\le n, d\le n)$.
For the rebuilding, you are firstly given two positive integers $2$ and $k$, then following $k$ positive integers representing $b_1, b_2,...,b_k$. The list of node's indexes may coincide, you can just ignore the duplication and keep only one of the same indexes.
It's guaranteed that $\sum k \le 6\times 10^5$ across all rebuilding events.
Output
For each rebuild event, you should output one line consisting one positive integer representing the minimal number of the temporary transportation hubs to make the trade centers connected.
4 5
1 2 2
2 2 1 4
1 2 3 1
2 3 2 3 4
1 4 4 1
2 2 3 4
10 10
1 2 3 3 4 5 7 7 9
1 2 10 3
2 9 9 5 3 10 7 2 4 6 8
1 6 10 3
1 2 7 3
1 7 10 3
2 2 4 3
2 3 7 4 4
1 3 9 3
1 3 9 3
1 10 10 3
3
4
3
10
3
3