package sprint4.final

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

infix fun Int.myMod(m: Int) = this - (this.toDouble() / m).toInt()

class MyHashTable {
    private val capacity = 100003
    private val innerArray: MutableList<Bucket?> = MutableList(capacity) { null }

    operator fun set(key: Int, value: Int) {
        innerArray[getIndex(key)] = Bucket(value, key)
    }

    operator fun get(key: Int) = innerGet(key)?.value

    fun delete(key: Int) = innerGet(key)?.delete()

    private fun innerGet(key: Int): Bucket? = innerArray[getIndex(key)]?.takeIf { !it.deleted }

    private fun getIndex(key: Int): Int {

        var step = 0
        var deletedIndexPotentialToInsert: Int? = null
        var rounds = 0

        while (true) {
            val secondHash = (key / 2)
                .let {
                    it + if (key % 2 == it % 2) {
                        1
                    } else {
                        0
                    }
                }
            // Ищем следующий подходящий индекс
            val candidateIndex: Int = (key.mod(capacity) + (secondHash * step).mod(capacity)) % capacity
//            val candidateIndex: Int = (key.mod(capacity) + step) % capacity

            if (step != 0 && candidateIndex == key.mod(capacity) && ++rounds == 5) {
                throw Error(
                    """
                    step: $step
                    rounds: $rounds
                    total: ${innerArray.count { it != null }}
                    deleted: ${innerArray.count { it?.deleted == true }}
                    active: ${innerArray.count { it?.deleted == false }}
                    empty: ${innerArray.count { it == null }}
                    key: $key
                    candidateIndex: $candidateIndex
                    deletedIndexPotentialToInsert: $deletedIndexPotentialToInsert
                    keyExists: ${innerArray.find { it?.key == key } ?: "none"}
                """.trimIndent()
                )
            }


            // Если элемент по этому индексу свободен, то значит он подходит для вставки,
            // а искомого элемента для возврата или удаления нет
            // Но при этом для экономии возвращаем найденный удалённый, если такой есть
            val candidateBucket = innerArray[candidateIndex]
                ?: return deletedIndexPotentialToInsert ?: candidateIndex

            // В данной ветке мы ещё не нашли нужный индекс
            // Если текущий удалён, и он первый удалённый, то запоминаем его индекс
            if (candidateBucket.deleted && deletedIndexPotentialToInsert == null) deletedIndexPotentialToInsert =
                candidateIndex

            // Если текущий удалён или ключ не совпадает...
            if (candidateBucket.deleted || candidateBucket.key != key) {
                // ...то уходим на следующую итерацию
                ++step
                continue
            }

            //Нашли интересующий нас индекс
            return candidateIndex
        }
    }

    private class Bucket constructor(val value: Int, val key: Int) {
        var deleted = false
            private set

        fun delete(): Int {
            deleted = true
            //При удалении для упрощения синтаксиса возвращаем удалённый элемент
            return value
        }
    }
}

fun main() {
    val buffer = BufferedReader(InputStreamReader(System.`in`))
    val sb = StringBuilder()
    val hashTable = MyHashTable()
    repeat(buffer.readLine().toInt()) {
        val tokenizer = StringTokenizer(buffer.readLine())
        when (tokenizer.nextToken()) {
            "get" -> hashTable[tokenizer.nextToken().toInt()].nullSafeToString()
            "put" -> {
                hashTable[tokenizer.nextToken().toInt()] = tokenizer.nextToken().toInt()
                null
            }
            "delete" -> hashTable.delete(tokenizer.nextToken().toInt()).nullSafeToString()
            else -> throw Error("unknown command")
        }
            ?.let { sb.appendLine(it) }
    }
    println(sb)
}

fun Int?.nullSafeToString() = this?.toString() ?: "None"