L - Deterministic League Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

1 から N までの番号がついた N 人の人がいます。それぞれの人の強さは 1 以上 N 以下の整数で表され、強さは全員異なります。

2 人が対戦すると、強さの値が大きい方が必ず勝利します。

この N 人で総当たり戦をした際の途中結果の表が与えられます。これは N 個の文字列 S_1,S_2,\ldots,S_N として表され、 以下の条件を満たします。

  • S_i の j 文字目が o のとき：人 i と人 j が対戦し、人 i が勝利した。
  • S_i の j 文字目が x のとき：人 i と人 j が対戦し、人 j が勝利した。
  • S_i の j 文字目が ? のとき：人 i と人 j はまだ対戦していない。
  • S_i の j 文字目が - のとき： i=j である。

矛盾の生じないように S_1,S_2,\ldots,S_N の ? を o か x に置き換えてください。ただし、どのように置き換えても矛盾が生じる場合は、そのことを指摘してください。

より厳密には、以下の条件を満たすように S_1,S_2,\ldots,S_N の ? を o か x に置き換えられるか判定し、置き換えられる場合はその一例を示してください。

  • 以下の条件を満たす (1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) が存在する。
    • i\neq j を満たす整数の組 (i,j) に対し、 P_i>P_j ならば S_i の j 文字目は o で、 P_i<P_j ならば S_i の j 文字目は x である。

制約

  • 1\le N\le 10^3
  • N は整数
  • S_1,S_2,\ldots,S_N は o 、x 、? 、- からなる長さ N の文字列
  • S_i の j 文字目が o ならば S_j の i 文字目は x
  • S_i の j 文字目が x ならば S_j の i 文字目は o
  • S_i の i 文字目は -
  • i\neq j ならば S_i の j 文字目は - ではない

入力

入力は以下の形式で標準入力から与えられる。

N
S_1
S_2
\vdots
S_N

出力

どのように置き換えても矛盾する場合は No を出力せよ。

矛盾しないような置き換え方が存在する場合は、まず Yes と一行に出力し、その後に矛盾のないように置き換えた後の S_1,S_2,\ldots,S_N を改行区切りで順に出力せよ。

条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

4
-?x?
?-o?
ox-?
???-

出力例 1

Yes
-xxx
o-oo
ox-o
oxx-

例えば、人 1,2,3,4 の強さをそれぞれ 1,4,3,2 とすると途中結果の表と勝敗に矛盾が生じません。

その他にも、例えば以下の出力も条件を満たします。

Yes
-xxx
o-ox
ox-x
ooo-

入力例 2

4
-oxo
x-xx
oo-o
xox-

出力例 2

Yes
-oxo
x-xx
oo-o
xox-

? が存在しない場合もあります。

入力例 3

3
-ox
x-o
ox-

出力例 3

No

人 1,2,3 の強さをどのように決めても途中結果の表と矛盾が生じます。

入力例 4

6
-x?x??
o-o??o
?x-???
o??-o?
???x-o
?x??x-

出力例 4

Yes
-xxxxx
o-oxxo
ox-xxx
ooo-oo
ooox-o
oxoxx-

Problem Statement

There are N people numbered 1 through N. The strength of each person is represented by an integer between 1 and N, and all strengths are distinct.

If two people battles, the one with the larger strength always wins.

You are given preliminary results of a round-robin competition between the N people. They are represented by N strings S_1,S_2,\ldots, and S_N and satisfy the following conditions:

  • If the j-th character of S_i is o: person i has battled person j and won.
  • If the j-th character of S_i is x: person i has battled person j and lost.
  • If the j-th character of S_i is ?: person i has not battled person j yet.
  • If the j-th character of S_i is -: it holds that i=j.

Fill each ? in S_1,S_2,\ldots, and S_N with o or x consistently. If any assignment causes a contradiction, report that fact.

More precisely, determine if one can replace each occurrence of ? in S_1,S_2,\ldots, and S_N with either o or x subject to the following condition, and print one such assignment if it is possible.

  • There exists a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) such that:
    • for every integer pair (i,j) with i\neq j, the j-th character of S_i is o if P_i>P_j and x if P_i<P_j.

Constraints

  • 1\le N\le 10^3
  • N is an integer.
  • Each of S_1,S_2,\ldots, and S_N is a string of length N consisting of o, x, ?, and -.
  • If the j-th character of S_i is o, then the i-th character of j is x.
  • If the j-th character of S_i is x, then the i-th character of j is o.
  • The i-th character of S_i is -.
  • If i\neq j, then the j-th character of S_i is not -.

Input

The input is given from Standard Input in the following format:

N
S_1
S_2
\vdots
S_N

Output

Print No if any assignment causes a contradiction.

If there is a consistent assignment, first print Yes in a single line, and then S_1,S_2,\ldots, and S_N resulting from a consistent assignment, with newlines in between.

If there are multiple conforming solutions, printing any of them is accepted.

Sample Input 1

4
-?x?
?-o?
ox-?
???-

Sample Output 1

Yes
-xxx
o-oo
ox-o
oxx-

For example, it is consistent with the preliminary results to assume that the strengths of people 1,2,3, and 4 are 1,4,3, and 2, respectively.

Another possible assignment is:

Yes
-xxx
o-ox
ox-x
ooo-

Sample Input 2

4
-oxo
x-xx
oo-o
xox-

Sample Output 2

Yes
-oxo
x-xx
oo-o
xox-

There may be no ?.

Sample Input 3

3
-ox
x-o
ox-

Sample Output 3

No

Any assignment of strengths of people 1,2, and 3 is inconsistent with the preliminary results.

Sample Input 4

6
-x?x??
o-o??o
?x-???
o??-o?
???x-o
?x??x-

Sample Output 4

Yes
-xxxxx
o-oxxo
ox-xxx
ooo-oo
ooox-o
oxoxx-