题目描述

在那寂静的死后世界中，遗忘的记忆仿佛遥远的钟声，回荡在风中。一棵巨大的生命之树，悄然连接起每一颗尚未安息的灵魂的遗憾。

立华奏，那个沉默的守护者，在这片无声的领域中再次醒来。树上的每一个节点都藏着一个数字 $a_i$ ——是情感的碎片、未完成的心愿，以及逐渐淡去的光芒。

为了唤醒那些散落在世界各处的伙伴们，奏必须沿着一条从 $l$ 到 $r$ 的简单路径前行。路径上的值依次为 $w_1, w_2, \ldots, w_k$。她以第一个节点的值 $w_1$ 作为起点，作为她计数器的初始值。

在接下来的 $k-1$ 步中，她会：

1. 将下标加 $1$；
2. 选择将当前值 $w_{id}$ 与计数器 相加 或 相乘 。

她的使命是：将最终的计数器值变成 $24$。这是一个象征——代表完整的一天、24 小时的陪伴、24 个未说出口的心声。

输入格式

第一行两个整数 $n$ 和 $q$ ($1 \leq n, q \leq 5 \times 10^5$)，表示节点数量与操作数量；

接下来一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$)，表示每个节点上记录的记忆值；

接下来 $n-1$ 行，每行两个整数 $u, v$，表示一条连接节点 $u$ 和 $v$ 的边；

接下来 $q$ 行，每行为以下两种之一的操作格式：

• 1 l r：查询从节点 $l$ 到 $r$ 的路径是否可以通过上述操作使计数器变为 24；
• 2 x d：将第 $x$ 个节点的记忆值更新为 $d$。

输出格式

对于每个 1 l r 的询问，输出一行：

• 若能得到 $24$，输出 1；
• 否则输出 0。

9 8
1 3 1 2 4 6 5 2 2
1 2
1 3
2 4
2 5
3 6
3 7
6 8
7 9
1 4 8
1 4 9
1 2 8
1 6 9
1 9 6
2 3 8
1 6 9
1 9 6

1
1
0
1
0
0
1

8 8
3 2 3 3 1 3 1 2
2 1
3 2
4 1
5 2
6 4
7 6
8 7
2 4 4
1 8 2
2 5 2
1 2 4
1 5 2
2 1 3
1 4 8
2 6 2

1
1
0
1