남극 탐험

한 여행사는 남극 근처에 있는 섬 N개를 당일치기 여행지로 운영한다. 각 섬에는 황제펭귄이 살고 있으며, 여행사는 섬 사이에 다리를 지어 관광객을 버스로 이동시키려 한다.

섬에는 1번부터 N번까지 번호가 붙어 있다. 처음에는 다리가 하나도 없고, 각 섬에 사는 펭귄 수가 주어진다. 펭귄 수는 명령에 따라 바뀔 수 있으며 항상 0 이상 1000 이하이다.

프로그램은 다음 세 가지 명령을 처리해야 한다.

• bridge A B: 섬 A와 B 사이에 다리를 짓는다. 이미 지어진 다리들만 이용해서 A에서 B로 갈 수 없다면 다리를 짓고 yes를 출력한다. 이미 갈 수 있다면 새 다리를 지을 필요가 없으므로 no를 출력한다. A와 B는 서로 다르다.
• penguins A X: 섬 A의 펭귄 수가 X마리로 바뀐다. 이 명령은 아무것도 출력하지 않는다.
• excursion A B: 관광객이 섬 A에서 출발해 섬 B에서 끝나는 경로로 이동한다. 두 섬 사이를 이동할 수 있다면 경로에 포함되는 모든 섬의 펭귄 수 합을 출력한다. A와 B도 합에 포함한다. 이동할 수 없다면 impossible을 출력한다.

모든 명령을 순서대로 처리하는 프로그램을 작성하시오.

첫째 줄에 섬의 수 N이 주어진다. (1 <= N <= 30000)

둘째 줄에는 1번 섬부터 N번 섬까지 각 섬의 펭귄 수가 순서대로 주어진다.

셋째 줄에는 명령의 개수 Q가 주어진다. (1 <= Q <= 300000)

다음 Q개 줄에는 bridge A B, penguins A X, excursion A B 중 하나가 주어진다.

bridge 명령과 excursion 명령이 주어질 때마다 문제에서 요구한 값을 한 줄에 하나씩 출력한다.