题目背景

滑稽树上滑稽果，滑稽树下你和我。

小L发现自己家旁长了一棵滑稽树，非常好奇，便仔细观察滑稽树的性质。

问题描述

小 \(L\) 发现，滑稽树可以看成 \(n\)（ \(1\le n\le 100000\) ）个节点（节点为 \(1\sim n\) 号）和 \(n-1\) 条边组成的无项联通图，也就是一棵树，规定 \(1\) 号节点为根，每一个节点上都长着一颗滑稽果，根据滑稽果种类的不同，第 \(i\) 个节点上的滑稽果可以将其看成一个数 \(a_i\)（ \(1\le a_i\le n\) ）。

小 \(L\) 发现，有时滑稽果的种类会发生变化，记作 x y，表示编号为 \(x\) 的节点的滑稽果变为第 \(y\) 种。

小 \(L\) 想要知道，对于指定的 \(m\) 个点 \({c_1,c_2 ,……,c_m }\)，对于每个点需要你输出已它为根的子树中被指定点的滑稽果种类数个数。

输入格式

第一行一个数 \(n\) 表示树有 \(n\) 个节点。

第二行 \(n\) 个数表示初始时的节点上的滑稽果种类。

然后 \(n-1\) 行，每行两个数 \(x,y\)，表示 \(x\) 与 \(y\) 之间有直接相邻的边。

下一行一个数 \(q\) ，表示变化和查询的数目总和。

以下 \(q\) 行，每行第一个数字若为 \(1\)，则表示变化操作，后跟2个数\(x\ \ y\)。

若第一个数字为 \(2\)，则表示询问操作，后跟 \(1\) 个数 \(m\)，表示时间和被指定点个数，后跟 \(m\) 个数,表示 \({ c_1, c_2 ,\cdots, c_m }\)。

输出格式

对于每一个查询操作（按读入顺序），输出一行，包括每个被指定点（按读入顺序）的答案。

样例

样例输入 1

5
1 2 3 4 5
1 2
2 3
1 4
4 5
4
1 3 1
2 3 3 1 5
1 5 4
2 5 5 4 3 2 1

样例输出 1

1 2 1
1 1 1 2 3

数据范围

性质1：保证查询时节点读入顺序从小到大。

性质2：保证任意一个 \(m\le 30\);
\(100\%\) 的数据 \(n\le 100000;q\le 100000; \sum m\le 200000\); 任意一个 \(m\le n\)。\(a_i\) 永远 \(\le n\) ;所有数字均小于 \(2^{31}-1\);

时空限制

\(1\mathrm s,512\mathrm{MiB}\)