Maskpunk 2077

The year is 2077, and the spread of an unending pandemic means every household can make masks at home. Skill varies from person to person, though, so the cost of producing a mask differs from house to house.

In Seogang Village, where $N$ houses sit in order along a straight line, the household in the $i$-th house needs $c_i$ to make a mask, and moving between the $i$-th and $(i+1)$-th houses takes $t_i$ minutes.

The villagers of Seogang call in to ask what the cheapest mask they can get within $m$ minutes costs. Juhyeon, who handles phone duties at the city hall, is having a hard time dealing with these calls, because the ever-changing traffic conditions mean the travel times have to be recalculated on the spot.

Juhyeon has asked you to write a program that computes the answers to the villagers' calls. You do not know how to refuse, so you have no choice but to take the request.

The first line gives $N$, the number of houses in Seogang Village. ($2 \le N \le 100\,000$)

The second line gives the mask production costs $c_1$, $c_2$, $...$, $c_N$ of each household, separated by spaces. ($1 \le c_i \le 10\,000$)

The third line gives the initial travel times $t_1$, $t_2$, $...$, $t_{N-1}$, separated by spaces. ($1 \le t_i \le 10\,000$)

The fourth line gives $Q$, the number of tasks Juhyeon must handle. ($1 \le Q \le 50\,000$)

Each of the next $Q$ lines gives one task, in order, and each is one of the following two types.

• UPDATE $x$ $t$ : set the travel time between the $x$-th and $(x+1)$-th houses to $t$ minutes. ($1 \le x \le N - 1$, $1 \le t \le 10\,000$)
• CALL $x$ $m$ : print the price of the cheapest mask the $x$-th house can obtain within $m$ minutes. ($1 \le x \le N$, $1 \le m \le 1\,000\,000$)

Print the results of the CALL tasks, one per line.