[CROATIAN2009]OTOCI

给出 $n$ 个结点以及每个点初始时对应的权值 $w_i$。起始时点与点之间没有连边。有 $3$ 类操作：

1. bridge A B：询问结点 $A$ 与结点 $B$ 是否连通。如果是则输出 no；否则输出 yes，并且在结点 $A$ 和结点 $B$ 之间连一条无向边。
2. penguins A X：将结点 $A$ 对应的权值 $w_A$ 修改为 $X$。
3. excursion A B：如果结点 $A$ 和结点 $B$ 不连通，则输出 impossible；否则输出结点 $A$ 到结点 $B$ 的路径上的点对应的权值的和。

给出 $q$ 个操作，要求在线处理所有操作。

输入格式

第一行包含一个整数 $n$，表示结点的数目。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个结点初始时对应的权值。

第三行包含一个整数 $q$，表示操作的数目。

以下 $q$ 行，每行包含一个操作，操作的类别见题目描述。

输出格式

输出所有 bridge 操作和 excursion 操作对应的输出，每个一行。

样例输入

5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5

样例输出

4
impossible
yes
6
yes
yes
15
yes
15
16

数据范围

• $1\le n\le 3\times 10^4$；
• $1\le q\le 3\times 10^5$；
• $0\le w_i\le 1000$，且任意时刻每个结点对应的权值都是 $1$ 到 $1000$ 的整数。

来源与许可

本题为 CROATIAN 2009 试题「OTOCI」，题面与测试数据整理自 BZOJ 1180。

样例 1

输入

5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5

输出

4
impossible
yes
6
yes
yes
15
yes
15
16