A - ノートの照合 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君と青木君は、同じ講義のノートをそれぞれ取っていました。しかし、二人とも途中で読み取れなかった部分があり、ノートには一部空欄があります。

講義で板書された内容は英小文字のみからなる N 文字の文字列でした。高橋君のノートを文字列 S、青木君のノートを文字列 T とします。S, T はいずれも N 文字からなり、読み取れなかった箇所は ? として記録されています。それ以外の箇所には英小文字が記録されていますが、書き写し間違いにより元の板書と異なる文字が記録されている可能性があります。

二人は互いのノートを見比べて、元の板書の復元を試みます。二人が一致して書き取れた文字は正しいと信じることにして、各位置 i（1 \leq i \leq N）について、S の i 文字目と T の i 文字目を比較し、以下のルールで復元後の i 文字目を決定します。

  • 両方とも同じ英小文字である場合、その文字を採用します。
  • 一方が ? でもう一方が英小文字である場合、その英小文字を採用します。
  • 両方とも ? である場合、復元できないため ? のまま残します。
  • 両方とも英小文字であるが互いに異なる場合、少なくとも一方のノートに書き写し間違いがあり正しい文字を判定できないため、矛盾を表す ! とします。

すべての位置について復元を行った結果の文字列を出力してください。また、復元結果に矛盾（!）が 1 箇所でも含まれるかどうかを判定し、含まれる場合は Yes を、含まれない場合は No を出力してください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • N は整数である。
  • S は英小文字および ? からなる長さ N の文字列である。
  • T は英小文字および ? からなる長さ N の文字列である。

入力

N
S
T
  • 1 行目には、文字列の長さを表す整数 N が与えられる。
  • 2 行目には、高橋君のノートを表す長さ N の文字列 S が与えられる。
  • 3 行目には、青木君のノートを表す長さ N の文字列 T が与えられる。

出力

2 行で出力せよ。

  • 1 行目には、復元した長さ N の文字列を出力せよ。各位置の文字は問題文中のルールに従って決定される。
  • 2 行目には、復元結果に ! が 1 箇所以上含まれる場合（矛盾がある場合）は Yes を、含まれない場合は No を出力せよ。

入力例 1

5
ab?de
a?cd?

出力例 1

abcde
No

入力例 2

6
abc?ef
axc?yf

出力例 2

a!c?!f
Yes

入力例 3

15
he??o?wor?d?abc
?ell??world?axc

出力例 3

hello?world?a!c
Yes

入力例 4

40
ab?dab?dab?dab?dab?dab?dab?dab?dab?dab?d
a?cda?cda?cda?cda?cda?cda?cda?cda?cda?cd

出力例 4

abcdabcdabcdabcdabcdabcdabcdabcdabcdabcd
No

入力例 5

1
?
?

出力例 5

?
No

Score : 233 pts

Problem Statement

Takahashi and Aoki each took notes during the same lecture. However, both of them had parts they couldn't read, so their notes contain some blanks.

The content written on the blackboard during the lecture was a string of N characters consisting only of lowercase English letters. Let string S represent Takahashi's notes and string T represent Aoki's notes. Both S and T consist of N characters, where parts that couldn't be read are recorded as ?. All other parts are recorded as lowercase English letters, but due to copying errors, some characters may differ from the original blackboard content.

The two compare each other's notes and attempt to reconstruct the original blackboard content. They decide to trust characters that both of them wrote down identically. For each position i (1 \leq i \leq N), they compare the i-th character of S with the i-th character of T and determine the i-th character of the reconstruction according to the following rules:

  • If both are the same lowercase English letter, adopt that letter.
  • If one is ? and the other is a lowercase English letter, adopt that lowercase English letter.
  • If both are ?, the character cannot be reconstructed, so it remains ?.
  • If both are lowercase English letters but differ from each other, at least one of the notes contains a copying error and the correct character cannot be determined, so it becomes ! to represent a contradiction.

Output the resulting string after performing the reconstruction for all positions. Also, determine whether the reconstruction result contains at least one contradiction (!), and output Yes if it does, or No if it does not.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • N is an integer.
  • S is a string of length N consisting of lowercase English letters and ?.
  • T is a string of length N consisting of lowercase English letters and ?.

Input

N
S
T
  • The first line contains an integer N representing the length of the strings.
  • The second line contains the string S of length N representing Takahashi's notes.
  • The third line contains the string T of length N representing Aoki's notes.

Output

Output in 2 lines.

  • On the first line, output the reconstructed string of length N. The character at each position is determined according to the rules described in the problem statement.
  • On the second line, output Yes if the reconstruction result contains at least one ! (i.e., there is a contradiction), or No otherwise.

Sample Input 1

5
ab?de
a?cd?

Sample Output 1

abcde
No

Sample Input 2

6
abc?ef
axc?yf

Sample Output 2

a!c?!f
Yes

Sample Input 3

15
he??o?wor?d?abc
?ell??world?axc

Sample Output 3

hello?world?a!c
Yes

Sample Input 4

40
ab?dab?dab?dab?dab?dab?dab?dab?dab?dab?d
a?cda?cda?cda?cda?cda?cda?cda?cda?cda?cd

Sample Output 4

abcdabcdabcdabcdabcdabcdabcdabcdabcdabcd
No

Sample Input 5

1
?
?

Sample Output 5

?
No