Bfs

시간 제한1초메모리 제한1024 MB

요약

소년은 기울기를 오른쪽으로, 소녀는 왼쪽으로 밀어 기울기가 S를 넘지 않는 던지기 순서가 있는지 확인합니다. 한 그룹 안에서 두 인접한 사람의 순서를 바꿀 때마다 그 판단을 다시 합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 세그먼트 트리, 누적 합
정답자: 아직 제출이 없습니다

문제

402반 아이들이 종소리를 듣고 밖으로 뛰어나가 놀았다. 운동장 한가운데에 큰 기둥이 있어서, 아이들은 다음과 같은 게임을 생각해냈다. 먼저 아이들은 $m$ 명의 여자아이와 $n$ 명의 남자아이로 나뉘어 운동장 어딘가에 자리를 잡는다.

기둥은 처음에 완전히 수직이며 기울기는 $0$ 이다. 각 아이에게는 힘이 있다. $B_i$ 는 $i$ 번째 남자아이의 힘이고, $F_i$ 는 $i$ 번째 여자아이의 힘이다. 게임은 한 단계씩 진행된다. 매 단계마다 기둥에 가장 가까운 남자아이 또는 여자아이(번호가 가장 작은 아이)가 기둥에 공을 던지고 게임에서 빠진다. 남자아이가 던지면 기둥이 오른쪽으로 기울고, 여자아이가 던지면 왼쪽으로 기운다. 던질 때마다 기울기는 던진 아이의 힘만큼 바뀐다.

게임이 끝까지 무사히 진행되도록, 기둥은 어느 방향으로든 $S$ 를 넘게 기울어서는 안 된다. 아이들은 이 조건을 지키는 던지기 순서가 있는지 알고 싶어 한다.

선생님은 $Q$ 번의 순간에 연속한 남자아이 두 명 또는 연속한 여자아이 두 명의 순서를 맞바꾼다. 맞바꾼 순서는 그대로 유지된다. 매번 맞바꾼 뒤에 유효한 던지기 순서가 있는지 판단하라.

입력

첫 줄에 정수 $n$ , $m$ , $S$ 가 주어진다.

둘째 줄에는 남자아이들의 힘을 나타내는 정수 $n$ 개가 주어진다.

셋째 줄에는 여자아이들의 힘을 나타내는 정수 $m$ 개가 주어진다.

넷째 줄에는 정수 $Q$ 가 주어진다.

이어지는 $Q$ 개의 줄은 B x y 또는 F x y 형식이다. B는 남자아이 그룹에서, F는 여자아이 그룹에서 맞바꾸는 것이고, $x$ 와 $y$ 는 맞바꿀 위치다.

출력

$Q$ 개의 줄을 출력한다. 맞바꾼 뒤 게임을 성공시킬 수 있으면 $1$ , 그렇지 않으면 $0$ 을 출력한다.

제한

$1 \le n, m, Q \le 10^5$
$1 \le S \le 10^9$
$0 \le B_i, F_i \le 10^9$
모든 맞바꾸기에서 $|x - y| = 1$ 이다.
첫 번째 맞바꾸기 전에 게임이 성공한다고 보장된다.

예제1

예제 1

입력

6 3 30000
15000 15000 60000 30000 29805 56555
60000 60000 57187
14
B 2 3
B 2 3
B 2 3
B 2 3
F 2 3
F 2 3
B 2 3
B 2 3
B 3 4
B 3 4
B 2 3
B 2 3
F 2 3
F 2 3

예상 출력