AT_scpc2026_div1_i Tree, Game, and Query

#### 表示言語 / / Terra and Lulu are playing a board game on a tree consisting of $ N $ vertices and $ N-1 $ edges. Each vertex $ i $ of the tree has a weight $ V_i $ and a multiplier $ W_i $ . The $ i $ -th edge of the tree connects vertices $ u_i $ and $ v_i $ . Initially, all multipliers $ W_i $ are $ 1 $ , and vertex $ 1 $ is the root. When a game starts, all stones currently on each vertex $ i $ are removed, and $ V_i \cdot W_i $ stones are placed on that vertex. The players take turns performing the following action. 1. Choose a non-root vertex with at least $ 1 $ stone on it. 2. Choose one or more stones on the chosen vertex and move them to its **parent vertex**. The player who can no longer perform an action loses, and the other player wins. Each game starts with Terra. Terra and Lulu are so good at the game that they found it monotonous. They decided to play $ Q $ games while performing the following two types of queries in order. - `1 x y`: For every vertex $ i $ on the shortest path between vertices $ x $ and $ y $ , change its multiplier $ W_i $ to $ 1 - W_i $ . In other words, $ 0 $ changes to $ 1 $ , and $ 1 $ changes to $ 0 $ . - `2 z`: Change the root of the tree to vertex $ z $ . If vertex $ z $ is already the root of the tree, nothing happens. Each time a query is performed, Terra and Lulu start a new game from the beginning. For each of the $ Q $ games, determine who wins if both players play optimally. The effects of all queries are cumulative.

The input is given from Standard Input in the following format: > $ 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 $ Each query is given in one of the following two formats. ``` 1 x y ``` ``` 2 z ```

For each game played after a query, output `Terra` if Terra wins, and `Lulu` if Lulu wins, one per line.

### 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 $ - All given numbers are integers. - The given graph is a tree.