Real-Time Navigation

Dijkstra's algorithm made it easy to find routes. However, drivers kept using the same few roads, so traffic jams got worse. The Korean Expressway Corporation then edited the travel time data for some roads so that the navigation system would recommend other routes. Soon, other roads started to jam.

As new roads kept getting congested, the Korean Expressway Corporation changed the road data more and more often. However, Dijkstra's algorithm performs $O(E \log V)$ operations every time the road data changes, and the navigation server went down.

After this serious problem, the navigation company began writing new software that quickly finds the shortest path whenever road data changes. First, the company will model only the Gangbyeon Expressway and the Olympic Expressway sections, which have the highest demand, and find shortest paths there.

The Gangbyeon Expressway runs on the north side of the Han River, and the Olympic Expressway runs on the south side. Each road has $N$ junctions. The junctions on the Gangbyeon Expressway are coded N-1, N-2, ..., N-N from the westernmost one in order. The junctions on the Olympic Expressway are coded S-1, S-2, ..., S-N from the westernmost one in order. Road $i$ on the Gangbyeon Expressway connects junctions N-i and N-(i+1). Road $i$ on the Olympic Expressway connects junctions S-i and S-(i+1). Bridge $i$ across the Han River connects junctions N-i and S-i. Each road and bridge takes a fixed amount of time to cross.

The navigation server initially has the travel time data for $3N-2$ roads. After that, it receives messages from the Korean Expressway Corporation saying that the travel time of a specific road has changed. Whenever a driver asks for the fastest way from one place to another, the server must quickly compute the answer and send it back. Write a program that handles these two kinds of queries quickly. Note that a route that crosses the bridges several times can also be an answer.

The first line contains the number of bridges $N$. ($2 \le N \le 300,000$)

The second line contains the travel times $N_i$ for the $N-1$ roads on the Gangbyeon Expressway, in order from the west. ($1 \le N_i \le 1,000,000,000$)

The third line contains the travel times $S_i$ for the $N-1$ roads on the Olympic Expressway, in order from the west. ($1 \le S_i \le 1,000,000,000$)

The fourth line contains the travel times $B_i$ for the $N$ bridges across the Han River, in order from the west. ($1 \le B_i \le 1,000,000,000$)

The fifth line contains the number of queries $Q$. ($1 \le Q \le 300,000$)

The next $Q$ lines each contain one query in one of the following formats.

• 1 a b: Find the minimum time needed to go from junction $a$ to junction $b$. $a$ and $b$ are different. Junction $x$ on the Gangbyeon Expressway is written Nx, and junction $x$ on the Olympic Expressway is written Sx.
• 2 a Na: The travel time of road $a$ on the Gangbyeon Expressway changes to $N_a$. ($1 \le a \le N-1$, $1 \le N_a \le 1,000,000,000$)
• 3 b Sb: The travel time of road $b$ on the Olympic Expressway changes to $S_b$. ($1 \le b \le N-1$, $1 \le S_b \le 1,000,000,000$)
• 4 c Bc: The travel time of bridge $c$ across the Han River changes to $B_c$. ($1 \le c \le N$, $1 \le B_c \le 1,000,000,000$)

For each query of type 1, print the answer on its own line. At least one query of type 1 is guaranteed to appear.