В самолёте есть n рядов мест. Если смотреть на ряды сверху, то в каждом ряду есть 3 места слева, затем проход между рядами, затем 4 центральных места, затем ещё один проход между рядами, а затем ещё 3 места справа.

Известно, что некоторые места уже заняты пассажирами. Всего есть два вида пассажиров — статусные (те, которые часто летают) и обычные. 

Перед вами стоит задача рассадить ещё k обычных пассажиров так, чтобы суммарное число соседей у статусных пассажиров было минимально возможным. Два пассажира считаются соседями, если они сидят в одном ряду и между ними нет других мест и прохода между рядами. Если пассажир является соседним пассажиром для двух статусных пассажиров, то его следует учитывать в сумме соседей дважды.


-----Входные данные-----

В первой строке следуют два целых числа n и k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10·n) — количество рядов мест в самолёте и количество пассажиров, которых нужно рассадить.

Далее следует описание рядов мест самолёта по одному ряду в строке. Если очередной символ равен '-', то это проход между рядами. Если очередной символ равен '.', то это свободное место. Если очередной символ равен 'S', то на текущем месте будет сидеть статусный пассажир. Если очередной символ равен 'P', то на текущем месте будет сидеть обычный пассажир. 

Гарантируется, что количество свободных мест не меньше k. Гарантируется, что все ряды удовлетворяют описанному в условии формату.


-----Выходные данные-----

В первую строку выведите минимальное суммарное число соседей у статусных пассажиров.

Далее выведите план рассадки пассажиров, который минимизирует суммарное количество соседей у статусных пассажиров, в том же формате, что и во входных данных. Если в свободное место нужно посадить одного из k пассажиров, выведите строчную букву 'x' вместо символа '.'. 


-----Примеры-----
Входные данные
1 2
SP.-SS.S-S.S

Выходные данные
5
SPx-SSxS-S.S

Входные данные
4 9
PP.-PPPS-S.S
PSP-PPSP-.S.
.S.-S..P-SS.
P.S-P.PP-PSP

Выходные данные
15
PPx-PPPS-S.S
PSP-PPSP-xSx
xSx-SxxP-SSx
P.S-PxPP-PSP



-----Примечание-----

В первом примере нужно посадить ещё двух обычных пассажиров. Для минимизации соседей у статусных пассажиров, нужно посадить первого из них на третье слева место, а второго на любое из оставшихся двух мест, так как независимо от выбора места он станет соседом двух статусных пассажиров. 

Изначально, у статусного пассажира, который сидит на самом левом месте уже есть сосед. Также на четвёртом и пятом местах слева сидят статусные пассажиры, являющиеся соседями друг для друга (что добавляет к сумме 2).

Таким образом, после посадки ещё двух обычных пассажиров, итоговое суммарное количество соседей у статусных пассажиров станет равно пяти.

Difficulty: interview

Starter code:

Solutions:
n, k = list(map(int, input().split()))
plain = list()

for i in range(n):
    plain.append(list(input()))

fr = {
    "0": list(),
    "1": list(),
    "2": list(),
}
for i in range(n):
    for j in range(12):
        if plain[i][j] != ".":
            continue

        st = 0
        if j > 0 and plain[i][j - 1] == "S":
            st += 1
        if j < 11 and plain[i][j + 1] == "S":
            st += 1

        fr[str(st)].append((i, j))

for i in range(k):
    if len(fr["0"]):
        x, y = fr["0"].pop()
    elif len(fr["1"]):
        x, y = fr["1"].pop()
    else:
        x, y = fr["2"].pop()
    plain[x][y] = "x"


result = 0
for i in range(n):
    for j in range(12):
        if plain[i][j] != "S":
            continue
        if j > 0 and plain[i][j - 1] in ("S", "x", "P"):
            result += 1
        if j < 11 and plain[i][j + 1] in ("S", "x", "P"):
            result += 1

print(result)
for i in range(n):
    print("".join(plain[i]))


n, k = map(int, input().split())

ss = []

r = [0, 0, 0]

t = 0

PASSENGERS = ('x', 'P', 'S')

# - is 0
# . is 1
# P is 10
# S is 11

for i in range(n):
    s = input()
    for c in s:
        ss.append(c)
    ss.append('\n')

for i in range(len(ss)):
    if ss[i] == '.':
        rank = 0
        if i > 0 and ss[i-1] == 'S': rank += 1
        if i+1 < len(ss) and ss[i+1] == 'S': rank += 1
        ss[i] = str(rank)
        r[rank] += 1

if k > r[0]:
    k -= r[0]
    if k > r[1]:
        k -= r[1]
        r[2] = k
    else:
        r[1] = k
        r[2] = 0
else:
    r[0] = k
    r[1] = 0
    r[2] = 0

