#include <stdlib.h>
#include <string.h>
//#include "temelia/common.h"

#ifndef _new
    #define _new malloc
    #define _delete free
#endif

int* _linear_hash_nil = NULL;

typedef struct{
    void** hash;
    int size, cap, keySize, linearORquadratic_probing;
    double calibrateConstant;

    int (*compare_key)(void*, void*);
    int (*hash_function)(void*);
    int (*probing)(int);
} _linear_hash_t;

///PRIVATE FUNCTIONS
int _linear_hash_linear_probing(int);
int _linear_hash_quadratic_probing(int);
int _linear_hash_new_capacity(int);
void _linear_hash_calibrate(_linear_hash_t*);
int _linear_hash_keep_going(_linear_hash_t*, void*, void*, int);
int _linear_hash_find(_linear_hash_t*, void*);
int _linear_hash_is_element(void*);
int _linear_hash_has_element(void*);

///PUBLIC FUNCTIONS
void* linear_hash_new(int ,int (*)(void*, void*), int (*)(void*), int, double);
void linear_hash_clear(_linear_hash_t*);
void linear_hash_delete(_linear_hash_t*);
void linear_hash_swap(_linear_hash_t*, _linear_hash_t*);
int linear_hash_contains(_linear_hash_t*, void*);
int linear_hash_is_empty(_linear_hash_t*);
int linear_hash_get_size(_linear_hash_t*);
int linear_hash_get_capacity(_linear_hash_t*);
void linear_hash_insert(_linear_hash_t*, void*);
void linear_hash_erase(_linear_hash_t*, void*);
void linear_hash_iterate(_linear_hash_t*, void (*)(void*, void*), void*);

///PRIVATE FUNCTIONS
int _linear_hash_linear_probing(int i){
    return 1;
}

int _linear_hash_quadratic_probing(int i){
    return (i << 1) + 1;
}

int _linear_hash_new_capacity(int cap){
    return (cap << 1) + 1;
}

void _linear_hash_calibrate(_linear_hash_t* hash){
    return;
    if (hash -> size < hash -> calibrateConstant * hash -> cap)
        return;

    void* H = linear_hash_new(_linear_hash_new_capacity(hash -> cap),
                              hash -> compare_key,
                              hash -> hash_function,
                              hash -> linearORquadratic_probing,
                              hash -> calibrateConstant
                              );

    int i;
    for (i = 0; i < hash -> cap ; i++)
        if (_linear_hash_has_element(hash -> hash[i]))
            linear_hash_insert(H, hash -> hash[i]);

    linear_hash_swap(hash, H);
    linear_hash_delete(H);
}

int _linear_hash_keep_going(_linear_hash_t* hash, void* key, void* poz, int insertORfind){
    if (poz == NULL)
        return 0;

    if (poz == _linear_hash_nil)
        return insertORfind;

    return hash -> compare_key(poz, key) != 0;
}

int _linear_hash_find(_linear_hash_t* hash, void* key){
    int poz = (unsigned short int)hash -> hash_function(key), i = 0;
    while (_linear_hash_keep_going(hash, key, hash -> hash[poz], 1))
        poz = (unsigned short int)(poz + hash -> probing(i++));

    return poz;
}

int _linear_hash_has_element(void* poz){
    return poz != NULL && poz != _linear_hash_nil;
}

///PUBLIC FUNCTIONS
void* linear_hash_new(int cap, int (*compare)(void*, void*), int (*hashFunction)(void*), int linearORquadratic_probing, double fillConstant){
    if (_linear_hash_nil == NULL)
        _linear_hash_nil = _new(sizeof(int));

    _linear_hash_t* hash = _new( sizeof(_linear_hash_t) );

    hash -> cap = cap;
    hash -> hash = _new(cap * sizeof(void*));
    linear_hash_clear(hash);

    hash -> compare_key = compare;
    hash -> hash_function = hashFunction;
    hash -> linearORquadratic_probing = linearORquadratic_probing;

    if (linearORquadratic_probing)
        hash -> probing = _linear_hash_linear_probing;
    else
        hash -> probing = _linear_hash_quadratic_probing;

    if (fillConstant <= 0 || fillConstant > 1){
        if (linearORquadratic_probing)
            fillConstant = 0.8;
        else
            fillConstant = 0.5;
    }
    hash -> calibrateConstant = fillConstant;
    return hash;
}

void linear_hash_clear(_linear_hash_t* hash){
    hash -> size = 0;
    memset(hash -> hash, 0, hash -> cap * sizeof(void*));
}

void linear_hash_delete(_linear_hash_t* hash){
    _delete(hash -> hash);
    _delete(hash);
}

void linear_hash_swap(_linear_hash_t* A, _linear_hash_t* B){
    _linear_hash_t aux = *A;
    *A = *B;
    *B = aux;
}

int linear_hash_contains(_linear_hash_t* hash, void* key){
    return _linear_hash_has_element(hash -> hash[_linear_hash_find(hash, key)]);
}

int linear_hash_is_empty(_linear_hash_t* hash){
    return hash -> size == 0;
}

int linear_hash_get_size(_linear_hash_t* hash){
    return hash -> size;
}

int linear_hash_get_capacity(_linear_hash_t* hash){
    return hash -> cap;
}

void linear_hash_insert(_linear_hash_t* hash, void* key){
    _linear_hash_calibrate(hash);

    int write_poz = (unsigned short int)(hash -> hash_function(key)), i = 0;
    while (_linear_hash_keep_going(hash, key, hash -> hash[write_poz], 0))
        write_poz = (unsigned short int)(write_poz + hash -> probing(i++));

    int poz = write_poz;
    while (_linear_hash_keep_going(hash, key, hash -> hash[poz], 0))
        poz = (unsigned short int)(poz + hash -> probing(i++));

    if (_linear_hash_has_element(hash -> hash[poz]))
        return;

    hash -> hash[write_poz] = key;
    hash -> size++;
}

void linear_hash_erase(_linear_hash_t* hash, void* key){
    int poz = _linear_hash_find(hash, key);

    if (!_linear_hash_has_element(hash -> hash[poz]))
        return;

    hash -> size--;
    _delete(hash -> hash[poz]);
    hash -> hash[poz] = _linear_hash_nil;
}

void linear_hash_iterate(_linear_hash_t* hash, void (*iterate)(void*, void*), void* context){
    int i;
    for (i = 0 ; i < hash -> cap ; i++)
        if (_linear_hash_has_element(hash -> hash[i]))
            iterate(hash -> hash[i], context);
}

///ACTUAL CODE

int compara(void* a, void *b){
    return (*(int*)a) != (*(int*)b);
}

int hashFunction(void* a){
    return *(int*)a;
}

int* fint(int x){
    int* poz = _new(sizeof(int));
    *poz = x;

    return poz;
}

char* sth(){
    return _new(sizeof(char));
}

#include <stdio.h>

int main(){
    void* hash = linear_hash_new(1 << 16, compara, hashFunction, 0, 1);
    FILE* fin = fopen("hashuri.in", "r");
    FILE* fout = fopen("hashuri.out", "w");

    int times, tip, x;

    fscanf(fin, "%d", &times);
    while (times--){
        fscanf(fin, "%d%d", &tip, &x);

        if (tip == 1)
            linear_hash_insert(hash, fint(x));
        if (tip == 2)
            linear_hash_erase(hash, &x);
        if (tip == 3)
            fprintf(fout, "%d\n", linear_hash_contains(hash, &x));
    }

    fclose(fin);
    fclose(fout);

    return 0;
}