Description

Not long ago, Mirko founded a travel agency called “Polar Dream.” The agency bought $n$ islands near the Arctic and offers sightseeing services.

The most popular attraction is, of course, the emperor penguins. These little fellows often move in groups between the islands. Mirko’s agency suffered a major setback, making cruise tours no longer cost-effective. The agency will build bridges between islands and use sightseeing buses to carry tourists.

Mirko wants to develop a computer program to manage the bridge-building process to avoid unexpected errors. The islands are labeled from $1$ to $n$. Initially, there are no bridges between islands, and the number of emperor penguins on each island is known. Although the number on each island may change, it is always within $[0, 1000]$. Your program must process the following three commands:

• bridge u v: Ask whether nodes $u$ and $v$ are connected. If they are, output no; otherwise output yes, and add an undirected edge between $u$ and $v$.
• penguins u x: Set the weight $w_u$ of node $u$ to $x$.
• excursion u v: If nodes $u$ and $v$ are not connected, output impossible. Otherwise, output the sum of the weights of the nodes on the path from $u$ to $v$.

There are $q$ operations in total.

Input Format

• The first line contains an integer $n$, the number of nodes.
• The second line contains $n$ integers; the $i$-th integer is the initial weight $w_i$ of node $i$.
• The third line contains an integer $q$, the number of operations.
• Each of the next $q$ lines contains one operation as described above.

Output Format

Output the results of all bridge and excursion operations, one answer per line.

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

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

yes
yes
yes
6
impossible
yes
15
13
no

Hint

Constraints
For $100\%$ of the testdata, $1 \le n \le 3 \times 10^4$, $1 \le q \le 3 \times 10^5$, $0 \le w_i \le 1000$.

Translated by ChatGPT 5