← Home
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

type Page struct {
	p     int
	words []string
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	k, _ := strconv.Atoi(scanner.Text())

	pages := make([]Page, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		pages[i].p, _ = strconv.Atoi(scanner.Text())
		pages[i].words = make([]string, k)
		for j := 0; j < k; j++ {
			scanner.Scan()
			pages[i].words[j] = scanner.Text()
		}
	}

	sort.Slice(pages, func(i, j int) bool {
		return pages[i].p < pages[j].p
	})

	var allWords []string
	for _, page := range pages {
		allWords = append(allWords, page.words...)
	}

	chars := make(map[byte]bool)
	for _, w := range allWords {
		for i := 0; i < len(w); i++ {
			chars[w[i]] = true
		}
	}

	adj := make(map[byte]map[byte]bool)
	for c := range chars {
		adj[c] = make(map[byte]bool)
	}

	for i := 0; i < len(allWords)-1; i++ {
		w1 := allWords[i]
		w2 := allWords[i+1]

		minLen := len(w1)
		if len(w2) < minLen {
			minLen = len(w2)
		}

		diff := false
		for j := 0; j < minLen; j++ {
			if w1[j] != w2[j] {
				adj[w1[j]][w2[j]] = true
				diff = true
				break
			}
		}
		if !diff && len(w1) > len(w2) {
			fmt.Println("IMPOSSIBLE")
			return
		}
	}

	inDegree := make(map[byte]int)
	for c := range chars {
		inDegree[c] = 0
	}
	for _, edges := range adj {
		for v := range edges {
			inDegree[v]++
		}
	}

	var queue []byte
	for c, deg := range inDegree {
		if deg == 0 {
			queue = append(queue, c)
		}
	}

	var result []byte
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		result = append(result, u)

		for v := range adj[u] {
			inDegree[v]--
			if inDegree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}

	if len(result) != len(chars) {
		fmt.Println("IMPOSSIBLE")
		return
	}
	fmt.Println(string(result))
}