광고 매칭

MOLOCO는 고성능 광고 플랫폼을 이용해 광고주와 잠재 사용자를 매칭하는 회사입니다.

MOLOCO는 $N$명의 광고주와 계약되어 있습니다. $i$번째 광고주는 전달할 광고를 $a_i$개 결제했습니다. 저희 고도화된 예측 알고리즘이 광고를 받을 잠재 수신자 $M$명을 골랐습니다. $j$번째 수신자에게는 광고를 최대 $b_j$개까지 전달할 수 있습니다.

재현은 광고 참여도를 높이기 위한 가설 여러 개를 검증하고 있습니다. 어느 날 재현은 한 수신자가 받는 광고가 모두 서로 다른 광고주의 것이어야 한다고 생각했습니다. 같은 광고를 여러 번 보는 것은 지루하기 때문입니다.

재현은 이 가설들의 수익성을 추정하려 합니다. 다음 네 종류의 갱신을 수행합니다.

• 1 i: $a_i$를 1 증가시킨다.
• 2 i: $a_i$를 1 감소시킨다.
• 3 j: $b_j$를 1 증가시킨다.
• 4 j: $b_j$를 1 감소시킨다.

모든 갱신은 누적됩니다. 광고주나 수신자의 상황이 바뀔 때마다 모든 광고를 전달할 수 있는지 확인하려 합니다.

첫 줄에 두 정수 $N$과 $M$이 주어진다 ($1 \le N, M \le 250\,000$).

다음 줄에 $N$개의 정수 $a_1, a_2, \ldots, a_N$이 주어진다 ($0 \le a_i \le 250\,000$).

다음 줄에 $M$개의 정수 $b_1, b_2, \ldots, b_M$이 주어진다 ($0 \le b_j \le 250\,000$).

다음 줄에 정수 $Q$가 주어진다 ($1 \le Q \le 250\,000$).

다음 $Q$개의 줄에는 아래 형식 중 하나의 갱신이 주어진다.

• 1 i ($1 \le i \le N$)
• 2 i ($1 \le i \le N$)
• 3 j ($1 \le j \le M$)
• 4 j ($1 \le j \le M$)

입력은 모든 $a_i$와 $b_j$가 항상 0 이상이도록 주어진다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 처음 $i$개의 갱신을 반영한 뒤 모든 광고를 전달할 수 있으면 1을, 그렇지 않으면 0을 출력한다.