i = 0
while r[0] > 0:
    while ss[i] != '0':
        i += 1
    ss[i] = 'x'
    r[0] -= 1

i = 0
while r[1] > 0:
    while ss[i] != '1':
        i += 1
    ss[i] = 'x'
    r[1] -= 1

i = 0
while r[2] > 0:
    while ss[i] != '2':
        i += 1
    ss[i] = 'x'
    r[2] -= 1

for i in range(len(ss)):
    if ss[i] in ('0', '1', '2'):
        ss[i] = '.'

for i in range(len(ss)):
    if ss[i] == 'S':
        if i > 0 and (ss[i-1] in PASSENGERS):
            t += 1
        if i+1 < len(ss) and (ss[i+1] in PASSENGERS):
            t += 1

print(t)
print(''.join(ss))

from collections import Counter
n,k=list(map(int,input().split()))
#n,k=1,2
a=set()
c=[set() for i in range(3)]
b=set()
z=0
for i in range(n):
    s=input()
    for i0 in range(len(s)):
        if s[i0]=='.':
            a.add(tuple([i,i0]))
        elif s[i0]=='S':
            b.add(tuple([i,i0]))
    for i0 in range(len(s)):
        if s[i0]=='.':
            zz=0
            if tuple([i,i0+1]) in b:
                zz=zz+1
            if tuple([i,i0-1]) in b:
                zz=zz+1
            c[zz].add(tuple([i,i0]))
c=list(c[0])+list(c[1])+list(c[2])
for i in range(k):
    a.remove(c[i])
for i in b:
    if (i[1]!=2)and(i[1]!=7)and(i[1]!=11):
        if not(tuple([i[0],i[1]+1])in a):
            z=z+1
    if (i[1]!=4)and(i[1]!=9)and(i[1]!=0):
        if not(tuple([i[0],i[1]-1])in a):
            z=z+1
c=set(c)

print(z)
for i in range(n):
    s=''
    for i0 in range(12):
        if i0==3 or i0==8:
            s=s+'-'
        elif tuple([i,i0])in a:
            s=s+'.'
        elif tuple([i,i0])in b:
            s=s+'S'
        elif tuple([i,i0])in c:
            s=s+'x'
        else:
            s=s+'P'
    print(s)

n, k = [int(i) for i in input().split()]
rows = ['P' + input() + 'P' for i in range(n)]

def try_good(rows):
	for j in range(len(rows)):
		for i in range(1, len(rows[j]) - 1):
			if rows[j][i] == '.':
				if rows[j][i - 1] != 'S' and rows[j][i + 1] != 'S':
					rows[j] = rows[j][:i] + 'x' + rows[j][i + 1:]
					return True
	return False

def try_medium(rows):
	for j in range(len(rows)):
		for i in range(1, len(rows[j]) - 1):
			if rows[j][i] == '.':
				if rows[j][i - 1] != 'S' or rows[j][i + 1] != 'S':
					rows[j] = rows[j][:i] + 'x' + rows[j][i + 1:]
					return True
	return False

def try_bad(rows):
	for j in range(len(rows)):
		for i in range(1, len(rows[j]) - 1):
			if rows[j][i] == '.':
				rows[j] = rows[j][:i] + 'x' + rows[j][i + 1:]
				return True
	return False

for i in range(k):
	if try_good(rows) == True:
		continue
	if try_medium(rows) == True:
		continue
	try_bad(rows)

ans = 0
for r in rows:
	for i in range(len(r)):
		if r[i] == 'S':
			if i > 1 and r[i - 1] != '.' and r[i - 1] != '-':
				ans += 1
			if i < len(r) - 2 and r[i + 1] != '.' and r[i + 1] != '-':
				ans += 1

print(ans)
for r in rows:
	print(r[1:-1])	


n, k = (int(s) for s in input().split())
rows = []
for i in range(n):
    rows.append([c for c in input()])

def nbcnt(row, col):
    res = 0
    if col != 0 and rows[row][col - 1] == 'S':
        res += 1
    if col != 11 and rows[row][col + 1] == 'S':
        res += 1
    return res

for c in range(3):
    for i in range(n):
        for j in range(12):
            if k != 0 and rows[i][j] == '.' and nbcnt(i, j) == c:
                rows[i][j] = 'x'
                k -= 1

res = 0
for i in range(n):
    for j in range(12):
        if rows[i][j] != '.' and rows[i][j] != '-':
            res += nbcnt(i, j)

print(res)

for i in range(n):
    print("".join(rows[i]))


