Bfs

Kids from 402 heard the bell and ran outside to play. A tall pole stood in the middle of the field, so they came up with this game. At first the kids split into a group of $m$ girls and a group of $n$ boys, then they took positions somewhere on the field.

The pole starts completely vertical, with tilt $0$. Each player has a force: $B_i$ is the force of the $i$-th boy and $F_i$ is the force of the $i$-th girl. The game runs step by step. At each step, either the boy or the girl closest to the pole (the one with the smallest index) throws a ball at the pole, then leaves the game. A boy's throw tilts the pole to the right, and a girl's throw tilts it to the left. Each throw changes the tilt by the thrower's force.

To keep the game from ending in disaster, the tilt of the pole must never exceed $S$ in either direction. The kids want to know whether some order of throws keeps the tilt within this limit.

The teacher picks $Q$ moments and swaps the order of two consecutive boys or two consecutive girls. The swaps are permanent. After each swap, decide whether a valid order of throws exists.

The first line contains three integers $n$, $m$, and $S$.

The second line contains $n$ integers, the forces of the boys.

The third line contains $m$ integers, the forces of the girls.

The fourth line contains a single integer $Q$.

Each of the next $Q$ lines has the form B x y or F x y. B means the swap is in the boys' group, F means it is in the girls' group, and $x$ and $y$ are the swapped positions.

Print $Q$ lines. Print $1$ if the game can be successful after the swap, or $0$ otherwise.

• $1 \le n, m, Q \le 10^5$
• $1 \le S \le 10^9$
• $0 \le B_i, F_i \le 10^9$
• For every swap, $|x - y| = 1$.
• It is guaranteed that the game is successful before the first swap.