I Don't Want to Be Late

Interview

Time limit1sMemory limit1024 MB

Summary

Given route populations under point updates, report the first and second route numbers of a fastest Aeji Hall to ITBT path, breaking ties by smallest index.

Level: Medium4 of 10
Topics: Segment tree, Array
Solved: No attempts yet

Problem

Kim Hanyang became a third-year student, but he is still late all the time. He even had to retake a course twice in order to get a P in the Inyebon lecture. Tired of being late, Kim Hanyang wants to write a program that finds the fastest route from Aeji Hall to the ITBT building and keeps updating it.

To get from Aeji Hall to the ITBT building, you must pass through the Grand Playground. There are $N$ routes from Aeji Hall to the Grand Playground, numbered 1 to $N$ . There are $M$ routes from the Grand Playground to the ITBT building, numbered $N+1$ to $N+M$ . The population on each route changes over time, and the time it takes to cross a route is proportional to its population. Given the population changes, write a program that performs the following two operations.

U $x$ $y$ : Changes the population of route $x$ to $y$ . ( $1 \le x \le N+M$ , $1 \le y \le 100$ )
L: Suppose the fastest path from Aeji Hall to the ITBT building goes through route $a$ to the Grand Playground and then through route $b$ to the ITBT building. Print $a$ and $b$ separated by a space. If several fastest paths exist, print the one with the smallest $a$ . If several fastest paths with the smallest $a$ exist, print the one with the smallest $b$ .

Input

The first line contains $N$ ( $1 \le N \le 100\,000$ ) and $M$ ( $1 \le M \le 100\,000$ ), separated by a space. $N$ is the number of routes from Aeji Hall to the Grand Playground, and $M$ is the number of routes from the Grand Playground to the ITBT building.

The second line contains the initial populations of the $N$ routes from Aeji Hall to the Grand Playground, separated by spaces.

The third line contains the initial populations of the $M$ routes from the Grand Playground to the ITBT building, separated by spaces.

The fourth line contains the number of operations $K$ ( $1 \le K \le 200\,000$ ). The following $K$ lines each contain one operation.

Output

For each L operation, print the result on its own line.

Examples4

Example 1

Input

7 6
13 92 51 97 27 93 74
67 58 93 78 94 41
5
U 11 2
L
U 1 7
L
U 6 13

Expected output

1 11
1 11

Example 2

Input

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
10
U 1 2
L
U 3 1
L
U 15 10
L
U 11 10
L
U 13 10
L

Expected output

Example 3

Input

Expected output

Example 4

Input

5 4
5 46 31 38 85
80 27 17 45
10
U 7 1
L
U 9 5
L
U 7 3
L
U 5 3
L
U 8 5
L

Expected output