금고 털이

GSHS국가의 수도에는 $N$개의 빌딩이 일렬로 놓여 있다. 빌딩은 왼쪽부터 $1, 2, \cdots, N$번까지 번호가 붙어 있고, $i$번 빌딩의 높이는 $H_i$이다. 모든 빌딩의 높이는 서로 다르다. 각 빌딩의 옥상에는 금고가 하나씩 있으며, $i$번 빌딩의 금고에는 $C_i$원이 들어 있다. $H_i$와 $C_i$는 모두 양의 정수이다.

당신은 수도의 금고를 털어 돈을 버는 금고 털이범이다. 임의의 빌딩 옥상에서 출발하여 빌딩 사이를 이동하며 금고를 턴다. 금고 털이를 마치면 조력자가 헬리콥터를 $E$번 빌딩 옥상으로 보내 수도를 빠져나가도록 돕는다. 따라서 마지막으로 도착하는 빌딩은 반드시 $E$번 빌딩이어야 한다. 안전을 위해 다음 규칙을 지켜야 한다.

1. 빌딩 $i$에서 빌딩 $j$로 이동하려면 빌딩 $j$가 빌딩 $i$의 옥상에서 보여야 한다. 빌딩 $i$에서 빌딩 $j$가 보인다는 것은 빌딩 $i$와 $j$ 사이(빌딩 $i$, $j$ 포함)의 모든 빌딩 높이가 빌딩 $j$의 높이보다 같거나 작다는 뜻이다. 그렇지 않으면 다른 빌딩에 가려 보이지 않는다.
2. 이동 과정에서 연속으로 방문한 두 빌딩의 금고는 최대 하나만 털 수 있다.
3. 방문한 빌딩마다 얻는 수익은 금고를 털었다면 $C_i$, 털지 않았다면 0이다. 총 수익은 방문한 모든 빌딩의 수익을 합한 값이다.

빌딩의 높이는 확실하지만 금고의 가치는 바뀔 수 있고, 조력자가 도착할 빌딩 번호 $E$도 바뀔 수 있다. 정보가 $Q$번 갱신될 때마다, 위 조건을 지키면서 얻을 수 있는 최대 수익을 구하시오.

첫 줄에 두 정수 $N$, $E$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 정수 $H_1, H_2, \cdots, H_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 $N$개의 정수 $C_1, C_2, \cdots, C_N$이 공백으로 구분되어 주어진다.

네 번째 줄에 정수 $Q$가 주어진다.

다섯 번째 줄부터 $Q$줄에 걸쳐 다음 형식의 갱신이 주어진다.

• 1 i c: $i$번 빌딩 금고의 가치가 $c$원으로 바뀐다.
• 2 e: 조력자의 도착 위치 $E$가 $e$로 바뀐다.

$Q+1$줄을 출력한다. 첫 줄에는 초기 상태에서 얻을 수 있는 최대 수익을, $i+1$번째 줄에는 처음부터 $i$번째 갱신까지 적용했을 때 얻을 수 있는 최대 수익을 출력한다 ($1 \le i \le Q$).

• $1 \le N \le 10^5$
• $1 \le E \le N$
• $1 \le H_i \le N$, $H_i$는 서로 다르다.
• $1 \le C_i \le 10^9$
• $0 \le Q \le 10^5$

금고 털이를 시작하는 빌딩과 $E$가 같아도 된다.