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!
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.
For all subtasks:
will always be a lowercase letter of the alphabet.
Subtask 1 [30%]
Subtask 2 [70%]
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
Sample Input 1
7 4 a 2 2 c 2 7 b 3 7 c 1 5
Sample Output 1
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
Sample Input 2
4 2 x 2 3 y 2 3
Sample Output 2
Explanation of Sample Output 2
It is impossible for characters
y to each appear twice in the first three characters.