Recinzione della mandria#11184
Il fattore John ha bisogno del vostro aiuto per determinare dove costruire uno steccato rettilineo per limitare gli spostamenti delle sue mucche. Ha considerato diverse possibili posizioni per lo steccato e vuole determinare quali di esse siano valide. Uno steccato è considerato valido se tutte le mucche si trovano strettamente da un solo lato di esso; se anche una sola mucca giace direttamente sullo steccato, tale steccato è considerato non valido.
FJ porrà una serie di interrogazioni riguardo a possibili posizioni dello steccato. Per ogni interrogazione, stampate se lo steccato corrispondente è valido, e altrimenti.
Inoltre, FJ potrà ogni tanto aggiungere nuove mucche alla mandria. Dal momento in cui viene aggiunta una nuova mucca, ogni successiva interrogazione riguardante uno steccato deve tenere conto anche di essa: affinché uno steccato sia considerato valido, anche la nuova mucca dovrà trovarsi dallo stesso lato dello steccato di tutte le altre mucche.
La prima riga contiene due interi n~(1 \le n \le 10^5) e q~(1 \le q \le 10^5), che indicano rispettivamente il numero iniziale di mucche nella mandria e il numero di interrogazioni.
Le successive righe descrivono lo stato iniziale della mandria. Ogni riga contiene due interi separati da uno spazio, e , che indicano la posizione di una mucca.
Le successive righe contengono le interrogazioni, che aggiungono una nuova mucca alla mandria oppure verificano la validità di uno steccato.
Una interrogazione della forma "1 x y" significa che una nuova mucca viene aggiunta alla mandria nel punto .
Una interrogazione della forma "2 A B C" significa che FJ desidera verificare lo steccato definito dall'equazione Ax + By = C.
Tutte le posizioni delle mucche sono distinte durante l'intero insieme di dati in ingresso e soddisfano -10^9 \le x, y \le 10^9. I parametri dello steccato soddisfano -10^9 \le A, B \le 10^9 e -10^{18} \le C \le 10^{18}. Nessuna interrogazione riguardante uno steccato ha A = B = 0.
Per ogni interrogazione riguardante uno steccato, stampate "" se lo steccato è valido, e "" altrimenti.
La retta 2x + 2y = 3 inizialmente lascia tutte e le mucche da un solo lato di essa. Tuttavia, dopo l'aggiunta di una mucca nel punto , quest'ultima si trova dall'altro lato dello steccato, quindi lo steccato non è più valido.
La retta y = 1 non è valida, poiché le mucche nei punti e giacciono direttamente su di essa.
Esempio 1