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

#ifndef _new
    #define _new malloc
#endif

#define _local_swap(A, B, X) X = A; A = B; B = X;

typedef enum{
    FREE,
    DELETED,
    OCCUPIED,
} _inplace_linear_hash_node_state;

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

    int (*compare_key)(void*, void*);
    int (*inplace_linear_hash_function)(void*);
    int (*probing_increment)(int);
} _inplace_linear_hash_t;

///PRIVATE FUNCTIONS
int _inplace_linear_hash_linear(int);
int _inplace_linear_hash_quadratic(int);
void _inplace_linear_hash_alloc(_inplace_linear_hash_t*, int);
void _inplace_linear_hash_calibration(_inplace_linear_hash_t*);
int _inplace_linear_hash_keep_going(_inplace_linear_hash_t*, int, void*, int);
int _inplace_linear_hash_supposed_position(_inplace_linear_hash_t*, void*, int);
int _inplace_linear_hash_find(_inplace_linear_hash_t*, void*);
void* _inplace_linear_hash_get_key(_inplace_linear_hash_t*, int poz);
void _inplace_linear_hash_set_key(_inplace_linear_hash_t*, int, void*);
void* _inplace_linear_hash_get_state_pointer(_inplace_linear_hash_t*, int);
_inplace_linear_hash_node_state _inplace_linear_hash_get_state(_inplace_linear_hash_t*, int);
void _inplace_linear_hash_set_state(_inplace_linear_hash_t*, int, _inplace_linear_hash_node_state);

///PUBLIC FUNCTIONS
void* inplace_linear_hash_new(int, int ,int (*)(void*, void*), int (*)(void*), int);
void inplace_linear_hash_clear(_inplace_linear_hash_t*);
void inplace_linear_hash_delete(_inplace_linear_hash_t*);
void inplace_linear_hash_swap(_inplace_linear_hash_t*, _inplace_linear_hash_t*);
int inplace_linear_hash_contains(_inplace_linear_hash_t*, void*);
int inplace_linear_hash_is_empty(_inplace_linear_hash_t*);
int inplace_linear_hash_get_size(_inplace_linear_hash_t*);
int inplace_linear_hash_get_capacity(_inplace_linear_hash_t*);
void inplace_linear_hash_insert(_inplace_linear_hash_t*, void*);
void inplace_linear_hash_erase(_inplace_linear_hash_t*, void*);
void inplace_linear_hash_iterate(_inplace_linear_hash_t*, void (*)(void*));

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

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

void _inplace_linear_hash_alloc(_inplace_linear_hash_t* hash, int size){
    hash -> cap = size;
    hash -> hash = _new( size * (hash -> keySize + sizeof(char)) );
}

void _inplace_linear_hash_calibration(_inplace_linear_hash_t* hash){
    _inplace_linear_hash_t* H = inplace_linear_hash_new((hash -> cap << 1) + 1,
                                       hash -> keySize,
                                       hash -> compare_key,
                                       hash -> inplace_linear_hash_function,
                                       hash -> linearORquadratic_probing
                                       );

    int i, cap = inplace_linear_hash_get_capacity(hash);
    for (i = 0 ; i < cap ; i++)
        if (_inplace_linear_hash_get_state(hash, i) == OCCUPIED)
            inplace_linear_hash_insert(H, _inplace_linear_hash_get_key(hash, i));

    inplace_linear_hash_swap(hash, H);
    inplace_linear_hash_delete(H);
}

