package sprint4.final

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

class MyHashTable {
    private val capacity = 1000003
    private val innerArray: MutableList<Bucket?> = MutableList(capacity) { null }
    private val modifier = Int.MAX_VALUE / 2

    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

        while (true) {
            val secondHash = (key / 2)
                .let {
                    it + if (key % 2 == it % 2) {
                        1
                    } else {
                        0
                    }
                }
            val candidateIndex: Int = (key % capacity + modifier + (secondHash * step) % capacity) % capacity
            val candidateBucket = innerArray[candidateIndex] ?: return 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"