Summer is an employee of a certain company which tries to create viral trends. The company's latest scheme is to create a single word which will then be adopted by the "youth" and become a meme. Summer is put in charge of this project, and she decides the word should have exactly **lowercase** letters.

Excited by the possibility of a new internet sensation, of Summer's friends each make one suggestion as to what the word should contain. Specifically, each friend wants a **lowercase** letter to appear **exactly** times within the first letters of the word (inclusive).

Since Summer doesn't want to disappoint any of her friends, she asks you to help her create the next big thing!

#### Input Specification

The first line will contain two space separated integers and , which represent the length of the word Summer is to make, and the number of friends she has respectively.

The next lines will each contain a suggestion by one of her friends in the form `c x i`

.

#### Constraints

For all subtasks:

will always be a lowercase letter of the alphabet.

##### Subtask 1 [30%]

##### Subtask 2 [70%]

#### Output Specification

The output should be one line, consisting of a string which satisfies **all** suggestions of her friends. If there are multiple solutions, output any of them. If there are no solutions, output `-1`

.

#### Sample Input 1

```
7 4
a 2 2
c 2 7
b 3 7
c 1 5
```

#### Sample Output 1

`aacbbbc`

#### Explanation of Sample Output 1

The word must have its first two letters be `a`

to fulfill the first suggestion. The second suggestion is fulfilled by having `c`

appear at indices and . The third suggestion is fulfilled, with `b`

appearing at the , and indices. Finally, the last suggestion is fulfilled, as the letter `c`

only appears once in the first indices.

Other possible solutions include `aacbbcb`

, `aabcbbc`

, etc.

#### Sample Input 2

```
4 2
x 2 3
y 2 3
```

#### Sample Output 2

`-1`

#### Explanation of Sample Output 2

It is impossible for characters `x`

and `y`

to each appear twice in the first three characters.

## Comments

I think the checker might be broken for this question. It marks 'aabcd' as a wrong answer for input 4. However, I think that it is impossible for my algorithm to output something other than "-1" which is incorrect, because I have written my own validator to check my answers. Also, I managed to write a hack that outputs the input for test 4 to check, and it looks to me like my output is correct.

If the checker is not broken, I will be interested to see what wrong idea I had. Because I read the problem statement many times now, haha!

the case you're failing on is an edge case, unfortunately i can't give more details since the contest is ongoing and it's unfair to others. however, the case and its answer are both valid and correct (i checked manually).

I found my misunderstanding :(