题目背景

往昔，阴阳由天地所创，孕大含深；今昔，时光为记忆所刻，随行如影。
流水落花间，嬉闹于阴阳树的意境；沧海桑田间，铭心于阴阳忆的缤斓。
阴鱼，阳鱼……挥翰着日月的闲情，留存着浣熊的惬意，却不复存在……
小浣熊 CleverRaccoon 与最后一瞬阴阳，含泪而笑……

题目描述

一棵树的各结点都悬挂着 $1$ 条阴鱼或阳鱼（分别用 $0,1$ 表示），它们可能在某刻由于基因突变互相转化。

小浣熊 CleverRaccoon 带着一只能装 $2$ 条鱼的篮筐在此树的某条链上行走。当他所在点上的鱼与某条筐内鱼的属性相反时，他会将这 $2$ 条鱼合成 $1$ 条阴阳鱼并吃下；在筐中没有满的条件下，他会将所在点上的鱼放入筐中。

现有两种操作：

1. 一个结点上的阴阳鱼发生基因突变，变为另一种类型的阴阳鱼。
2. 帮助聪明的小浣熊 CleverRaccoon 求出：当他沿着这棵树上的某条链行走时，能吃下的阴阳鱼的条数。

输入格式

第一行，两个正整数 $n$ 和 $q$，表示结点个数、修改和询问总次数。

第二行 $n$ 个整数，表示每个结点上悬挂的鱼的属性。

接下来 $n−1$ 行，每行两个正整数 $u,v$，表示 $u$ 和 $v$ 两个点之间有一条边。

接下来 $q$ 行，格式为 1 u 或 2 u v。

若格式为 1 u，则表示结点 $u$ 上的鱼基因突变。

若格式为 2 u v，则表示询问小浣熊 CleverRaccoon 在从 $u$ 到 $v$ 的简单路径中能吃下的阴阳鱼的条数。

输出格式

对于每次询问，单行输出一个整数，表示小浣熊 CleverRaccoon 能吃下的阴阳鱼的条数。

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

3
2

提示

数据范围

本题采用 Subtask 捆绑测试。

• Subtask 0（10 points）：$n,q \leq 10$。
• Subtask 1（15 points）：$n,q \leq 2\times10^3$。
• Subtask 2（15 points）：保证树的深度小于 $10^3$。
• Subtask 3（60 points）：无特殊限制。

对于所有测试数据： $1 \leq n,q\leq 10^5$。