실시간 내비게이션

다익스트라(dijkstra)가 고안한 알고리즘 덕분에 길을 쉽게 찾을 수 있게 되었습니다. 그러나 사람들이 몇몇 도로에만 몰리면서 교통체증이 심해졌습니다. 이에 한국도로공사는 내비게이션이 다른 경로를 추천하도록 일부 도로의 통행시간 정보를 수정했습니다. 그러자 이번에는 다른 도로들이 막히기 시작했습니다.

새로운 도로들이 계속 막히자 한국도로공사는 도로 정보를 더 자주 바꾸기 시작했습니다. 하지만 다익스트라 알고리즘은 도로 정보가 바뀔 때마다 $O(E \log V)$ 만큼의 연산을 수행하므로, 내비게이션 서버가 다운되고 말았습니다.

큰 문제가 생기자 내비게이션 회사는 도로 정보가 바뀔 때 최단경로를 빠르게 구해 주는 소프트웨어를 새로 만들기 시작했습니다. 회사는 우선 수요가 많은 강변북로와 올림픽대로 구간만 모델링해서 최단경로를 구하려고 합니다.

한강 북쪽에는 강변북로, 남쪽에는 올림픽대로가 있으며, 각각 $N$개의 나들목이 있습니다. 강변북로의 나들목 코드는 가장 서쪽에 있는 것부터 순서대로 N-1, N-2, ..., N-N입니다. 올림픽대로의 나들목 코드는 서쪽부터 순서대로 S-1, S-2, ..., S-N입니다. 강변북로의 $i$번째 도로는 N-i번 나들목과 N-(i+1)번 나들목을 잇고, 올림픽대로의 $i$번째 도로는 S-i번 나들목과 S-(i+1)번 나들목을 잇습니다. 한강의 $i$번째 다리는 N-i번 나들목과 S-i번 나들목을 잇습니다. 각 도로와 다리를 지나는 데는 일정한 시간이 걸립니다.

내비게이션 서버는 처음에 $3N-2$개 도로의 통행시간 정보를 갖고 있습니다. 이후 한국도로공사 서버로부터 "특정 도로의 통행시간이 바뀌었다"는 정보를 받습니다. 서버는 운전자가 "여기에서 저기까지 가는 가장 빠른 길을 알려 달라"고 물을 때마다 재빨리 답을 구해 보내야 합니다. 두 종류의 쿼리를 빠르게 처리하는 프로그램을 작성하세요. 단, 다리를 여러 번 건너는 경로도 답이 될 수 있습니다.

첫 번째 줄에 다리의 수 $N$이 주어집니다. ($2 \le N \le 300,000$)

두 번째 줄에는 강변북로의 $N-1$개 도로를 지나는 데 걸리는 시간 $N_i$가 서쪽 도로부터 순서대로 주어집니다. ($1 \le N_i \le 1,000,000,000$)

세 번째 줄에는 올림픽대로의 $N-1$개 도로를 지나는 데 걸리는 시간 $S_i$가 서쪽 도로부터 순서대로 주어집니다. ($1 \le S_i \le 1,000,000,000$)

네 번째 줄에는 한강의 $N$개 다리를 지나는 데 걸리는 시간 $B_i$가 서쪽 다리부터 순서대로 주어집니다. ($1 \le B_i \le 1,000,000,000$)

다섯 번째 줄에는 쿼리의 수 $Q$가 주어집니다. ($1 \le Q \le 300,000$)

여섯 번째 줄부터 $Q$개의 줄에 쿼리가 다음 형식으로 주어집니다.

• 1 a b: 나들목 $a$에서 나들목 $b$까지 가는 데 걸리는 최소 시간을 구합니다. $a$와 $b$는 서로 다릅니다. 강변북로의 $x$번째 나들목은 Nx, 올림픽대로의 $x$번째 나들목은 Sx 꼴로 주어집니다.
• 2 a Na: 강변북로의 $a$번째 도로를 지나는 데 걸리는 시간이 $N_a$로 바뀝니다. ($1 \le a \le N-1$, $1 \le N_a \le 1,000,000,000$)
• 3 b Sb: 올림픽대로의 $b$번째 도로를 지나는 데 걸리는 시간이 $S_b$로 바뀝니다. ($1 \le b \le N-1$, $1 \le S_b \le 1,000,000,000$)
• 4 c Bc: 한강의 $c$번째 다리를 지나는 데 걸리는 시간이 $B_c$로 바뀝니다. ($1 \le c \le N$, $1 \le B_c \le 1,000,000,000$)

1번 쿼리마다 답을 한 줄에 하나씩 출력합니다. 1번 쿼리가 적어도 한 번 나오는 것은 보장됩니다.