1231 : 地震与重建

Description

卡拉米塔王国是一个经常受到自然灾害困扰的小国。人们在王国中心巨大榕树的庇护下建立了他们的村庄和城镇。它巨大的根系为土地提供了稳定性，村民们总是向它寻求指导和保护。

这棵巨大的榕树是一棵有根树，其根节点为 \(1\) 号节点。对于其他节点 \(i\ (i>1)\)，它在树中的父节点为 \(fa[i]\ (1\le fa[i]<i)\)，并且它们之间存在一条边。在卡拉米塔王国中，有两种类型的事件 — 地震和重建。

1. 地震：当一次震级为 \(d\) 的地震发生在范围 \([l, r]\) 时，榕树的结构会发生某些变化，具体来说，\([l,r]\) 范围内每个节点的父节点编号都会减少 \(d\)。换句话说，对于 \(\forall i \in [l, r]\)，有 \(fa'[i] = max(1, fa[i]-d)\)。

2. 重建：在一些灾难后的重建过程中，村民们希望经济快点复苏。为了促进经济，他们会在一些节点 \([b_1, b_2,..., b_k]\) 上重建新的贸易中心，并决定建立一些临时交通枢纽来连接所有的新贸易中心。当且仅当连接两个贸易中心之间的简单路径上的每个节点都建有临时交通枢纽时，这两个贸易中心才会相连。显然，村民们只需要建立最少的临时交通枢纽来完成目标。

据历史的记载，王国共发生了 \(m\) 个这样的事件 — 一些地震震动了榕树根，一些灾后重建旨在经济复苏。

对于每个重建计划，你需要帮助村民们找出使所有贸易中心相连所需的最小临时交通枢纽数量。

请注意，两个重建事件是独立的，即在前一次重建事件之后，临时交通枢纽将关闭，如果你想再次使用，你需要重新建立它。

Input

第一行包含两个整数 \(n,m\ (2\le n,m\le 2\times 10^5)\)，分别表示树的大小和事件的数量。

第二行包含 \(n-1\) 个整数，第 \(i\) 个整数 \(fa[i+1]\) 表示节点 \(i+1\) 的父节点。

接下来的 \(m\) 行描述了这些事件。

对于地震事件，给出了四个正整数 \(1,l,r,d\ (2\le l\le r\le n, d\le n)\)。

对于重建事件，首先给出了两个正整数 \(2\) 和 \(k\)，然后是 \(k\) 个正整数，表示 \(b_1, b_2,...,b_k\)。节点可能会重复，你可以忽略重复的部分。

保证在所有重建事件中，\(\sum k \le 6\times 10^5\)。

Output

对于每个重建事件，你应该输出一行，其中包含一个正整数，表示使新建贸易中心相连所需的最小临时交通枢纽数量。

Sample

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
##CASE##
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

##CASE##
10
3
3

Hint

Source

Author

SYSU