Кола — це ТОЧКИ !#13067

Кола — це ТОЧКИ !

4 секунди

1 024 мегабайти

Вам задано множину з $n$ точок, кожна точка задається двома цілими числами $(x_{i}, y_{i})$ (x_i , y_i); дві з них є базовими точками. Вам потрібно обробити $q$ запитів двох типів.

$+ (x, y)$ + \hspace{2mm} (x,y) , додати точку ( $x, y$ ) до множини; гарантується, що додана точка ще не належить множині.
$- (x, y)$ - \hspace{2mm} (x,y) , вилучити точку ( $x, y$ ) з множини; гарантується, що вилучувана точка належить множині та не є базовою точкою важливо!Динамічна мультимножина точних раціональних центрів описаних кіл трикутника.

Для початкової множини та після кожного запиту виведіть "YES", якщо можна провести коло, яке проходить через усі точки множини, та "NO" інакше.

Вхідні дані

Перший рядок містить одне ціле число $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить чотири цілих числа $n, q, a, b$ n,q,a,b ( $2 \leq n \leq 2 \cdot 1 0^{5}$ 2 \le n \le 2\cdot 10^5 ; $0 \leq q \leq 2 \cdot 1 0^{5}$ 0 \le q \le 2\cdot 10^5) ( $1 \leq a, b \leq n$ 1 \le a,b \le n , $a \neq = b$ a \neq b) — кількість точок, кількість запитів, індекс першої базової точки, індекс другої базової точки відповідно.

Далі йдуть $n$ рядків; кожен рядок містить два цілих числа $x_{i}, y_{i}$ x_i , y_i ( $- 1 0^{6} \leq x_{i}, y_{i} \leq 1 0^{6}$ -10^6 \le x_i , y_i \le 10^6) — координати $i_{t h}$ i_{th} точки.

Далі йдуть $q$ рядків вигляду $c_{i}, x_{i}, y_{i}$ c_i , x_i , y_i ( $c_{i} \in {+, -}$ c_i \in \{+ , -\} , $- 1 0^{6} \leq x_{i}, y_{i} \leq 1 0^{6}$ -10^6 \le x_i,y_i \le 10^6).

Гарантується, що сума $n$ і сума $q$ за всіма тестовими випадками не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть $q + 1$ q+1 рядків: відповідь для початкової множини, а потім відповідь після кожного запиту.

Приклади

Приклад 1

Примітка

У першому тестовому випадку після другого запиту коло можна провести так, як показано нижче.

Оцінювання

Підзадача $1$ ( $5$ балів) $n = 2, q = 0$ n = 2 \hspace{1mm}, \hspace{1mm}q = 0 для всіх тестових випадків.
Підзадача $2$ ( $15$ балів) $n = 3, q = 0$ n = 3 \hspace{1mm} , \hspace{1mm} q = 0 для всіх тестових випадків.
Підзадача $3$ ( $40$ балів) $q = 0$ q = 0 для всіх тестових випадків.
Підзадача $4$ ( $240$ балів) Без додаткових обмежень.