def insertp():
    x,y = 0,0
    min = 3
    for i in range(n):
        for j in range(12):
            if a[i][j] == '.':
                if j != 0 and j != 11:
                    if a[i][j-1] != 'S':
                        if a[i][j+1] != 'S':
                            a[i][j] = 'x'
                            return 0
                        else:
                            if min > 1:
                                min = 1
                                x, y = i, j
                    else:
                        if a[i][j+1] != 'S':
                            if min > 1:
                                min = 1
                                x, y = i, j
                        else:
                            if min > 2:
                                min = 2
                                x,y = i, j
                elif j == 0:
                    if a[i][j+1] != 'S':
                        a[i][j] = 'x'
                        return 0
                    else:
                        if min > 1:
                            min = 1
                            x, y = i, j
                else:
                    if a[i][j-1] != 'S':
                        a[i][j] = 'x'
                        return 0
                    else:
                        if min > 1:
                            min = 1
                            x, y = i, j
    a[x][y] = 'x'
    return min

n, k = map(int, input().split())
a = [list(input()) for i in range(n)]
ans = 0

for i in range(n):
    for j in range(12):
        if a[i][j] == 'S':
            if j != 0 and j != 11:
                if a[i][j-1] == 'P' or a[i][j-1] == 'S':
                    ans += 1
                if a[i][j+1] == 'P' or a[i][j+1] == 'S':
                    ans += 1
            elif j == 0:
                if a[i][j+1] == 'P' or a[i][j+1] == 'S':
                    ans += 1
            else:
                if a[i][j-1] == 'P' or a[i][j-1] == 'S':
                    ans += 1
    
for i in range(k):
    ans += insertp()

print(ans)
for i in range(n):
    for j in range(12):
        print(a[i][j], end = '')
    print()


n, k = map(int, input().split())
a = []
s0 = []
s1 = []
s2 = []
ans = 0
for i in range(n):
    s = list(input())
    a.append(s)
    for j in range(12):
        if s[j] == '.':
            if j == 0:
                if s[j+1] == 'S':
                    s1.append((i,j))
                else:
                    s0.append((i,j))
            elif j == 11:
                if s[j-1] == 'S':
                    s1.append((i,j))
                else:
                    s0.append((i,j))
            else:
                if s[j-1] == 'S' and s[j+1] == 'S':
                    s2.append((i,j))
                elif s[j-1] != 'S' and s[j+1] != 'S':
                    s0.append((i,j))
                else:
                    s1.append((i, j))
        if s[j] == 'S':
            if j > 0 and (s[j-1] == 'P' or s[j-1] == 'S'):
                ans += 1
            if j < 11 and (s[j+1] == 'P' or s[j+1] == 'S'):
                ans += 1
p0=0
p1=0
p2=0
for g in range(k):
    if p0 < len(s0):
        i,j = s0[p0]
        p0+=1
        a[i][j] = 'x'
    elif p1 < len(s1):
        i,j = s1[p1]
        p1+=1
        a[i][j] = 'x'
        ans+=1
    else:
        i,j = s2[p2]
        p2+=1
        a[i][j] = 'x'
        ans+=2
print(ans)
for s in a:
    print(''.join(s))

n, k = (int(i) for i in input().split())
z = [[i for i in input()] for i in range(n)]
a1 = []
a2 = []
a3 = []
r = 0
for i in range(n):
    for j in range(12):
        t = 0
        t = (j != 0 and z[i][j-1] == 'S') + (j != 11 and z[i][j+1] == 'S')
        if z[i][j] == 'P' or z[i][j] == 'S':
            r += t
        elif z[i][j] == '.':
            if t == 0:
                a1.append((i, j))
            elif t == 1:
                a2.append((i, j))
            else:
                a3.append((i, j))
for i in a1:
    if k != 0:
        z[i[0]][i[1]] = 'x'
        k -= 1
    else:
        break
for i in a2:
    if k != 0:
        z[i[0]][i[1]] = 'x'
        k -= 1
        r += 1
    else:
        break
for i in a3:
    if k != 0:
        z[i[0]][i[1]] = 'x'
        k -= 1
        r += 2
    else:
        break
print(r)
for i in z:
    print(*i, sep='')

