F: Swap
問題
長さ $N$ の文字列 $S,\ T$ が与えられます.$S,\ T$ はそれぞれ 'o' , '.' の二種類の文字だけで構成されています.
あなたは $S$ に対して,以下の操作を行うことができます.
- 以下の条件を全て満たす整数対 $(l, r)$ を選択する.その後,$S[l]$ と $S[l + 1],S[r - 1]$ と $S[r]$ をそれぞれスワップする.
- $1 \leq l, r \leq N$
- $r - l \geq 3$
- $S[l] = S[r] =$ '.'
- $S[l + 1] = S[l + 2] = \dots = S[r - 1] =$ 'o'
何回か操作を繰り返したあと(0回でも可),文字列 S を T に変形することが可能か判定してください.
制約
- $1 \leq N \leq 100000$
- $|S| = |T| = N \ \ \ \ \ \ \ |S|$ , $|T|$ は文字列の長さ
- $S$ , $T$ は 'o', '.' の二種類の文字からのみ構成される。
入力形式
入力は以下の形式で与えられる。
$N$
$S$
$T$
出力
操作を何回か適用後( $0$ 回でも可), $S$ を $T$ に変形することが可能ならば Yes,どのように操作しても不可能ならば No を出力してください.また、末尾に改行も出力してください.
サンプル
サンプル入力 1
8
.oo.ooo.
o.o.oo.o
サンプル出力 1
Yes
以下の手順で操作を行うことで達成できます.
- $S$ = ".oo.ooo." : $(l, r) = (1, 4)$ を選択する.
- $S$ = "o..oooo." : $(l, r) = (4, 9)$ を選択する.
- $S$ = "o.o.oo.o" : $T$ と一致し,目的を達成.
サンプル入力 2
7
.ooooo.
oo.o.oo
サンプル出力 2
Yes
以下の手順で操作を行うことで達成できます.
- $S$ = ".ooooo." : $(l, r) = (1, 7)$ を選択する.
- $S$ = "o.ooo.o" : $(l, r) = (2, 6)$ を選択する.
- $S$ = "oo.o.oo" : $T$ と一致し,目的を達成.
サンプル入力 3
6
o.o.o.
ooo...
サンプル出力 3
No
操作を適用できる $(l, r)$ が存在しないため,$S$ を変形して $T$ にすることができません.
サンプル入力 4
9
.oo.oooo.
.oo.oooo.
サンプル出力 4
Yes
$1$ 回も変形させずに目的を達成できます
サンプル入力 5
11
.oooo.oooo.
oo.oo.oo.oo
サンプル出力 5
Yes
Note
Commentary