The Polar Dream: Bridge Building and Penguin Excursions

Mirko recently founded a travel agency called "The Polar Dream" near the Arctic. The agency purchased n islands (numbered from 1 to n) and originally each island has a known number of penguins (in the range \([0, 1000]\)). Initially, there are no bridges connecting any two islands.

The agency now plans to build bridges between islands and use sightseeing buses to transport visitors. However, the penguins roam freely across the islands, and their numbers may change over time. Your task is to develop a program that processes q operations to manage the building of bridges and the excursions, while updating penguin counts as needed.

The operations are as follows:

• bridge u v: Check if islands u and v are already connected (directly or indirectly). If u and v are connected, print no. Otherwise, print yes and build an undirected bridge between island u and island v.
• penguins u x: Update the number of penguins on island u to x (with \(0 \le x \le 1000\)).
• excursion u v: If islands u and v are not connected, print impossible. Otherwise, find the unique path between u and v (since bridges are only built when the islands are in separate components) and output the sum of the penguin counts on all islands along this path.

You are guaranteed that the commands are provided sequentially. Initially, the islands are disconnected; bridges are added only if the two islands are not already in the same connected component. The sum along a valid excursion should always represent the current penguin counts updated via the penguins command.

Note: When using mathematical formulas in your description, ensure that they are in LaTeX format (e.g. \(a+b\)).

inputFormat

The first line contains a single integer n indicating the number of islands.

The second line contains n integers \(w_1, w_2, \dots, w_n\) representing the initial penguin count on each island, where \(0 \le w_i \le 1000\).

The third line contains an integer q denoting the number of operations.

Each of the following q lines contains one of the following commands:

• bridge u v
• penguins u x
• excursion u v

The commands are processed in the order they are given.

outputFormat

For each command that produces an output (bridge and excursion), print the result on a new line. For bridge, output either yes or no. For excursion, output the sum of penguins along the unique path if possible; otherwise, print impossible.

sample

4
5 10 15 20
7
excursion 1 2
bridge 1 2
excursion 1 2
bridge 2 3
excursion 1 3
penguins 2 7
excursion 1 3

impossible
yes
15
yes
30
27

</p>