不久之前，Mirko建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了N座冰岛，并且提供观光服务。当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。Mirko的旅行社遭受一次重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。Mirko希望开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。这些冰岛从1到N标号。一开始时这些岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在[0, 1000]之间。你的程序需要处理以下三种命令：

1."bridge A B"——在A与B之间建立一座大桥（A与B是不同的岛屿）。由于经费限制，这项命令被接受，当且仅当A与B不联通。若这项命令被接受，你的程序需要输出"yes"，之后会建造这座大桥。否则，你的程序需要输出"no"。

2."penguins A X"——根据可靠消息，岛屿A此时的帝企鹅数量变为X。这项命令只是用来提供信息的，你的程序不需要回应。

3."excursion A B"——一个旅行团希望从A出发到B。若A与B连通，你的程序需要输出这个旅行团一路上所能看到的帝企鹅数量（包括起点A与终点B），若不联通，你的程序需要输出"impossible"。

第一行一个正整数N，表示冰岛的数量。

第二行N个范围[0, 1000]的整数，为每座岛屿初始的帝企鹅数量。

第三行一个正整数M，表示命令的数量。接下来M行即命令，为题目描述所示。

1<=N<=30000,1<=M<=100000

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 30010

using namespace std;

int fa[N] , c[2][N] , w[N] , sum[N] , rev[N];

char str[15];

void pushup(int x)

{

	sum[x] = sum[c[0][x]] + sum[c[1][x]] + w[x];

}

void pushdown(int x)

{

	if(rev[x])

	{

		int l = c[0][x] , r = c[1][x];

		swap(c[0][l] , c[1][l]) , swap(c[0][r] , c[1][r]);

		rev[l] ^= 1 , rev[r] ^= 1 , rev[x] = 0;

	}

}

bool isroot(int x)

{

	return c[0][fa[x]] != x && c[1][fa[x]] != x;

}

void update(int x)

{

	if(!isroot(x)) update(fa[x]);

	pushdown(x);

}

void rotate(int x)

{

	int y = fa[x] , z = fa[y] , l = (c[1][y] == x) , r = l ^ 1;

	if(!isroot(y)) c[c[1][z] == y][z] = x;

	fa[x] = z , fa[y] = x , fa[c[r][x]] = y , c[l][y] = c[r][x] , c[r][x] = y;

	pushup(y) , pushup(x);

}

void splay(int x)

{

	update(x);

	while(!isroot(x))

	{

		int y = fa[x] , z = fa[y];

		if(!isroot(y)) rotate((c[0][y] == x) ^ (c[0][z] == y) ? x : y);

		rotate(x);

	}

}

void access(int x)

{

	int t = 0;

	while(x) splay(x) , c[1][x] = t , pushup(x) , t = x , x = fa[x];

}

int find(int x)

{

	access(x) , splay(x);

	while(c[0][x]) pushdown(x) , x = c[0][x];

	return x;

}

void makeroot(int x)

{

	access(x) , splay(x) , swap(c[0][x] , c[1][x]) , rev[x] ^= 1;

}

void link(int x , int y)

{

	makeroot(x) , fa[x] = y;

}

int main()

{

	int n , i , m , x , y;

	scanf("%d" , &n);

	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &w[i]) , sum[i] = w[i];

	scanf("%d" , &m);

	while(m -- )

	{

		scanf("%s%d%d" , str , &x , &y);

		if(str[0] == 'b')

		{

			if(find(x) == find(y)) puts("no");

			else puts("yes") , link(x , y);

		}

		else if(str[0] == 'p') splay(x) , w[x] = y , pushup(x);

		else

		{

			if(find(x) != find(y)) puts("impossible");

			else makeroot(x) , access(y) , splay(y) , printf("%d\n" , sum[y]);

		}

	}

	return 0;

}