Migrated from Lutece 2526 土豆的树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

土豆喜欢玩《哦的世界》，尤其喜欢在里面种树，土豆在里面种了一棵很大的树，但是他觉得这棵树并不好看，于是他准备在这棵树上倒上一些颜料，让它变得鲜艳。

在《哦的世界》里面，树由方块组成的，方块编号从$1$ 到 $n$。液体会从某个高度的方块按一定的规则流向比该方块低一个高度的方块：除了最顶上的方块（可能多个），每个方块都有且仅有一个上游方块，液体只会从上游方块处流动到该方块处（这点与某游戏不同），以至于继续往下流动。

土豆通过大量实验和观察，知道了每个非顶层的方块对应的上游方块是哪个。于是，土豆开始准备泼颜料了：初始所有方块的颜色均为 $0$ 号颜色，之后每次选择一个方块，然后从自己准备的颜料中选择一种编号的颜色，往这个方块上倒上一桶这个颜料，很快啊，这个方块及它下方的方块都被染成了这种颜色（下方是指所有能被这桶颜料流到的方块）。

土豆是一个有艺术追求的人。为了让最终这棵树鲜艳得恰到好处，土豆也不是一直不停的泼颜料，有时候他也会停下来数一数，这棵树某些部分有多少种颜色，看看后面是不是需要做一些调整。同时，土豆也严格控制着颜色的「对比度」，他不能接受任何时候树上存在两种颜色，它们的编号差异大于 $50$。

土豆的这棵树由 $n$ 个方块组成，土豆接下来 $m$ 天会干两种事情，要么往某个方块上泼上一桶颜料，要么数一下，一个方块及其下方的方块被染成了多少种颜色，但是土豆不擅长于数数，于是找到了擅长数数的你来帮助他。

Input

第一行两个数 $n,m$，其中 $n$ 表示方块的个数，$m$ 表示天数。

第二行 $n$ 个数 $a_1,a_2,...,a_n$，如果 $a_i$ 等于 $0$，表示 $i$ 号方块是顶层方块；否则，$a_i$ 号方块为 $i$ 号方块的上游方块。注意可能存在不止一个顶层方块。

接下来 $m$ 行，每行前两个数为 $q_i,p_i$，如果 $q_i=1$，则后面还有第三个数 $c_i$，表示土豆往 $p_i$ 号方块处倒了一桶颜色编号为 $c_i$ 的颜料；如果 $q_i=2$，则表示土豆想知道此时 $p_i$ 号方块及其下方的方块一共含有多少种颜色。

输入保证，任何时候，树上都不存在两种编号相差大于 $50$ 的颜色。

树上所有的方块均由 $1$ 到 $n$ 之间的一个数唯一编号。

Output

对于每次 $q_i=2$，请输出 $p_i$ 号方块及其下方的方块一共含有多少种颜色。

Samples

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

2
3
4

Constraints

$1\leq n\leq 200000,1\leq m\leq 200000$ $0\leq a_i\leq n$ $1\leq q_i\leq 2,1\leq p_i\leq n,0\leq c_i\leq 10^9$

Resources

2021 UESTC ICPC Training for Data Structures