The Black Pawn's Revenge Objective

The black pawn wants revenge. Plot out its last attack.

Rules

The black pawn (L) starts at the top row and moves downwards to the bottom row. Maximise points taken, indicating the path with X. Pawns (P) are 1, bishops (B) and knights (N) 3, rooks (R) 5, and queens (Q) 9. There won't be any kings in the input.

If there is more than one path that has the maximum amount of points, output any of those paths. There will not be any situations where the pawn cannot reach the bottom row.

Examples

Input:

----L---
-----P--
------P-
--R--P-Q
----P-P-
---P-P-P
--P-N---
-P------


Output:

----L---
-----X--
------X-
--R--P-X
----P-X-
---P-X-P
--P-X---
-P--X---


Input:

--L-----
-P------
P-------
-P------
P--Q----
-P------
P-------
-P------


Output:

--L-----
-PX-----
P-X-----
-PX-----
P--X----
-P-X----
P--X----
-P-X----
Python, 332

def s(m,l,p):
 if not m:return 1
 b=m[0]+'-';z=filter(lambda i:(b[i]=='-')==(i==l),[l,l-1,l+1])
 if not z:return 0
 g=lambda i:s(m[1:],i,0)+[0,1,3,3,5,9]['-PBNRQ'.index(b[i])];i=max(z,key=g)
 if p:print m[0][:i]+'X'+m[0][i+1:];s(m[1:],i,p)
 return g(i)
import sys
t=sys.stdin.read().split('\n')
print t[0]
s(t[1:],t[0].index('L'),1)