In a city parade, there is a long banner with n empty positions.

There are q groups participating in the parade. Each group supports one lowercase English letter from a to z.

For each group, you are given l, r, and c. This means the group gives one vote to letter c for every position from l to r.

After all votes are counted, each position of the banner will show the letter with the maximum number of votes at that position.

If more than one letter has the same maximum number of votes, choose the lexicographically smallest letter.

Your task is to print the final banner.

The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the length of the banner and the number of groups.

Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and one lowercase English letter KaTeX can only parse string typed expression.

Print a single string of length KaTeX can only parse string typed expression — the final banner after all votes are counted.