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.

特拉（Terra）和露露（Lulu）正在一棵包含 $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$ 颗石子；

2. 从所选顶点上选择一颗或多颗石子，并将它们移动至其父顶点。

无法再执行操作的玩家判负，另一方获胜。每局游戏均由特拉先手。

特拉与露露棋艺高超，以至于觉得此游戏单调乏味。于是她们决定进行 $Q$ 局游戏，并按顺序执行以下两类查询：

• 1 x y：对顶点 $x$ 与 $y$ 之间最短路径上的每一个顶点 $i$，将其乘数 $W_i$ 更新为 $1 - W_i$。换言之，$0$ 变为 $1$，$1$ 变为 $0$。

• 2 z：将树的根节点更改为顶点 $z$。若顶点 $z$ 当前已是根节点，则不执行任何操作。

每次查询执行后，特拉与露露均从头开始一局新游戏。对于这 $Q$ 局游戏中的每一局，请判断：若双方均以最优策略进行游戏，谁将获胜？所有查询的影响是累积的。

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

输入从标准输入中按以下格式给出：

$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$

每个查询以以下两种格式之一给出：

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.

对于每次查询之后进行的比赛，若 Terra 获胜则输出 Terra，若 Lulu 获胜则输出 Lulu，每行一个。

表示言語

/ /

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.

表示语言

/ /

限制条件

• $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$
• 所有给定的数均为整数。
• 给定的图是一棵树。