34897번 - 수상한 문자열 스페셜 저지

문제

이루매는 강의실에 가던 도중에 길바닥에 떨어져 있는 종이를 발견했다. 그 종이를 주워보니 길이가 $N$인 문자열이 적혀 있었지만, 잉크가 번져 일부 문자를 알아볼 수 없게 되어 있었다. 확실히 알 수 있었던 것은 그 문자열이 알파벳 대문자 'A'와 'B'로 이루어져 있었다는 사실뿐이었다.

이루매는 이 수상한 문자열의 정체를 알아내기 위해 지나가던 $M$명의 사람들에게 도움을 요청했다. 각 사람들은 문자열에 대한 힌트를 주었고 모두 사실이라고 믿기로 했다. 힌트의 종류는 다음과 같다.

1. $S[i, j]$가 팰린드롬이다. $S[i, j]$란 1ドル \le i \le j \le N$인 정수 $i, j$에 대해서 $S$의 $i$번째 문자부터 $j$번째 문자까지를 포함하는 부분문자열을 뜻한다.
2. $S[i]$와 $S[j]$는 다르다.

이루매는 사람을 잘 믿기 때문에 모든 힌트들이 참이라고 가정한다.

당신의 임무는 이루매를 도와 이 힌트들을 모두 만족하는 문자열 $S$가 존재하는지를 알아내는 것이다.

입력

첫째 줄에 문자열 $S$의 길이 $N$과 힌트의 개수 $M$이 공백으로 구분되어 주어진다. ($ 1 \le N, M \le 200,000円 $)

둘째 줄부터 $M$개의 줄에 걸쳐 힌트가 한 줄에 하나씩 주어진다.

• 1ドル$ $i$ $j$: $S[i, j]$가 팰린드롬이다.
• 2ドル$ $i$ $j$: $S[i]$와 $S[j]$는 다르다.
• 모든 힌트에 대해 $ 1 \le i \le j \le N $이 성립한다.
• 모든 1번 힌트의 구간 길이의 합 $\sum(j-i+1) \le 200,000円$이 성립한다.

출력

첫째 줄에 모든 힌트를 만족하는 문자열 $S$를 만들 수 있다면 Yes, 그렇지 않다면 No를 출력한다.

답이 Yes인 경우, 둘째 줄에 문자열 $S$를 출력한다. 가능한 문자열이 여러 개인 경우에는 아무거나 출력한다.

제한

노트