Text Pieces

There is a secret string of length $N$, consisting of lowercase English letters. However, the full string is unknown to you.

Instead, you are provided with $Q$ hints of the string. Each hint contains information about a partial piece of the string:

• An integer $B_i$: the starting position ($0$-based index) of the piece.
• An integer $K_i$: the length of the piece.
• A substring $S_i$ of length $K_i$: the partial piece.

Each hint indicates that the string $S_i$, or its reversed version, appears at position $B_i$ in the secret string.

Your task is to determine whether there exists a string of length $N$ that is consistent with all the given hints
If such a string exists, output any valid string. Otherwise, report that the hints are inconsistent.

Input data

The first line of the input contains two integers $N$ and $Q$ - the length of the unknown string and the number of hints, respectively.

Each of the next $Q$ lines contains the integers $B_i$ and $K_i$, and the string $S_i$ of length $K_i$, describing a hint.
No pair of hints correspond to the exact same substring of the hidden string, that is for all $i \ne j$, either $B_i \ne B_j$ or $K_i \ne K_j$.

Output data

Print NO in a single line if there is no string that satisfies the given conditions. Otherwise, print YES on the first line, followed by one such valid string on the next line.

Constraints and clarifications

• $1 \le N \le 20 \ 000$.
• $1 \le Q \le 20 \ 000$.
• $0 \le B_i \le N-1$, and $B_i + K_i \le N$ for each $i=0,\ldots,Q-1$.
• $B_i \ne B_j$ or $K_i \ne K_j$ for all $i \ne j$.
• $1 \le K_i \le 150$ for each $i=0,\ldots,Q-1$.
• Each $K_i$ consists of lowercase English letters.

Example 1

stdin

11 5
0 2 ii
7 4 yrag
1 3 toi
6 4 ngar
3 4 thun

stdout

YES
iiothungary

Example 2

stdin

7 3
0 5 cabac
1 3 aba
4 3 dbd

stdout

NO