Nightmare Brother

Interview

Time limit2sMemory limit1024 MB

Summary

Given N hints placing substrings in a length-M string, with at most one hint false, print the unique possible string, -1 if none exists, or -2 if several do.

Level: Medium5 of 10
Topics: Brute force, String, Implementation
Solved: No attempts yet

Problem

Your brother has a string $S$ of length $M$ with indices from $1$ to $M$ . You want to know exactly what string $S$ is. To help you, he gives you $N$ hints. Hint $i$ is an integer $X_i$ and a string $T_i$ , meaning that $T_i$ appears as a substring of $S$ starting at index $X_i$ . All hints are unique: there are no hints $i$ and $j$ with $i \ne j$ such that $X_i = X_j$ and $T_i = T_j$ .

Your brother is known to be mischievous. He tells you that at most one of the $N$ hints is false, but he does not say which one.

A string $S$ is a possible solution if and only if there is a set of at least $N - 1$ hints (assumed true) such that $S$ is the only string consistent with all hints in that set.

Find a possible solution. If there is none, output -1. If there is more than one, output -2.

Input

The first line contains two integers $N$ and $M$ ( $1 \le N \le 100$ , $1 \le M \le 100$ ), the number of hints and the length of the string. Each of the next $N$ lines contains an integer $X_i$ and a string $T_i$ ( $1 \le X_i$ , $1 \le |T_i|$ , $X_i + |T_i| - 1 \le M$ ). The string $T_i$ consists only of uppercase letters. No two hints have the same $X_i$ and the same $T_i$ .

Output

If there is exactly one possible solution, print the string $S$ on a single line. If there is no possible solution, print -1 on a single line. If there is more than one possible solution, print -2 on a single line.

Examples4

Example 1

Input

3 11
5 JAKARTA
1 ICPC
3 BINUS

Expected output

ICPCJAKARTA

Example 2
Input
```
3 9
6 EX
8 AM
1 FINAL
```
Expected output
```
FINALEXAM
```
Example 3
Input
```
3 8
1 GRAD
5 UAL
6 ATE
```
Expected output
```
-1
```
Example 4
Input
```
3 5
1 BIN
4 US
4 OM
```
Expected output
```
-2
```