AT_scpc2026_div1_i Tree, Game, and Query

#### 表示言語 / / テラとルルは， $ N $ 個の頂点と $ N-1 $ 本の辺からなる木の上でボードゲームをしている．木の各頂点 $ i $ には重み $ V_i $ と倍率 $ W_i $ がある．木の $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結ぶ．最初，すべての倍率 $ W_i $ は $ 1 $ であり， $ 1 $ 番頂点が根である． ゲームが始まると，各頂点 $ i $ に置かれている石をすべて取り除き，その頂点に $ V_i \cdot W_i $ 個の石を置く．プレイヤーは交互に次の行動を行う． 1. 石が $ 1 $ 個以上置かれている，根でない頂点を $ 1 $ つ選ぶ． 2. 選んだ頂点上の石を $ 1 $ 個以上好きな個数選び，**親頂点** の上に置く． これ以上行動できないプレイヤーが敗北し，相手が勝利する．各ゲームはテラから始まる． テラとルルはゲームがあまりにも得意なため，ゲームが単調だと考えた．テラとルルは次の $ 2 $ 種類のクエリを順に実行しながら， $ Q $ 回のゲームを行うことにした． - `1 x y`: 頂点 $ x $ と頂点 $ y $ を結ぶ最短経路上に存在するすべての頂点 $ i $ の倍率 $ W_i $ を $ 1 - W_i $ に変更する．すなわち， $ 0 $ は $ 1 $ に， $ 1 $ は $ 0 $ に変わる． - `2 z`: 頂点 $ z $ を木の根に変更する．頂点 $ z $ がすでに木の根である場合，何も起こらない． 各クエリを実行するたびに，テラとルルは最初からゲームを始める．両プレイヤーが勝利のために最善を尽くすとき， $ Q $ 回の各ゲームで誰が勝利するか求めよ．すべてのクエリの効果は累積する．

入力は以下の形式で標準入力から与えられる． > $ N $ $ Q $ $ V_1 $ $ V_2 $ $ \dots $ $ V_N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは次の $ 2 $ つの形式のいずれかで与えられる． ``` 1 x y ``` ``` 2 z ```

各クエリの後に行うゲームについて，テラが勝利するなら `Terra`，ルルが勝利するなら `Lulu` を $ 1 $ 行に出力せよ．

### Constraints - $ 2 \leq N \leq 300\,000 $ - $ 1 \leq Q \leq 500\,000 $ - $ 1 \leq V_i \leq 10^9 $ - $ 1 \leq u_i, v_i \leq N $ - $ 1 \leq x, y, z \leq N $ - $ u_i \ne v_i $ - 入力される数値はすべて整数である． - 与えられるグラフは木である．