a = input().split()
n, k = int(a[0]), int(a[1])
zero = []
one = []
two = []
plain = []
neighbours = 0
notS = ['P', '-', '.']
for i in range(n):
    row = input()
    plain.append(list(row))
    for e in range(len(row)):
        if row[e] == '.':
            if e == 0:
                if row[e + 1] in notS:
                    zero.append((i, e))
                elif row[e + 1] == 'S':
                    one.append((i, e))
            else:
                if e != len(row) - 1:
                    if row[e + 1] in notS and row[e - 1] in notS:
                        zero.append((i, e))
                    elif (row[e + 1] in notS and row[e - 1] not in notS) or (row[e - 1] in notS and row[e + 1] not in notS):
                        one.append((i, e))
                    else:
                        two.append((i, e))
                else:
                    if row[e - 1] in notS:
                        zero.append((i, e))
                    else:
                        one.append((i, e))
        elif row[e] == 'P':
            if e == 0:
                if row[e + 1] == 'S':
                    neighbours += 1
            else:
                if e == len(row) - 1:
                    if row[e - 1] == 'S':
                        neighbours += 1
                else:
                    if row[e - 1] == 'S':
                        neighbours += 1
                    if row[e + 1] == 'S':
                        neighbours += 1
        elif row[e] == 'S':
            if e == 0:
                if row[e + 1] == 'S':
                    neighbours += 1
            else:
                if e == len(row) - 1:
                    if row[e - 1] == 'S':
                        neighbours += 1
                else:
                    if row[e - 1] == 'S':
                        neighbours += 1
                    if row[e + 1] == 'S':
                        neighbours += 1
for i in range(len(zero)):
    if k != 0:
        k -= 1
        plain[zero[i][0]][zero[i][1]] = 'x'
    else:
        break
if k != 0:
    for i in range(len(one)):
        if k != 0:
            k -= 1
            plain[one[i][0]][one[i][1]] = 'x'
            neighbours += 1
        else:
            break
    if k != 0:
        for i in range(len(two)):
            if k != 0:
                k -= 1
                plain[two[i][0]][two[i][1]] = 'x'
                neighbours += 2
            else:
                break
print(neighbours)
for i in range(n):
    print(''.join(plain[i]))








n, k = list(map(int, input().split()))
lines = [[ch for ch in input()]+['\n'] for i in range(n)]
queue = [[], [], []]
count = 0

for i in range(n):
    for seat in range(12):
        if lines[i][seat]=='.':
            queue[(lines[i][seat-1]=='S')+(lines[i][seat+1]=='S')].append([i, seat])
        elif lines[i][seat]=='S':
            count+=(lines[i][seat-1]>'A')+(lines[i][seat+1]>'A')

while k:
    if   queue[0]: seat = queue[0].pop()
    elif queue[1]:
        seat = queue[1].pop()
        count+=1
    else:
        seat = queue[2].pop()
        count+=2

    lines[seat[0]][seat[1]] = 'x'
    k-=1

print(count)
print(''.join([''.join(line) for line in lines]))


n,k = list(map(int, input().split()))
g = []
q = []
for i in range(n):
    v = input()
    p = []
    for i in v:
        p.append(i)
    v = p
    g.append(v)
    for x in range(len(v)):
        if v[x] != '.': continue
        num = 0
        if x != 0 and v[x-1] == 'S':
            num += 1
        if x+1 < len(v) and v[x+1] == 'S':
            num += 1
        q.append((num, len(g)-1, x))
q = sorted(q)
for i in range(k):
    g[q[i][1]][q[i][2]] = 'x'
an = 0
for s in g:
    for j in range(len(s)):
        if s[j] != 'S': continue
        if j != 0 and ( s[j-1] != '.' and s[j-1] != '-' ):
            an += 1
        if j+1 < len(s) and ( s[j+1] != '.' and s[j+1] != '-' ):
            an += 1
print(an)
    
for s in g:
    print("".join(s))
        


n, k = map(int, input().split())
 
raw_list = list()
for i in range(0,n):
    raw_list.append(input())
 
place_list = list()  
count_list = list()
 
for raw_index, raw in enumerate(raw_list):
    for place_index, place in enumerate(raw):
        if place == '.':	
            count = 0		
            if place_index > 0 and raw[place_index - 1] == 'S':
                count += 1	
            if place_index < (len(raw) - 1) and raw[place_index + 1] == 'S':
                count += 1	
            place_list.append((raw_index, place_index))
            count_list.append(count)
 
min_list = list()	
put_list = list()	
 
for i in range(0, k):
    min_list.append(count_list.index(min(count_list)))  
    put_list.append(place_list[min_list[i]])	
 
    del count_list[min_list[i]]	
    del place_list[min_list[i]]
 
new_raw_list = list()	
here = False	
 
for raw_index, raw in enumerate(raw_list):
    new_raw = str()
    for place_index, place in enumerate(raw):
        for i in range(0, len(min_list)):
            if raw_index == put_list[i][0] and place_index == put_list[i][1]:
                new_raw += 'x'
                here = True	
                break
            else:
                continue
 
        if here == False:	
            new_raw += place
        else:
            here = False
 
    new_raw_list.append(new_raw)
 
result = 0
alive = ['S', 'P', 'x']
for raw in new_raw_list:
    for place_index, place in enumerate(raw):
        if place == 'S':	
            if place_index != 0:	
                if raw[place_index - 1] in alive:
                    result += 1	
            if place_index != (len(raw) - 1):
                if raw[place_index + 1] in alive:
                    result += 1	
         
