29811번 - 지각하기 싫어

문제

3학년이 된 김한양은 정말 지각을 자주 하는 학생이다. 그 꿀강이라는 인예본 강의도 2번의 재수강 끝에 P를 받았다. 더 이상 지각하기 싫었던 김한양은 애지문부터 ITBT관으로 이동할 때 가장 빠르게 이동하는 경로를 찾고, 업데이트하는 프로그램을 만드려고 한다.

애지문에서 ITBT관으로 가기 위해서는 대운동장을 반드시 지나가야 한다. 애지문부터 대운동장까지 가는 경로는 총 $N$개이며, 1ドル$부터 $N$까지 차례대로 번호가 붙어 있다. 대운동장부터 ITBT관까지 가는 경로는 총 $M$개이며, $N+1$부터 $N+M$까지 차례대로 번호가 붙어 있다. 각 경로의 인구는 유동적이며, 어떤 경로를 지나는 시간은 해당 경로의 인구와 비례한다. 각 경로의 인구 변화가 주어질 때, 김한양을 도와 가장 빠른 경로를 찾아주자. 구체적으로, 다음 두 연산을 수행하는 프로그램을 작성해야 한다.

• U $x$ $y$: $x$번 경로의 인구를 $y$로 바꾼다. $(1 \le x \le N+M;$ 1ドル \le y \le 100)$
• L: $a$번 경로를 통해 애지문에서 대운동장으로 간 뒤 $b$번 경로를 통해 대운동장에서 ITBT관으로 가는 길이 애지문에서 ITBT관으로 가는 가장 빠른 길일 때, $a$와 $b$를 공백으로 구분하여 출력한다. 가장 빠른 길이 여러 가지라면 그 중 $a$가 가장 작은 경우를, 가장 빠르면서 $a$가 가장 작은 경로도 여러 가지라면 그 중 $b$가 가장 작은 경우를 출력한다.

입력

첫 줄에 애지문에서 대운동장까지의 경로 수 $N(1 \leq N \leq 100,000円)$과 대운동장에서 ITBT관까지의 경로 수 $M(1 \leq M \leq 100,000円)$이 공백으로 구분되어 주어진다.

둘째 줄에 애지문에서 대운동장까지의 $N$개 경로의 초기 인구가 공백으로 구분되어 주어진다.

셋째 줄에 대운동장에서 ITBT관까지의 $M$개 경로의 초기 인구가 공백으로 구분되어 주어진다.

넷째 줄에 수행할 연산의 수 $K(1 \leq K \leq 200,000円)$가 주어진다.

다섯째 줄부터 $K$개의 줄에는 수행할 연산이 한 줄에 하나씩 주어진다.

출력

L 연산의 결과를 한 줄에 하나씩 출력한다.

제한

힌트