Sürünün hasarlanması#11184

Sürünün hasarlanması

1 saniyə

128 meqabayt

Çox çətin

Fermer Con öz inəklərinin hərəkətini məhdudlaşdırmaq üçün hara düz xətli hasar qurmalı olduğunu müəyyən etməkdə sizin köməyinizə ehtiyac duyur. O, hasarın bir neçə mümkün yerləşmə variantını nəzərdən keçirib və bunlardan hansının etibarlı olduğunu bilmək istəyir. Hasar o zaman etibarlı sayılır ki, bütün inəklər ondan ciddi şəkildə bir tərəfdə yerləşsinlər; əgər ən azı bir inək hasarın üzərində birbaşa yerləşirsə, belə hasar etibarsız sayılır.

FC hasarın mümkün yerləşmələri haqqında bir sıra sorğular verəcək. Hər sorğu üçün, uyğun hasar etibarlı olarsa $Y E S$ , əks halda isə $N O$ çap edin.

Bundan əlavə, FC vaxtaşırı sürüyə yeni inəklər əlavə edə bilər. Yeni inək əlavə edildiyi andan etibarən, hasar haqqında hər bir sonrakı sorğuda onu da nəzərə almaq lazımdır: hasarın etibarlı sayılması üçün yeni inək də bütün digər inəklərlə eyni tərəfdə yerləşməlidir.

Giriş

Birinci sətirdə iki tam ədəd $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) və $q (1 \leq q \leq 1 0^{5})$ q~(1 \le q \le 10^5) verilir – uyğun olaraq sürüdəki inəklərin ilkin sayı və sorğuların sayı.

Sonrakı $n$ sətir sürünün ilkin vəziyyətini təsvir edir. Hər sətirdə boşluqla ayrılmış iki tam ədəd $x$ və $y$ verilir – bir inəyin mövqeyini göstərir.

Sonrakı $q$ sətirdə sürüyə yeni inək əlavə edən və ya hasarın etibarlılığını yoxlayan sorğular verilir.

"1 x y" formalı sorğu o deməkdir ki, sürüyə $(x, y)$ nöqtəsində yeni inək əlavə olunur.

"2 A B C" formalı sorğu o deməkdir ki, FC $A x + B y = C$ Ax + By = C tənliyi ilə verilən hasarı yoxlamaq istəyir.

Bütün inəklərin mövqeləri bütün giriş məlumatları boyunca fərqlidir və $- 1 0^{9} \leq x, y \leq 1 0^{9}$ -10^9 \le x, y \le 10^9 şərtini ödəyir. Hasarın parametrləri $- 1 0^{9} \leq A, B \leq 1 0^{9}$ -10^9 \le A, B \le 10^9 və $- 1 0^{18} \leq C \leq 1 0^{18}$ -10^{18} \le C \le 10^{18} şərtlərini ödəyir. Hasar haqqında heç bir sorğuda $A = B = 0$ A = B = 0 olmur.

Çıxış

Hasar haqqında hər sorğu üçün, hasar etibarlı olarsa " $Y E S$ ", əks halda isə " $N O$ " çap edin.

Nümunələr

$2 x + 2 y = 3$ 2x + 2y = 3 düz xətti başlanğıcda bütün $3$ inəyi eyni tərəfdə saxlayır. Lakin $(1, 1)$ nöqtəsində inək əlavə edildikdən sonra o, hasarın digər tərəfində olur, buna görə də hasar artıq etibarlı deyil.

$y = 1$ y = 1 düz xətti etibarsızdır, çünki $(0, 1)$ və $(1, 1)$ nöqtələrindəki inəklər onun üzərində birbaşa yerləşir.

Nümunə 1