题目描述

Asuka 面前有一棵带点权的二叉树，$1$ 号点是它的根。

Asuka 对于优雅的二叉搜索树情有独钟。另外，这棵树的点权时不时会被修改。

你需要完成两种操作。第一个操作为修改某个点的点权。第二个操作为回答某棵子树内有多少棵子树为二叉搜索树。

一棵二叉搜索树中每个点都满足左子树中所有点权都小于等于自己，且右子树中所有点权都大于等于自己。

输入格式

第一行三个整数 $n,q,K$，其中 $K$ 表示子任务编号。对于没有说明子任务编号的样例，$K=0$。

接下来 $n$ 行，每行两个整数表示每个点的左儿子和右儿子编号。编号为 $0$ 表示没有。

接下来一行 $n$ 个整数表示初始点权 $a_i$。

接下来 $q$ 行，每行为 $1\ x\ y$ 或 $2\ x$。

$1\ x\ y$ 表示修改 $x$ 的点权为 $y$。

$2\ x$ 表示询问 $x$ 的子树内有多少棵二叉搜索树。

输出格式

对于每个操作 $2$，输出一行一个整数表示答案。

样例输入 1

6 5 0
2 3
4 0
5 6
0 0
0 0
0 0
4 1 3 2 2 5
2 2
1 3 3
1 2 2
1 3 5
2 1

样例输出 1

1
5

数据范围

对于所有数据，$1\le n,q\le 2\times 10^5,1\le a_i,x,y\le n$。

特殊性质 $A$：第 $i$ 个点的父亲在 $[1,i-1]$ 中随机，若儿子位置满则一直随机。

特殊性质 $B$：询问满足 $x=1$。