print(result)
for i in range(0, n):
	print(new_raw_list[i])

#   TaskB

import sys

n, k = list(map(int, sys.stdin.readline().split()))

my_list = list()

for i in range(n):
    my_list.append(input())


def left(i, my_list):
    return my_list[i] == '.' and \
           ((i - 1) < 0 or
            my_list[i - 1] == '.' or
            my_list[i - 1] == 'P' or
            my_list[i - 1] == '-' or
            my_list[i - 1] == 'x')


def right(i, my_list):
    return my_list[i] == '.' and \
           ((i + 1) >= len(my_list) or
            my_list[i + 1] == '.' or
            my_list[i + 1] == 'P' or
            my_list[i + 1] == '-' or
            my_list[i + 1] == 'x')


while k > 0:
    for index in range(n):
        cur_list = my_list[index]
        for i, _ in enumerate(cur_list):
            if left(i, cur_list) and right(i, cur_list):
                k = k - 1
                try:
                    part3 = cur_list[(i + 1):]
                except:
                    part3 = ''
                cur_list = cur_list[:i] + 'x' + part3
                my_list[index] = cur_list
                if k == 0:
                    break
            if k == 0:
                break
        if k == 0:
            break
    if k == 0:
        break

    for index in range(n):
        cur_list = my_list[index]
        for i, _ in enumerate(cur_list):
            if ((not left(i, cur_list) and cur_list[i] == '.') and right(i, cur_list)) or (left(i, cur_list) and (not right(i, cur_list)) and cur_list[i] == '.'):
                k = k - 1
                try:
                    part3 = cur_list[(i + 1):]
                except:
                    part3 = ''
                cur_list = cur_list[:i] + 'x' + part3
                my_list[index] = cur_list
                if k == 0:
                    break
            if k == 0:
                break
        if k == 0:
            break
    if k == 0:
        break

    for index in range(n):
        cur_list = my_list[index]
        for i, _ in enumerate(cur_list):
            if cur_list[i] == '.':
                k = k - 1
                try:
                    part3 = cur_list[(i + 1):]
                except:
                    part3 = ''
                cur_list = cur_list[:i] + 'x' + part3
                my_list[index] = cur_list
                if k == 0:
                    break
            if k == 0:
                break
        if k == 0:
            break
    if k == 0:
        break
    break

neighbours = 0
for i in range(n):
    cur_list = my_list[i]
    for j, _ in enumerate(cur_list):
        if cur_list[j] == 'S':
            if j - 1 >= 0 and (cur_list[j - 1] == 'x' or cur_list[j - 1] == 'P' or cur_list[j - 1] == 'S'):
                neighbours += 1
            if j + 1 <= len(cur_list) - 1 and (cur_list[j + 1] == 'x' or cur_list[j + 1] == 'P' or cur_list[j + 1] == 'S'):
                neighbours += 1
print(neighbours)
for i in range(n):
    print(my_list[i])


#!/usr/bin/env python3

a, num = list(map(int, input().split()))

rows = {}
s = 0

for i in range(a):
    row = input()
    places = []
    best = []
    average = []

    for j, x in enumerate(row):
        if x == '.':
            row_ = ' ' + row + ' '
            if row_[j] != 'S' and row_[j + 2] != 'S':
                if num > 0:
                    row = row[:j] + 'x' + row[j+1:]
                    num -= 1
            elif row_[j] != 'S' or row_[j + 2] != 'S':
                average.append(j)
            else:
                places.append(j)

    rows[i] = {
        'average': average,
        'places': places,
        'row': row,
    }

for i in range(a):
    if rows[i]['average']:
        for j in rows[i]['average']:
            if num > 0:
                row = rows[i]['row']
                row = row[:j] + 'x' + row[j+1:]
                rows[i]['row'] = row
                num -= 1

for i in range(a):
    if rows[i]['places']:
        for j in rows[i]['places']:
            if num > 0:
                row = rows[i]['row']
                row = row[:j] + 'x' + row[j+1:]
                rows[i]['row'] = row
                num -= 1

for i in range(a):
    row = rows[i]['row']
    for j, x in enumerate(row):
        if x == 'S':
            row_ = ' ' + row + ' '
            if row_[j] in 'PSx':
                s += 1
            if row_[j + 2] in 'PSx':
                s += 1

print(s)

for i in range(a):
    print(rows[i]['row'])


def is_letter(char):
    return (
        ord('a') <= ord(char) <= ord('z') or
        ord('A') <= ord(char) <= ord('Z')
    )

n, kk = map(int, input().split())
placement = [
    [i for i in input()] for j in range(n)
]


kc = 0 