int _inplace_linear_hash_keep_going(_inplace_linear_hash_t* hash, int poz, void* key, int insertORfind){
    _inplace_linear_hash_node_state state = _inplace_linear_hash_get_state(hash, poz);

    if (state == FREE)
        return 0;

    if (state == DELETED)
        return insertORfind;

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

int _inplace_linear_hash_supposed_position(_inplace_linear_hash_t* hash, void* key, int insertORfind){
    int cap = inplace_linear_hash_get_capacity(hash);
    int poz = hash -> inplace_linear_hash_function(key) % cap, i = 0;

    while (_inplace_linear_hash_keep_going(hash, poz, key, insertORfind))
        poz = (poz + hash -> probing_increment(i++)) % cap;

    return poz;
}

int _inplace_linear_hash_find(_inplace_linear_hash_t* hash, void* key){
    if (hash -> size == 0)
        return -1;

    int poz = _inplace_linear_hash_supposed_position(hash, key, 1);

    if (_inplace_linear_hash_get_state(hash, poz) != OCCUPIED)
        return -1;

    if (hash -> compare_key(_inplace_linear_hash_get_key(hash, poz), key) == 0)
        return poz;
    return -1;
}

void* _inplace_linear_hash_get_key(_inplace_linear_hash_t* hash, int poz){
    return (hash -> hash) + ( (1 + hash -> keySize) * poz );
}

void _inplace_linear_hash_set_key(_inplace_linear_hash_t* hash, int poz, void* key){
    memcpy(_inplace_linear_hash_get_key(hash, poz), key, hash -> keySize);
}

void* _inplace_linear_hash_get_state_pointer(_inplace_linear_hash_t* hash, int poz){
    return _inplace_linear_hash_get_key(hash, poz) + (hash -> keySize);
}

_inplace_linear_hash_node_state _inplace_linear_hash_get_state(_inplace_linear_hash_t* hash, int poz){
    return *( (char*)_inplace_linear_hash_get_state_pointer(hash, poz) );
}

void _inplace_linear_hash_set_state(_inplace_linear_hash_t* hash, int poz, _inplace_linear_hash_node_state state){
    char p = state;
    memcpy(_inplace_linear_hash_get_state_pointer(hash, poz), &p, sizeof(char));
}

///PUBLIC FUNCTIONS
void* inplace_linear_hash_new(int startSize, int keySize, int (*compare_key)(void*, void*), int (*inplace_linear_hash_function)(void*), int linearORquadratic_probing){
    _inplace_linear_hash_t* H = _new( sizeof(_inplace_linear_hash_t) );

    H -> keySize = keySize;
    H -> linearORquadratic_probing = linearORquadratic_probing;
    _inplace_linear_hash_alloc(H, startSize);
    inplace_linear_hash_clear(H);

    H -> compare_key = compare_key;
    H -> inplace_linear_hash_function = inplace_linear_hash_function;

    if (linearORquadratic_probing)
        H -> probing_increment = _inplace_linear_hash_quadratic;
    else
        H -> probing_increment = _inplace_linear_hash_linear;

    return H;
}

void inplace_linear_hash_clear(_inplace_linear_hash_t* hash){
    memset(hash -> hash, 0, inplace_linear_hash_get_capacity(hash) * (hash -> keySize));
    hash -> size = 0;
}

void inplace_linear_hash_delete(_inplace_linear_hash_t* hash){
    free(hash -> hash);
    free(hash);
}

void inplace_linear_hash_swap(_inplace_linear_hash_t* A, _inplace_linear_hash_t* B){
    void* hash;
    int x;
    int (*compare_key)(void*, void*);
    int (*inplace_linear_hash_function)(void*);
    int (*probing_increment)(int);

    _local_swap(A -> hash, B -> hash, hash);
    _local_swap(A -> size, B -> size, x);
    _local_swap(A -> cap, B -> cap, x);
    _local_swap(A -> keySize, B -> keySize, x);
    _local_swap(A -> linearORquadratic_probing, B -> linearORquadratic_probing, x);
    _local_swap(A -> compare_key, B -> compare_key, compare_key);
    _local_swap(A -> inplace_linear_hash_function, B -> inplace_linear_hash_function, inplace_linear_hash_function);
    _local_swap(A -> probing_increment, B -> probing_increment, probing_increment);
}

int inplace_linear_hash_contains(_inplace_linear_hash_t* hash, void* key){
    return _inplace_linear_hash_find(hash, key) != -1;
}

int inplace_linear_hash_is_empty(_inplace_linear_hash_t* hash){
    return hash -> size == 0;
}

int inplace_linear_hash_get_size(_inplace_linear_hash_t* hash){
    return hash -> size;
}

int inplace_linear_hash_get_capacity(_inplace_linear_hash_t* hash){
    return hash -> cap;
}

void inplace_linear_hash_insert(_inplace_linear_hash_t* hash, void* key){
    if (inplace_linear_hash_contains(hash, key))
        return;

    if ( (hash -> size << 1) >= inplace_linear_hash_get_capacity(hash) )
        _inplace_linear_hash_calibration(hash);

    hash -> size++;
    int poz = _inplace_linear_hash_supposed_position(hash, key, 0);

    _inplace_linear_hash_set_key(hash, poz, key);
    _inplace_linear_hash_set_state(hash, poz, OCCUPIED);

    if ( (hash -> size << 1) >= inplace_linear_hash_get_capacity(hash) )
        _inplace_linear_hash_calibration(hash);
}

void inplace_linear_hash_erase(_inplace_linear_hash_t* hash, void* key){
    int poz = _inplace_linear_hash_supposed_position(hash, key, 1);

    if (poz == -1)
        return;

    hash -> size--;
    _inplace_linear_hash_set_state(hash, poz, DELETED);
}

void inplace_linear_hash_iterate(_inplace_linear_hash_t* hash, void (*iterate)(void*)){
    int i, cap = inplace_linear_hash_get_capacity(hash);

    for (i = 0 ; i < cap ; i++)
        if (_inplace_linear_hash_get_state(hash, i) == OCCUPIED)
            iterate(_inplace_linear_hash_get_key(hash, i));
}

///ACTUAL CODE

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

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

void scrie(void* key){
    printf("%d ", *(int*)key);
}

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

#include <stdio.h>

int main(){
    void* hash = inplace_linear_hash_new(0, sizeof(int), compara, hashFunction, 0);
    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)
            inplace_linear_hash_insert(hash, &x);
        if (tip == 2)
            inplace_linear_hash_erase(hash, &x);
        if (tip == 3)
            fprintf(fout, "%d\n", inplace_linear_hash_contains(hash, &x));
    }

    fclose(fin);
    fclose(fout);

    return 0;
}