题目描述

「搞 OI 不如种田。」

小 D 在家种了一棵二叉树，第 $i$ 个结点的权值为 $a_i$。

小 D 为自己种的树买了肥料，每天给树施肥。

可是几天后，小 D 却发现树上有几个结点枯死了，他这才发现，自己买的肥料是二叉搜索树专用版。

二叉搜索树是一种二叉树，满足每个结点的权值大于左子树内所有点的权值，小于右子树内所有点的权值。

二叉搜索树专用版肥料是这么工作的：首先，假设所有节点权值互不相同（小 D 的二叉树可能不满足），每种权值对应一种肥料，所有肥料会从根进入树中，如果一种肥料对应的权值等于当前结点权值，这种肥料会被当前结点完全吸收，否则若肥料对应的权值小于当前结点权值，肥料会流向左子树，否则流向右子树，如果流向的子树为空，肥料只好流失蒸发了。显然，如果树是二叉搜索树，所有节点都能吸收到肥料。

小 D 觉得自己还能抢救一下，他会进行若干次操作，每次操作修改一个点的权值或者翻转一个子树（子树内所有节点左右儿子互换）。在操作过程中，他有时会想知道一个点当前是否能吸收到肥料，以决定之后如何操作，请你帮帮可怜的小 D 吧。

输入格式

第一行两个正整数 $n, m$，分别表示节点数和操作数。

接下来 $n$ 行，每行三个非负整数，其中第 $i$ 行第一个整数表示 $a_i$，后两个数分别表示 $i$ 号点的左右儿子，没有则为 $0$。

接下来 $m$ 行，每行先给出两个正整数 ${\rm opt}, x$。若 $\rm opt = 1$，接下来还有一个整数 $y$，表示把结点 $x$ 的权值修改为 $y$；若 $\rm opt = 2$，表示翻转以 $x$ 为根的子树；若 $\rm opt = 3$，表示查询 $x$ 号点是否能吸收到肥料。

输出格式

对于每个询问，输出一行 YES 或 NO 表示答案。

3 7
10 2 3
5 0 0
5 0 0
3 1
3 2
3 3
1 3 100
3 3
2 1
3 3

YES
YES
NO
YES
NO

数据范围与提示

对于全部数据， $1 \leq n, m \leq 10^5, 0 \leq a_i, y \leq 10^9$。

• 子任务 $\rm 1(points: 20)$：$n, m \leq 5000$
• 子任务 $\rm 2(points: 30)$：$\rm opt \neq 2$
• 子任务 $\rm 3(points: 50)$：无特殊限制