24034번 - 선형대수학

홍윤이는 경기과학고등학교에서 학생들에게 선형대수학을 강의하고 있다. 여느 때와 같이 찾아온 기말고사 기간. 평균 점수 37점이라는 어마무시한 기록을 세웠던 중간고사 이후 모두가 홍윤이의 기말고사 문제들을 두려워하고 있다.

시험이 얼마 남지 않은 어느 날, 학생들에게 자습시간을 주고 어제 풀던 Ruby 3 문제를 고민하던 홍윤이는 충격적인 사실을 엿듣게 된다. 바로 학생들이 시험 시간에 단답형 문제를 각자 하나씩 풀고 은밀히 답을 공유하기로 약속한 것이다. 믿었던 학생들에게 배신감을 느낀 홍윤이는 각 학생마다 다른 단답형 문제를 출제해, 부정행위를 하려 한 학생들에게 본때를 보여주기로 결심한다.

1번 문제는 다음과 같다.

변수가 $x_1, x_2, \cdots, x_k$로 총 $k$개이고, 식이 $2$개인 다음 연립방정식의 해가 존재하는지 판별하시오.

$P_1 \times x_1+P_2 \times x_2+…+P_k \times x_k=A$

$Q_1 \times x_1+Q_2 \times x_2+…+Q_k \times x_k=B$

단, $0 \leq x_1, x_2, \cdots, x_k \leq 1$을 만족한다.

하지만 막상 학생별로 $P_i$들과 $Q_i$들을 따로 결정한 후 답까지 계산하려니 귀찮아진 홍윤이는 방금 전에 만든 시험지에서 새로운 $(P_i, Q_i)$ 순서쌍을 하나 추가하거나, 이미 있던 $(P_i, Q_i)$를 하나 제거하는 방식으로 문제들을 만들어내려 한다. 방금 떠오른 Ruby 3 문제의 풀이를 구현하러 간 홍윤이를 대신하여 시험 문제 출제를 도와주도록 하자.

홍윤이의 노트에는 출제에 사용하려고 한 $(U_i, V_i)$ 순서쌍이 $N$개 적혀 있고, 또 어떤 순서쌍을 추가하고, 삭제할지, 현재 상태의 시험지를 출제할지 계획해 놓은 길이 $Q$의 쿼리들이 적혀 있다. 쿼리들을 수행하기 전의 문제는 어떤 순서쌍도 추가되어 있지 않은, $k=0$의 상태이다.

쿼리는 두 종류로 표현된다.

• $1$ $a$ $b$: $A=a$, $B=b$로 설정한 뒤 현재 상태의 연립방정식을 출제하기 위해 문제의 답을 계산한다. 만약 $1 \leq i \leq k$인 모든 $x_i$가 $0 \leq x_i \leq 1$을 만족하는 해가 있다면 YES, 아니면 NO를 출력한다. $k=0$일 때 이 쿼리는 주어지지 않는다.
• $2$ $c$: 현재 문제에 $c$번째 순서쌍 $(U_c, V_c)$이 포함되어 있지 않다면 추가하고, 포함되어 있다면 제거한다.

첫 줄에 $N$과 $Q$가 주어진다. $(1 \leq N, Q \leq 300,000)$

다음 줄부터 $N$개의 줄에 걸쳐 순서쌍$(U_i, V_i)$가 공백으로 구분되어 주어진다. $(-10^9 \leq U_i, V_i \leq 10^9)$

다음 줄부터 $Q$개의 줄에 걸쳐 두 종류의 쿼리 "$1$ $a$ $b$" 혹은 "$2$ $c$"가 주어진다. ($-10^{15} \leq a, b \leq 10^{15}$, $1 \leq c \leq N$)

1번 쿼리에 대한 답을 YES 혹은 NO로 한 줄에 하나씩 순서대로 출력한다.