本題測資更新中，請稍後再回來

出處: 2022 NPSC網際網路程式設計大賽高中組初賽pA

巫醫巫醫是個傳奇人物，聽說他遇到很困難的問題的時候，都只要喊一聲咒語巫醫巫醫殿殿殿，問題就會被解決！於是，小 \(Y\) 給了他一個挑戰。

有一個 \(N × N\) 的地圖，上面充滿了危險，在這個地圖上面有四種土地：

1. 劇毒之地，上面充滿了恐怖的毒氣，任何人只要一走到這塊地就會立刻死掉。
2. 人人之地，上面有一個無辜的人，想要趕快回家。
3. 超級傳送門，可憐的人只要走上來就會被傳送出這個危險的地圖。
4. 安全之地，原本是劇毒之地，經過巫醫巫醫的法術之後，變成可以行走的地方。

而這個地圖是四連通的，也就是說無辜的人可以從座標 \((i, j)\) 走到以下四個座標：

1. \((i + 1, j)\)
2. \((i - 1, j)\)
3. \((i, j + 1)\)
4. \((i, j - 1)\)

而在地圖之外，全部都是可怕的無底洞，所以你只要走到一個超出範圍的座標 \((x, y)\) 滿足\(x \notin [1, N]\) 或 \(y \notin [1, N]\) 那你就會立刻掉下去摔死。註：\(n \notin [1, N]\) 表示 \(n < 1\) 或 \(n > N\)。

為了拯救無辜的人，巫醫巫醫必須施展法術，每次施展法術都只能把一個劇毒之地的毒氣消除，變成安全之地，讓人可以安全的走在這塊地上。巫醫巫醫希望在施展法術過後，每個無辜的人，都可以不經過劇毒之地，走到超級傳送門。

但是巫醫巫醫的法術能量有限，他最多只能施展 \(2 \times 10^6\) 次法術，請你幫他決定好要在哪些地方施法術，才能夠讓所有無辜的人都能夠安全抵達超級傳送門。

以下為範測說明，深藍的格子是劇毒之地，天藍色的格子是人人之地，黃色的格子是超級傳送門，紫色的格子是安全之地。

下圖是範測 \(1\) 原本的樣子

下圖是範測 \(1\) 施展過法術的樣子

輸入格式

輸入的第一行有一個正整數 \(N\)。

接下來 \(N\) 行，每行都有一個長度為 \(N\) 的字串 \(S_i\) ，其中 \(S_{i,j}\) 代表地圖上座標 \((i, j)\) 的土地類型。

• \(1 ≤ N ≤ 4 × 10^3\)
• \(S_{i,j} ∈ \{ ., P, X \}\)，其中 \(. P X\) 分別代表劇毒之地、人人之地和超級傳送門
• 保證只有 \(S_{1,1} = X\)，且 \(S_{1,1} = X\)
• 最多只會有 \(2 \times 10^5\) 個人人之地

輸出格式

請輸出 \(N\) 行，每一行一個長度為 \(N\) 的字串 \(S^′_i\) 代表施展過法術之後的地圖。字元 \(O\) 代表有施展法術的土地，其他規則和輸入一樣。如果你的地圖上面有超過 \(2 \times 10^6\) 個土地被施展法術、有土地被不合法的施展法術、或是有一個未被施展法術的土地與原本不同，那你會得到 WrongAnswer 的結果。注意到如果有多組解，任意一組都會得到 Accepted。

範例輸入

5
X..P.
.....
P....
.....
....P

範例輸出

XOOPO
OOOOO
POOOO
OOOOO
OOOOP

Hint

你可以利用以下的東西幫助思考。