Antarctic Expedition

Time limit5sMemory limit128 MB

Summary
Process bridge, penguin-update, and route-sum queries on an incrementally connected forest, requiring dynamic connectivity checks and path-sum queries under updates.
Level

Hard8 of 10

Topics
Union-find, Tree, Segment tree, Graph
Solved
No attempts yet

Problem

A travel company operates N islands near Antarctica as one-day tour destinations. Emperor penguins live on the islands, and the company wants to build bridges between islands so tourists can travel by bus.

The islands are numbered from 1 to N. Initially there are no bridges. The number of penguins on every island is known, but it may change after commands. The number is always between 0 and 1000, inclusive.

Your program must process three kinds of commands.

  • bridge A B: Build a bridge between islands A and B. If A and B are not already reachable using existing bridges, build the bridge and print yes. If they are already reachable, no new bridge is needed, so print no. The two islands are distinct.
  • penguins A X: The number of penguins on island A changes to X. This command prints nothing.
  • excursion A B: Tourists take a route that starts on island A and ends on island B. If the two islands are connected, print the total number of penguins on every island along the route, including A and B. If they are not connected, print impossible.

Write a program that processes all commands in order.

Input

The first line contains the number of islands N. (1 <= N <= 30000)

The second line contains the number of penguins on islands 1 through N, in order.

The third line contains the number of commands Q. (1 <= Q <= 300000)

Each of the next Q lines contains one command: bridge A B, penguins A X, or excursion A B.

Output

For each bridge command and each excursion command, print the required result on its own line.

Examples2

  1. Example 1

    Input
    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
    Expected output
    4
impossible
yes
6
yes
yes
15
yes
15
16

  2. Example 2

    Input
    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
    Expected output
    yes
yes
yes
6
impossible
yes
15
13
no