지각하기 싫어

김한양은 3학년이 되었지만 여전히 지각을 자주 한다. 인예본 강의도 두 번 재수강한 끝에 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$번 경로로 가고, 대운동장에서 ITBT관까지 $b$번 경로로 가는 길이 가장 빠른 길이면 $a$와 $b$를 공백으로 구분하여 출력한다. 가장 빠른 길이 여러 개이면 $a$가 가장 작은 경우를 고른다. 그런 길도 여러 개이면 $b$가 가장 작은 경우를 고른다.

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

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

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

넷째 줄에 수행할 연산의 수 $K$($1 \le K \le 200\,000$)가 주어진다. 다섯째 줄부터 $K$개의 줄에 연산이 한 줄에 하나씩 주어진다.

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