시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 1024 MB 111 30 24 39.344%

문제

MOLOCO is a company that matches advertisers with potential users using their high-performance ad platform.

MOLOCO is in contact with $N$ advertisers, where the $i$-th advertiser has paid for $a_i$ advertisements to deliver. Our advanced prediction algorithm has picked $M$ potential recipients, which we will deliver the advertisements to. For the $j$-th recipient, we can deliver up to $b_j$ advertisements. 

Jaehyun is testing several hypotheses to increase engagement in the advertisements. One day, Jaehyun thought that all advertisements received by a single recipient should come from different advertisers: it is boring to watch the same advertisement multiple times. 

Jaehyun wants to estimate the profitability of his hypotheses. He will perform the following kinds of updates.

  • 1 i: Increase $a_i$ by one.
  • 2 i: Decrease $a_i$ by one.
  • 3 j: Increase $b_j$ by one.
  • 4 j: Decrease $b_j$ by one.

All updates are cumulative. Jaehyun wants to check if the system can deliver all advertisements of our advertisers given the changing landscape of the advertisers and recipients.

입력

The first line contains two integers, $N$ and $M$ ($1 \le N, M \le 250\,000$).

The next line contains $N$ integers $a_1, a_2, \ldots, a_N$ ($0 \le a_i \le 250\,000$).

The next line contains $M$ integers $b_1, b_2, \ldots, b_M$ ($0 \le b_j \le 250\,000$).

The next line contains a single integer $Q$ ($1 \le Q \le 250\,000$).

The next $Q$ lines contain two integers in one of the following forms:

  • 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$)

The input will be set in a way such that all $a_i$ and $b_j$ values are always nonnegative.

출력

Print $Q$ lines. On the $i$-th line, print $1$ if all advertisements can be delivered given the first $i$ updates, and $0$ otherwise.

예제 입력 1

5 5
1 5 2 4 3
3 3 3 3 3
5
4 2
3 5
2 2
1 1
1 4

예제 출력 1

0
1
1
1
0

출처

University > KAIST > 2020 KAIST 10th ICPC Mock Competition A번