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

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

세 번째 줄에는 올림픽대로에 있는 N-1개의 길을 지나는데 걸리는 시간 O_i 가 서쪽 도로부터 순서대로 주어진다. (1 \le O_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개의 줄에는 아래 4가지 중 하나의 형식으로 추가 정보 또는 질문이 시간 순으로 주어진다.

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

1번 유형의 질문은 최소 한 번 이상 등장한다.

실시간 교통 정보 timer 3s memory 1024MB

실시간 교통 정보 3s 1024MB