题目描述

给定一棵有 $n$ 个顶点的无向树 $T$，顶点编号为 $1,2,\ldots,n$。另有一个整数序列：

你需要依次处理 $q$ 个查询。查询分为两类：修改查询和游戏查询。

修改查询

给定整数 $p_j,r_j$，将：

游戏查询

给定一个整数 $k_j\in\{0,1\}$。

在该查询中，先手和后手按照以下规则进行取石子游戏。双方都采取最优策略，判断最终谁会获胜。

1. 初始时，树上每个顶点 $u$ 放有 $s_u$ 个石子。
2. 从先手开始，双方轮流行动。轮到某位玩家时，他必须选择一个满足以下全部条件的顶点 $v$，并从该顶点取走一个石子：
   • 顶点 $v$ 当前至少有一个石子；
   • 与 $v$ 相邻的所有顶点上的石子数之和，对 $2$ 取模后等于 $k_j$。
3. 如果当前玩家找不到满足条件的顶点，则该玩家失败，另一位玩家获胜，游戏结束。

注意，在判断相邻顶点石子总数时，不包含顶点 $v$ 自身。

每次游戏查询都以当前序列 $(s_1,s_2,\ldots,s_n)$ 为初始状态；游戏过程不会真正修改后续查询所使用的序列。

输入格式

输入包含多组测试数据。

每组测试数据格式如下：

n
a1 b1
...
a(n-1) b(n-1)
s1 s2 ... sn
q
query1
...
queryq

• 第一行输入顶点数 $n$；
• 接下来 $n-1$ 行描述树边，第 $i$ 行的两个整数 $a_i,b_i$ 表示顶点 $a_i$ 与 $b_i$ 相邻；
• 下一行输入 $n$ 个整数 $s_1,s_2,\ldots,s_n$；
• 下一行输入查询数 $q$；
• 接下来 $q$ 行，每行是一条查询。

修改查询格式为：

1 pj rj

游戏查询格式为：

2 kj

输入以仅包含一个整数 0 的行结束。

输出格式

对于每个游戏查询：

• 若先手获胜，输出 First；
• 若后手获胜，输出 Second。

每个答案占一行。

数据范围

对于修改查询：

对于游戏查询：

每组测试数据至少包含一个游戏查询。

所有测试数据中 $n$ 的总和不超过 $3\times 10^5$，$q$ 的总和不超过 $3\times 10^5$。

样例

3
3 1
3 2
6 1 3
4
1 1 9
2 0
1 2 6
2 1
1
8
3
2 0
1 1 3
2 1
0

First
First
Second
Second