AT_kupc2018_m 整数と根付き木

[problemUrl]: https://atcoder.jp/contests/kupc2018/tasks/kupc2018_m $ N $ 頂点からなる根付き木 $ T $ があり、頂点には $ 1 $ から $ N $ の番号がついています。はじめは頂点 $ 1 $ が根です。 また、$ N-1 $ 本の辺のうち、$ i $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 各頂点 $ v $ はそれぞれ整数の配列 $ A_v $ を持っています。はじめはすべて空です。 この根付き木 $ T $ に $ Q $ 回のクエリ操作を行います。クエリ操作は $ 3 $ 種類あり、それぞれ以下の通りです。 - `1 v x k` ― 頂点 $ v $ の部分木に含まれる任意の頂点（頂点 $ v $ を含む） $ u $ に対して、 $ A_u $ に値 $ x $ を $ k $ 個追加する。 - `2 v y z` ― 頂点 $ v $ の配列 $ A_v $ に含まれる要素の中で、$ val $ $ xor $ $ y\ \leq\ z $ を満たす値 $ val $ の個数を求める。ここで、$ s $ $ xor $ $ t $ は $ s $ と $ t $ のビットごとの排他的論理和を指す。 - `3 v` ― 根を頂点 $ v $ に変更する。 あなたは、このようなクエリを順番に処理するプログラムを書かなくてはなりません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ : $ $ a_{N-1} $ $ b_{N-1} $ $ Q $ $ Query_1 $ $ Query_2 $ $ : $ $ Query_Q $ - $ Query_i $ は `1 v x k`、`2 v y z` もしくは `3 v` の形式で一行ごとに与えられる。

`2 v y z` の形式のクエリに対し、与えられた順番に答えを出力せよ。

### 制約 - 入力は全て整数である。 - $ 1\ \leq\ N\ \leq\ 1.4\ \times\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 1.4\ \times\ 10^5 $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ N-1) $ - $ 1\ \leq\ v\ \leq\ N $ - $ 0\ \leq\ x,\ y,\ z\