for row in placement:
    for i in range(len(row)):
        if (row[i] == '.'):
            count = 0
            if (i > 0 and row[i - 1] == 'S'):
                count += 1
            if (i < len(row) - 1 and row[i + 1] == 'S'):
                count += 1
            row[i] = count
        if (row[i] == 'S'):
            if (i > 0 and is_letter(str(row[i - 1]))):
                kc += 1
            if (i < len(row) - 1 and is_letter(str(row[i + 1]))):
                kc += 1
 
for i in range(3):
    for j in range(len(placement)):
        if (kk == 0):
            # print(f'broken here {i}, {j}') 
            break
        for k in range(len(placement[j])):
            if placement[j][k] == i:
                placement[j][k] = 'x'
                kc += i
                kk -= 1
                if (kk == 0):
                    # print("broken")                    
                    break

kkk = 0

for i in range(len(placement)):
    for j in range(len(placement[i])):
        if type(placement[i][j]) == type(1):
            placement[i][j] = '.'

print(kc)
for row in placement:
    print(''.join(row))

def count(flight):
	cnt = 0
	for i in range(len(flight)):
		for j in range(14):
			if flight[i][j] == 'S':
				f = [flight[i][j-1], flight[i][j+1]]
				cnt += 2 - f.count('-') - f.count('.')
	return cnt

def main():
	# f = open('B_input.txt', 'rt')
	n, k = map(int, input().split(' '))
	# n, k = map(int, f.readline().split(' '))
	flight = []
	for i in range(n):
		# flight.append(['-'] + list(f.readline().replace('\n', '')) + ['-'])
		flight.append(['-'] + list(input()) + ['-'])
	# f.close()

	for c in range(3):
		for i in range(n):
			for j in range(14):
				if flight[i][j] == '.' and [flight[i][j-1], flight[i][j+1]].count('S') == c:
					k -= 1
					flight[i][j] = 'x'
					if k == 0:
						return count(flight), '\n'.join([''.join(i[1:-1]) for i in flight]) 

print(*main(), sep = '\n')


n, k = (int(x) for x in input().split())
plane = []
neig = [[0] * 12 for x in range(n)]
count = [0, 0, 0]
count_all = 0
for i in range(n):
    s = input()
    plane.append(s)
    for j in range(12):
        if s[j] == 'S':
            if j > 0 and (s[j - 1] == 'S' or s[j - 1] == 'P'):
                count_all += 1
            if j < 11 and (s[j + 1] == 'S' or s[j + 1] == 'P'):
                count_all += 1
        if s[j] == '.':
            c = 2
            if (j > 0 and s[j - 1] != 'S') or j == 0:
                c -= 1
            if (j < 11 and s[j + 1] != 'S') or j == 11:
                c -= 1
            count[c] += 1
            neig[i][j] = c
# print(count)
k1 = k
for i in range(3):
    if k1 >= count[i]:
        k1, count[i] = k1 - count[i], count[i]
    else:
        k1, count[i] = 0, k1
# print(count_all, count)
print(count_all + count[1] + 2 * count[2])
# print(plane[12])
for i in range(n):
    for j in range(12):
        if plane[i][j] == '.':
            if k > 0:
                if count[0] > 0 and neig[i][j] == 0:
                    plane[i] = plane[i][:j] + 'x' + plane[i][j + 1:]
                    count[0] -= 1
                    k -= 1
                elif count[1] > 0 and neig[i][j] == 1:
                    plane[i] = plane[i][:j] + 'x' + plane[i][j + 1:]
                    count[1] -= 1
                    k -= 1
                elif count[2] > 0 and neig[i][j] == 2:
                    plane[i] = plane[i][:j] + 'x' + plane[i][j + 1:]
                    count[2] -= 1
                    k -= 1
            else:
                break
    print(plane[i])






n, k = (int(x) for x in input().split())
plane = []
neig = [[0] * 12 for x in range(n)]
count = [0, 0, 0]
count_all = 0
for i in range(n):
    s = input()
    plane.append(s)
    for j in range(12):
        if s[j] == 'S':
            if j > 0 and (s[j - 1] == 'S' or s[j - 1] == 'P'):
                count_all += 1
            if j < 11 and (s[j + 1] == 'S' or s[j + 1] == 'P'):
                count_all += 1
        if s[j] == '.':
            c = 2
            if (j > 0 and s[j - 1] != 'S') or j == 0:
                c -= 1
            if (j < 11 and s[j + 1] != 'S') or j == 11:
                c -= 1
            count[c] += 1
            neig[i][j] = c
k1 = k
for i in range(3):
    if k1 >= count[i]:
        k1, count[i] = k1 - count[i], count[i]
    else:
        k1, count[i] = 0, k1
