Problem Description

Recently, Mirko established a travel agency named "Polar Dream." This agency purchased $n$ ice islands near the North Pole and offers sightseeing services.

The most popular attractions are the emperor penguins, which often roam between the islands in groups. Mirko's agency faced a significant setback, making cruise tours unprofitable. Therefore, the agency plans to build bridges between the islands and use sightseeing buses to transport tourists.

Mirko wants to develop a computer program to manage the construction of these bridges to avoid unforeseen errors. The islands are numbered from 1 to $N$. Initially, there are no bridges connecting the islands, and the number of penguins on each island is known. The number of penguins on each island may change but will always be within the range $[0, 1000]$. Your program needs to handle the following three types of commands:

• bridge u v: Query whether nodes $u$ and $v$ are connected. If they are, output no; otherwise, output yes and connect nodes $u$ and $v$ with an undirected edge.
• penguins u x: Change 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, where the $i$-th integer represents the initial weight $w_i$ of the $i$-th node.

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

The following $q$ lines each contain an operation as described in the problem statement.

Output Format

Output the results for all bridge and excursion operations, each on a new line.

Sample Input and Output

Input Sample #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

Output Sample #1

4
impossible
yes
6
yes
yes
15
yes
15
16

Input Sample #2

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

Output Sample #2

yes
yes
yes
6
impossible
yes
15
13
no

Notes

Data Range

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

见题面 Input 部分

见题面 Output 部分