package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"

	"sort"
	"strconv"
	"strings"
)

//  長い入力を読む
func ReadLongLines(times int) ([]string, error) {
	result := make([]string, times)
	reader := bufio.NewReader(os.Stdin)
	buffer := bytes.NewBuffer(make([]byte, 0))
	readBytes := int64(2)
	for i := 0; i < times; i++ {
		for {
			readBuf, isPrefix, err := reader.ReadLine()
			// fmt.Printf("Reader.Read: %d\n", len(readBuf))
			readBytes += int64(len(readBuf) + 1)
			if err != nil {
				if err == io.EOF {
					fmt.Println("EOF")
					break
				} else {
					return result, err
				}
			}
			_, err = buffer.Write(readBuf)
			if err != nil {
				return result, err
			}
			// end of line
			if !isPrefix {
				result[i] = buffer.String()
				buffer.Reset()
				// reader = bufio.NewReader(os.Stdin)
				break
			}
		}
	}
	// 先読みしてしまうようなので、戻しておく
	os.Stdin.Seek(-int64(reader.Buffered()), os.SEEK_CUR)
	return result, nil
}

// 出力 for 競プロ
type Console struct {
	writer *bufio.Writer
}

func NewConsole() Console {
	return Console{bufio.NewWriter(os.Stdout)}
}
func (this *Console) Printf(format string, a ...interface{}) {
	fmt.Fprintf(this.writer, format, a...)
}
func (this *Console) Println(s string) {
	fmt.Fprintln(this.writer, s)
}
func (this *Console) Close() {
	this.Flush()
}
func (this Console) Flush() {
	this.writer.Flush()
}

func PrintList(list []int) {
	con := NewConsole()
	defer con.Flush()
	for i := range list {
		if i == 0 {
			con.Printf("%d", list[i])
		} else {
			con.Printf(" %d", list[i])
		}
	}
	con.Println("")
}

func GetFirst(s string) rune {
	r := []rune(s)
	return r[0]
}
func GetSecond(s string) rune {
	if 2 <= len(s) {
		r := []rune(s)
		return r[1]
	} else {
		return '`'
	}
}

type Map struct {
	maps map[rune]map[rune]map[string][]int
}

func NewMap() Map {
	maps := make(map[rune]map[rune]map[string][]int)
	for i := 'a'; i <= 'z'; i++ {
		maps[i] = make(map[rune]map[string][]int)
		for j := 'a'; j <= 'z'; j++ {
			maps[i][j] = make(map[string]([]int))
		}
		maps[i]['`'] = make(map[string][]int)
	}
	return Map{maps}
}

func (this *Map) Insert(key string, val int) {
	arr := this.maps[GetFirst(key)][GetSecond(key)][key]
	arr = append(arr, val)
	// sort.Slice(arr, func(lhs, rhs int) bool {
	// 	return arr[lhs] < arr[rhs]
	// })
	this.maps[GetFirst(key)][GetSecond(key)][key] = arr
}

func (this *Map) Get(key string) []int {
	v, ok := this.maps[GetFirst(key)][GetSecond(key)][key]
	if ok {
		return v
	} else {
		return []int{}
	}
}

func (this *Map) Delete(key string) {
	delete(this.maps[GetFirst(key)][GetSecond(key)], key)
}

type KeyValues struct {
	key   string
	value []int
}

func (this *Map) Dump(lKey string, rKey string) []KeyValues {
	result := make([]KeyValues, 0, 32)
	lFirstRune := GetFirst(lKey)
	lSecondRune := GetSecond(lKey)
	rFirstRune := GetFirst(rKey)
	rSecondRune := GetSecond(rKey)

	// fmt.Printf("[%c][%c]~[%c][%c]\n", lFirstRune, lSecondRune, rFirstRune, rSecondRune)
	for r1 := lFirstRune; r1 <= rFirstRune; r1++ {
		// other
		r2 := '`'
		last := 'z'
		// first
		if r1 == lFirstRune {
			r2 = lSecondRune
		}
		// last
		if r1 == rFirstRune {
			last = rSecondRune
		}
		for ; r2 <= last; r2++ {
			// fmt.Printf("[%c][%c] ", r1, r2)
			// fmt.Println(this.maps[r1][r2])
			for k, v := range this.maps[r1][r2] {
				if lKey <= k && k <= rKey {
					result = append(result, KeyValues{k, v})
				}
			}
		}
	}

	sort.Slice(result, func(lhs, rhs int) bool {
		return result[lhs].key < result[rhs].key
	})
	return result
}

func main() {
	con := NewConsole()
	defer con.Flush()

	// create list
	var n int
	fmt.Scanf("%d", &n)

	m := NewMap()
	lines, _ := ReadLongLines(n)
	for i := range lines {
		args := strings.Split(lines[i], " ")
		command, _ := strconv.Atoi(args[0])

		switch command {
		case 0: //insert
			k := args[1]
			v, _ := strconv.Atoi(args[2])
			m.Insert(k, v)
		case 1: //get
			k := args[1]
			v := m.Get(k)
			for i := range v {
				con.Printf("%d\n", v[i])
			}
		case 2: // delete
			k := args[1]
			m.Delete(k)
		case 3: // dump
			lk := args[1]
			rk := args[2]
			result := m.Dump(lk, rk)
			for i := range result {
				for j := range result[i].value {
					con.Printf("%s %d\n", result[i].key, result[i].value[j])
				}
			}
		}

	}
}



Measured memory_bytes: 56084