print(count_all + count[1] + 2 * count[2])
for i in range(n):
    for j in range(12):
        if plane[i][j] == '.':
            if k > 0:
                if count[0] > 0 and neig[i][j] == 0:
                    plane[i] = plane[i][:j] + 'x' + plane[i][j + 1:]
                    count[0] -= 1
                    k -= 1
                elif count[1] > 0 and neig[i][j] == 1:
                    plane[i] = plane[i][:j] + 'x' + plane[i][j + 1:]
                    count[1] -= 1
                    k -= 1
                elif count[2] > 0 and neig[i][j] == 2:
                    plane[i] = plane[i][:j] + 'x' + plane[i][j + 1:]
                    count[2] -= 1
                    k -= 1
            else:
                break
    print(plane[i])

n, z = map(int, input().split())
s = 0
a = []
x = []
for j in range(n):
    c = list(input())
    x.append(c)
    for i in range(12):
        if c[i] == '.':
            if i == 0:
                if c[1] == 'S':
                    a.append([1, (j,0)])
                else:
                    a.append([0, (j,0)])
            elif i == 11:
                if c[10] == 'S':
                    a.append([1, (j,11)])
                else:
                    a.append([0, (j,11)])
            else:
                k = 0
                if c[i - 1] == 'S':
                    k += 1
                if c[i + 1] == 'S':
                    k += 1
                a.append([k, (j,i)])
        if c[i] == 'S':
            if i == 0:
                if c[1] not in '.-':
                    s += 1
            elif i == 11:
                if c[10] not in '.-':
                    s += 1
            else:
                if c[i - 1] not in '.-':
                    s += 1
                if c[i + 1] not in '.-':
                    s += 1
a.sort()
b = []
c = []
for i in range(z):
    b.append(a[i][0])
    c.append(a[i][1])
for i in range(z):
    x[c[i][0]][c[i][1]] = 'x'
print(s + sum(b))
for i in range(n):
    print(''.join(x[i]))

def main():
    n, k = map(int, input().split())
    lines = list()
    m = [0, 0, 0]
    v = 0
    for i in range(n):
        lines.append(input() + ' ')
        for j in range(12):
            if lines[i][j] == '.':
                c = 0
                if lines[i][j - 1] == 'S':
                    c += 1
                if lines[i][j + 1] == 'S':
                    c += 1
                m[c] += 1
            elif lines[i][j] == 'S':
                if lines[i][j - 1] == 'S' or lines[i][j - 1] == 'P':
                    v += 1
                if lines[i][j + 1] == 'S' or lines[i][j + 1] == 'P':
                    v += 1
    m[0] = min(m[0], k)
    k -= m[0]
    m[1] = min(m[1], k)
    k -= m[1]
    m[2] = min(m[2], k)
    v += m[1] + 2 * m[2]
    print(v)
    for elem in lines:
        for j in range(12):
            if elem[j] == '.':
                c = 0
                if elem[j - 1] == 'S':
                    c += 1
                if elem[j + 1] == 'S':
                    c += 1
                if m[c] > 0:
                    print('x', end='')
                    m[c] -= 1
                else:
                    print('.', end='')
            else:
                print(elem[j], end='')
        print()

main()

DEBUG = False

def print_debug(*args):
    if DEBUG:
        print(*args)


def print_res():
    nonlocal places
    nonlocal ss
    print(ss)
    for row_i in range(n):
        print("".join(places[row_i]))


n, k = [int(x) for x in input().split()]
places = []

ss = 0

for row_i in range(n):
    row = list(input())
    places.append(row)
    for i in range(12):
        if k > 0 and row[i] == "." and (i == 0 or row[i - 1] != "S") and (i == 11 or row[i + 1] != "S"):
            row[i] = "x"
            k -= 1
        if row[i] == "S":
            if i > 0 and (row[i - 1] not in [".", "-"]):
                ss += 1
            if i < 11 and (row[i + 1] not in [".", "-"]):
                ss += 1

print_debug("--------")
print_debug(k)
#print_res()

if k > 0:
    for row_i in range(n):
        if k == 0:
            break
        row = places[row_i]
        for i in range(12):
            if k == 0:
                break
            if row[i] == ".":
                if i in [1, 5, 6, 10] and row[i - 1] == "S" and row[i + 1] == "S":
                    continue
                k -= 1
                ss += 1
                row[i] = "x"

print_debug("--------")
print_debug(k)
#print_res()

if k > 0:
    for row_i in range(n):
        if k == 0:
            break
        row = places[row_i]
        for i in range(12):
            if k == 0:
                break
            if row[i] == ".":
                row[i] = "x"
                ss += 2
                k -= 1

print_debug(k)
print_res()



__author__ = 'RaldenProg'
from pprint import pprint
n, k = [_ for _ in map(int, input().split())]
top = ['.', 'P', '-', 'x']
top1 = ['S', '-', 'p', '.']
pas = ['P', 'x', 'S']
y = []
for i in range(n):
    x = ['-']
    x.extend(list(input()))
    x.append('-')
    y.append(x)

