16686번 - 실시간 내비게이션 서브태스크

우리는 dijkstra가 고안한 알고리즘 덕분에 길을 쉽게 찾을 수 있지만, 그러다 보니 사람들은 몇몇 도로만 드나들게 되어 교통체증이 심해졌습니다. 이에 따라 한국도로공사는 도로의 통행시간 정보를 수정하여 내비게이션이 다른 경로를 추천하도록 하였습니다. 그러자 다른 도로들이 새롭게 막히기 시작했습니다.

새로운 도로들이 계속 막히다 보니 한국도로공사는 도로 정보를 더욱 자주 바꾸기 시작했습니다. 허나, dijkstra의 알고리즘은 도로 정보를 바꿀 때마다 O(E logV) 만큼 연산을 수행하기에 내비게이션 서버가 다운이 되어버렸습니다.

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

한강 북쪽에 강변북로, 남쪽에 올림픽대로가 있으며 강변북로와 올림픽대로에 각각 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 ≤ N ≤ 300,000)

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

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

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

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

여섯 번째 줄부터 Q 개의 줄에는 아래와 같은 형식으로 쿼리가 주어집니다.

• 1 a b : a 번 나들목에서 b 번 나들목까지 가는데 걸리는 최소 시간을 구해라. a 와 b 는 서로 다르며, 강변북로 x 번째 나들목은 Nx 꼴로, 올림픽대로 x 번째 나들목은 Sx 꼴로 주어진다.
• 2 a N_a : 강변북로 a 번째 도로를 지나는데 걸리는 시간이 N_a 로 바뀐다. (1 ≤ a ≤ N-1, 1 ≤ N_a ≤ 1,000,000,000)
• 3 b S_b : 올림픽대로 b 번째 도로를 지나는데 걸리는 시간이 S_b 로 바뀐다. (1 ≤ b ≤ N-1, 1 ≤ S_b ≤ 1,000,000,000)
• 4 c B_c : 한강에 있는 c 번째 다리를 지나는데 걸리는 시간이 B_c 로 바뀐다. (1 ≤ c ≤ N, 1 ≤ B_c ≤ 1,000,000,000)

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

N, Q ≤ 3,000을 만족한다.

문제 입력에서 주어진 조건 외에 추가적인 조건이 없다.