시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 54 32 32 65.306%

문제

때는 2077년, 끝나지 않는 전염병의 확산으로 모든 가정에서 가내수공업으로 마스크를 만들 수 있게 된다. 하지만 개개인의 기술력에 차이가 있어서, 마스크의 생산 비용이 집마다 달랐다.

$N$개의 집이 직선상에 순서대로 놓여 있는 서강 마을에서, $i$번째 집의 가정은 마스크를 만드는데 $c_i$만큼의 비용이 필요하며, $i$번째 집과 $i+1$번째 집 사이를 이동할 때 $t_i$분의 시간이 걸린다.

서강 마을의 주민들은 자신들이 $m$분 이내에 얻을 수 있는 가장 싼 마스크가 얼마인지에 대해 문의 전화를 걸곤 한다. 시청에서 전화 업무를 담당하고 있는 주현이는 이 문의 전화들에 대응하는 것에 골머리를 앓고 있다. 왜냐하면, 유동적으로 변하는 도로 교통 상황으로 인해서 이동 시간을 그때그때 계산해야 하기 때문이다!

주현이는 당신에게 주민들의 문의 전화에 대한 답변을 계산해주는 프로그램을 제작해달라고 부탁했다. 거절하는 법을 모르는 당신은 이 부탁을 들어줄 수밖에 없다!

입력

첫째 줄에 서강 마을에 있는 집의 개수인 $N$이 주어진다. ($2 \le N \le 100\,000$)

둘째 줄에 각 가정의 마스크 생산 비용인 $c_1$, $c_2$, $...$, $c_N$이 공백으로 구분되어 주어진다. ($1 \le c_i \le 10\,000$)

셋째 줄에 초기 이동 시간 $t_1$, $t_2$, $...$, $t_{N-1}$이 공백으로 구분되어 주어진다. ($1 \le t_i \le 10\,000$)

넷째 줄에 주현이가 해야할 업무의 개수 $Q$가 주어진다. ($1 \le Q \le 50\,000$)

다섯째 줄부터 $Q$개의 줄에 걸쳐, 다음 두 가지 유형 중 하나의 업무가 한 줄에 하나씩 순서대로 주어진다.

  • UPDATE $x$ $t$ : $x$번째 집과 $x+1$번째 집 사이의 이동 시간을 $t$분으로 갱신한다. ($1 \le x \le N - 1$, $1 \le t \le 10\,000$)
  • CALL $x$ $m$ : $x$번째 집이 $m$분 이내에 얻을 수 있는 가장 싼 마스크의 가격을 출력한다. ($1 \le x \le N$, $1 \le m \le 1\,000\,000$)

출력

CALL 업무에 대한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

5
10 17 8 2 16
2 5 10 6
5
CALL 2 4
CALL 2 5
UPDATE 2 20
CALL 2 18
CALL 2 30

예제 출력 1

10
8
10
2