chet = 0

for i in range(n):
    for j in range(len(y[i])):
        if y[i][j] == '.':
            if y[i][j-1] in top and y[i][j+1] in top and chet != k:
                #print(y[i][j-1], y[i][j], y[i][j+1])
                y[i][j] = 'x'
                chet += 1
while chet != k:
    flag = 0
    for i in range(n):
        for j in range(len(y[i])):
            if y[i][j] == '.':
                if y[i][j - 1] in top1 and y[i][j + 1] in top and chet != k:
                    #print(y[i][j - 1], y[i][j], y[i][j + 1])
                    y[i][j] = 'x'
                    chet += 1
                    flag = 1

                if y[i][j - 1] in top and y[i][j + 1] in top1 and chet != k:
                    #print(y[i][j - 1], y[i][j], y[i][j + 1])
                    y[i][j] = 'x'
                    chet += 1
                    flag = 1

    if flag == 0 and chet != k:
        for i in range(n):
            for j in range(len(y[i])):
                if y[i][j] == '.' and chet != k:
                    y[i][j] = 'x'
                    chet += 1
                    flag = 1

kol = 0
for i in range(n):
    for j in range(len(y[i])):
        if y[i][j] == 'S':
            if y[i][j - 1] in pas:
                kol += 1
            if y[i][j + 1] in pas:
                kol += 1
print(kol)
for i in range(n):
    for j in range(1, len(y[i])-1):
        print(y[i][j], end='')
    print()


n, k = map(int, input().split())
A = [['-'] + list(input()) + ['-'] for _ in range(n)]
neighs = 0
for i in A:
    for j in range(len(i)):
        if i[j] == 'S':
            if i[j - 1] != '.' and i[j - 1] != '-':
                neighs += 1
            if i[j + 1] != '.' and i[j + 1] != '-':
                neighs += 1
for i in range(len(A)):
    if k < 0:
        break
    for j in range(len(A[i])):
        if A[i][j] == '.' and A[i][j - 1] != 'S' and A[i][j + 1] != 'S' and k > 0:
            A[i][j] = 'x'
            k -= 1
        elif k <= 0:
            break
for i in range(len(A)):
    if k < 0:
        break
    for j in range(len(A[i])):
        if A[i][j] == '.' and A[i][j - 1] == 'S' and A[i][j + 1] != 'S' and k > 0:
            A[i][j] = 'x'
            neighs += 1
            k -= 1
        elif k <= 0:
            break
for i in range(len(A)):
    if k < 0:
        break
    for j in range(len(A[i])):
        if A[i][j] == '.' and A[i][j - 1] != 'S' and A[i][j + 1] == 'S' and k > 0:
            A[i][j] = 'x'
            neighs += 1
            k -= 1
        elif k <= 0:
            break
for i in range(len(A)):
    if k < 0:
        break
    for j in range(len(A[i])):
        if A[i][j] == '.' and k > 0:
            A[i][j] = 'x'
            neighs += 2
            k -= 1
        elif k <= 0:
            break
print(neighs)
for i in A:
    print(*i[1:-1], sep='')

n, k = list(map(int, input().split()))
rows = list()
# здесь и далее nb - neighbors
nb = 0
# места с соответствующим количеством соедей (0,1,2)
places_by_nb = [list(), list(), list()]
for i in range(n):
    # считываем строку и добавляем как массив
    line = input()
    rows.append(list(line))
    # вставляем символы-ограничители в начало и конец и идем по строке
    row = '-%s-' % line
    for j in range(1, 13):
        # вычисляем первоначальное количество соседей
        if row[j] == 'S':
            if row[j-1] == 'S' or row[j-1] == 'P':
                nb += 1
            if row[j+1] == 'S' or row[j+1] == 'P':
                nb += 1
        # вычисляем количество соседей у каждого свободного места
        # и записываем координату места (с учетом ограничителей) в соответствующий массив (по числу соседей)
        elif row[j] == '.':
            t = 0
            if row[j-1] == 'S':
                t += 1
            if row[j+1] == 'S':
                t += 1
            places_by_nb[t].append((i, j-1))
# до тех пор пока есть непосаженные пассажиры:
# берем место, садим пассажира, увеличиваем количество соседей, уменьшаем количество пассажиров
for m in range(0,3):
    while k > 0 and len(places_by_nb[m]) > 0:
        place = places_by_nb[m].pop(-1)
        rows[place[0]][place[1]] = 'x'
        nb += m
        k -= 1
    if k == 0:
        break
# и наконец выводим результат
print(nb)
for row in rows:
    print(''.join(row))