Vault Robbery

The capital of GSHS country has $N$ buildings in a row, numbered $1, 2, \cdots, N$ from left to right. The height of building $i$ is $H_i$, and all building heights are distinct. Each building has a vault on its roof, and the vault in building $i$ holds $C_i$ won. $H_i$ and $C_i$ are positive integers.

You are a thief who robs the vaults of the capital. You start on the roof of any building and move between buildings while robbing vaults. After the robbery, your helper sends a helicopter to the roof of building $E$ to take you out of the city. So the last building you reach must be building $E$. For safety, you must follow these rules.

1. To move from building $i$ to building $j$, building $j$ must be visible from the roof of building $i$. Building $j$ is visible from building $i$ if every building between them (including buildings $i$ and $j$) has height at most the height of building $j$. Otherwise, another building blocks the view.
2. While moving, you may rob at most one of any two consecutively visited buildings.
3. For each visited building, your gain is $C_i$ if you rob it and 0 otherwise. The total gain is the sum of the gains over all visited buildings.

The building heights are fixed, but the vault values can change, and the helper's destination building $E$ can also change. Each time the information is updated, compute the maximum total gain you can earn under the rules above.

The first line contains two integers $N$ and $E$, separated by a space.

The second line contains $N$ integers $H_1, H_2, \cdots, H_N$, separated by spaces.

The third line contains $N$ integers $C_1, C_2, \cdots, C_N$, separated by spaces.

The fourth line contains an integer $Q$.

Each of the next $Q$ lines is one of the following updates.

• 1 i c: the vault value in building $i$ changes to $c$ won.
• 2 e: the helper's destination $E$ changes to $e$.

Print $Q+1$ lines. The first line contains the maximum gain for the initial state. Line $i+1$ contains the maximum gain after applying the first $i$ updates ($1 \le i \le Q$).

• $1 \le N \le 10^5$
• $1 \le E \le N$
• $1 \le H_i \le N$, and the $H_i$ are distinct.
• $1 \le C_i \le 10^9$
• $0 \le Q \le 10^5$

You may start at the same building as $E$.