package main

import (
	"bufio"
	"fmt"
	"math/rand"
	"os"
	"strconv"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

// TreapKey is for string -> int map
type TreapKey = string

// TreapValue is for string -> int map
type TreapValue = int

// NewTreapNode is a constructor of TreapNode
func NewTreapNode(key string, value TreapValue, priority int) *TreapNode {
	tn := TreapNode{}
	tn.key = key
	tn.value = value
	tn.priority = priority
	return &tn
}

// TreapNode contains integer
type TreapNode struct {
	key      TreapKey
	value    TreapValue
	priority int
	left     *TreapNode
	right    *TreapNode
}

func (node *TreapNode) setLeftChild(key TreapKey, value TreapValue, priority int) {
	child := NewTreapNode(key, value, priority)
	node.left = child
}

func (node *TreapNode) setRightChild(key TreapKey, value TreapValue, priority int) {
	child := NewTreapNode(key, value, priority)
	node.right = child
}

// NewTreap is a constructor of Treap
func NewTreap() *Treap {
	treap := Treap{}
	return &treap
}

// Treap described at
//  https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_8_D
type Treap struct {
	root *TreapNode
}

func (t *Treap) insert(key TreapKey, value TreapValue, priority int) {
	if t.root == nil {
		node := NewTreapNode(key, value, priority)
		t.root = node
	} else {
		t.root = t.insertLoop(t.root, key, value, priority)
	}
}

func (t *Treap) insertLoop(current *TreapNode, key TreapKey, value TreapValue, priority int) *TreapNode {
	if current == nil {
		newNode := NewTreapNode(key, value, priority)
		return newNode
	}

	if key == current.key {
		return current
	}

	if key < current.key {
		current.left = t.insertLoop(current.left, key, value, priority)
		if current.priority < current.left.priority {
			current = t.rightRotate(current)
		}
	} else {
		current.right = t.insertLoop(current.right, key, value, priority)
		if current.priority < current.right.priority {
			current = t.leftRotate(current)
		}
	}

	return current
}

func (t *Treap) leftRotate(x *TreapNode) *TreapNode {
	y := x.right
	x.right = y.left
	y.left = x
	return y
}

func (t *Treap) rightRotate(y *TreapNode) *TreapNode {
	x := y.left
	y.left = x.right
	x.right = y
	return x
}

func (t *Treap) find(key TreapKey) *TreapNode {
	// fmt.Println(t.inorderTreeWalkV2(t.root))
	return t.findLoop(t.root, key)
}

func (t *Treap) findLoop(current *TreapNode, key TreapKey) *TreapNode {
	if current == nil {
		return nil
	}

	if key < current.key {
		return t.findLoop(current.left, key)
	} else if current.key == key {
		return current
	}
	return t.findLoop(current.right, key)
}

func (t *Treap) delete(key TreapKey) {
	t.root = t.deleteLoop(t.root, key)
}

func (t *Treap) deleteLoop(current *TreapNode, key TreapKey) *TreapNode {
	if current == nil {
		return nil
	}
	if key < current.key {
		current.left = t.deleteLoop(current.left, key)
	} else if key > current.key {
		current.right = t.deleteLoop(current.right, key)
	} else {
		return t.deleteNode(current, key)
	}
	return current
}

func (t *Treap) deleteNode(node *TreapNode, key TreapKey) *TreapNode {
	if node.left == nil && node.right == nil {
		return nil
	} else if node.left == nil {
		node = t.leftRotate(node)
	} else if node.right == nil {
		node = t.rightRotate(node)
	} else {
		if node.left.priority > node.right.priority {
			node = t.rightRotate(node)
		} else {
			node = t.leftRotate(node)
		}
	}
	return t.deleteLoop(node, key)
}

func (t *Treap) inorderTreeWalkV2(p *TreapNode) string {
	if p == nil {
		return "."
	}

	l := t.inorderTreeWalkV2(p.left)
	r := t.inorderTreeWalkV2(p.right)
	return fmt.Sprintf("(%v:%v %v %v)", p.key, p.value, l, r)
}

func (t *Treap) printInorderWalk(l, r TreapKey) {
	if t.root != nil {
		fmt.Print(t.printInorderWalkRoop(t.root, l, r))
	}
}

func (t *Treap) printInorderWalkRoop(mid *TreapNode, l, r TreapKey) string {
	concated := ""
	if mid.left != nil && l <= mid.key {
		concated += t.printInorderWalkRoop(mid.left, l, r)
	}
	if l <= mid.key && mid.key <= r {
		concated += fmt.Sprintf("%v %v\n", mid.key, mid.value)
	}
	if mid.right != nil && mid.key <= r {
		concated += t.printInorderWalkRoop(mid.right, l, r)
	}
	return concated
}

// NewMap is constructer of Map
func NewMap() *Map {
	s := new(Map)
	s.tree = *NewTreap()
	s.size = 0
	return s
}

// Map for integer
type Map struct {
	tree Treap
	size int
}

func (s *Map) insert(k string, v int) int {
	xNode := s.tree.find(k)
	if xNode == nil {
		priority := rand.Int()
		s.tree.insert(k, v, priority)
		s.size++
	} else {
		xNode.value = v
	}
	return s.size
}

func (s *Map) find(k string) int {
	target := s.tree.find(k)
	if target != nil {
		return target.value
	}
	return 0
}

func (s *Map) delete(k string) {
	target := s.tree.find(k)
	if target != nil {
		s.tree.delete(k)
		s.size--
	}
}

func (s *Map) printRange(l, r string) {
	s.tree.printInorderWalk(l, r)
}

func main() {
	scanner.Split(bufio.ScanWords)

	nQueries := nextInt()
	treapMap := NewMap()
	for iQuery := 0; iQuery < nQueries; iQuery++ {
		queryType := nextInt()
		if queryType == 0 { // insert
			key := nextString()
			value := nextInt()
			treapMap.insert(key, value)
		} else if queryType == 1 { // find
			x := nextString()
			// fmt.Println(x)
			fmt.Println(treapMap.find(x))
		} else if queryType == 2 { // delete
			// fmt.Println("delete", x)
			x := nextString()
			treapMap.delete(x)
		} else if queryType == 3 { // dump(L, R)
			l := nextString()
			r := nextString()
			// fmt.Println(l, r)
			// fmt.Println(treapMap.tree.inorderTreeWalkV2(treapMap.tree.root))
			treapMap.printRange(l, r)
		}
	}
}



Measured memory_bytes: 47496