Hide

Problem A
Winter Roads

Winter is coming, and the citizens of Winterfell are making preparations for the long months ahead. One particular concern is the stability of the roads and bridges; supply lines must stay uninterrupted as the season progresses.

The civil engineers of Winterfell would like to model possible scenarios of roads failing and repairs that need to be made. In their model, each road connects two landmarks in the city. Each road can be traveled in either direction, and has a certain carrying capacity. Trucks travel from landmark to landmark, and can only travel on sufficiently sturdy roads. In particular, a supply truck with weight $w$ can travel on a road with capacity $c$ iff $w \le c$. Whether by nature or by accident, the capacity of a road can decrease over time. In addition, repairs can increase the carrying capacity of a road. While roads change, however, supply trucks still need to be able to get from source to destination, and the engineers would like to test whether trucks can still make certain runs between landmarks.

Given a series of changes to the roads and some supply truck runs, help the engineers check whether or not supplies can still be delivered as winter strikes.

Input

There will be a single test case in the input. This test case will begin with a line with two integers $n$, $m$ ($1 \le n \le 1\, 000$, $1 \le m \le 100\, 000$), where $n$ is the number of landmarks, and $m$ is the number of roads between them. This will be followed by $m$ lines, each with three integers $a$, $b$, and $c$ ($1 \le a,b \le n$ and $1 \le c \le 1\, 000\, 000\, 000$) representing a road between landmarks $a$ and $b$ with carrying capacity $c$. Roads are numbered $1, 2, 3, \ldots , m$ in the order that they appear in the input.

Next will be a line with a single integer $e$ ($1 \le e \le 100\, 000$), indicating the number of events. This will be followed by $e$ lines, consisting of a capital letter followed by integers:

  • B r c: Indicates that road $r$ breaks down. Its carrying capacity decreases to $c$. ($1 \le r \le m$, $1 \le c < 1\, 000\, 000\, 000$)

  • R r c: Indicates that road $r$ is repaired. Its carrying capacity increases to $c$. ($1 \le r \le m$, $1 < c \le 1\, 000\, 000\, 000$)

  • S a b w: Check whether or not a supply truck with weight $w$ can travel from landmark $a$ to landmark $b$. ($1 \le a,b \le n$, $1 \le w \le 1\, 000\, 000\, 000$)

Only capital letters B, R or S will appear. All events occur in the order given in the input. There will be at most $2\, 000$ breakdown / repair events in the input.

Output

For each S a b w query, in order, output 1 if there is a path from $a$ to $b$ that can support a truck of weight $w$, and 0 if there is not. Output each number on its own line.

Sample Input 1 Sample Output 1
3 4
1 2 3
2 3 3
2 1 1
1 2 1
6
S 1 2 4
S 2 3 2
R 1 4
S 1 2 4
B 2 1
S 2 3 2
0
1
1
0

Please log in to submit a solution to this problem

Log in