C=lambda x:[x[:2]]+C(x[2:])if[]<x else[]
E=enumerate
def f(a,b,c):
 A,B,F=dict(C(a)+[(k,j)for j,k in C(a)]),dict(C(b)+[(k,j)for j,k in C(b)]),0
 q,S=[(c,[(x,y)for x,r in E(c)for y,v in E(r)if'.'==v])],[]
 for c,l in q:
  if[]==l:return c
  (x,y),*l=l
  for t in'SM':
   e=eval(str(c));e[x][y]=t
   if all(all(m*3not in''.join(k)for k in e+[*zip(*e)])for m in'SM')and all('.'in j or j.count('M')==j.count('S')for j in e+[*zip(*e)])and e not in S:
    F=1
    if(x,y)in A:X,Y=A[(x,y)];F=e[X][Y]in['.',t]
    elif(x,y)in B:X,Y=B[(x,y)];F=e[X][Y]=='.'or e[X][Y]!=t
    if F:q+=[(e,l)];S+=e,
 
s1= """
.MSSM.
M....M
S....M
S....S
M....S
.SMMS.
"""
 
s2 = """
MS....
M...SM
SM..M.
.S..MS
SM...M
....MS
"""
 
s3 = """
......
......
..S.S.
.M.S..
......
......
"""
 
s4 = """
..SS..
......
......
......
......
......
"""
 
def to_board(s):
	return [[*i] for i in filter(None, s.split('\n'))]
 
def get_board(s):
	return '\n'.join(map(''.join,s))
 
print(get_board(f([(1,1), (2,1), (3,1), (3,2)],[(1,2), (2,2), (1,3), (1,4), (2,3), (2,4), (3,3), (4,3), (3,4), (4,4), (4,1), (4,2)],to_board(s1))))
print('-'*40)
print(get_board(f([(2,2), (2,3), (2,3), (3,3)],[(3,2), (3,3), (2,2), (3,2)],to_board(s2))))
print('-'*40)
print(get_board(f([(0,1), (1,1), (1,0), (2,0), (2,5), (3,5), (3,0), (4,0), (4,0), (4,1)],[(0,1), (0,2), (0,3), (0,4), (0,4), (1,4), (1,0), (1,1), (1,4), (1,5), (1,5), (2,5), (2,0), (3,0), (3,5), (4,5), (4,4), (4,5), (4,4), (5,4), (5,3), (5,4), (5,1), (5,2), (4,1), (5,1)],to_board(s3))))
print('-'*40)
print(get_board(f([(1,2), (2,2), (2,1), (3,1), (3,2), (3,3), (4,0), (5,0), (5,1), (5,2), (5,3), (5,4), (4,5), (5,5)],[(1,3), (2,3), (2,4), (3,4), (4,1), (4,2), (4,3), (4,4)],to_board(s4))))

Qz1sYW1iZGEgeDpbeFs6Ml1dK0MoeFsyOl0paWZbXTx4IGVsc2VbXQpFPWVudW1lcmF0ZQpkZWYgZihhLGIsYyk6CiBBLEIsRj1kaWN0KEMoYSkrWyhrLGopZm9yIGosayBpbiBDKGEpXSksZGljdChDKGIpK1soayxqKWZvciBqLGsgaW4gQyhiKV0pLDAKIHEsUz1bKGMsWyh4LHkpZm9yIHgsciBpbiBFKGMpZm9yIHksdiBpbiBFKHIpaWYnLic9PXZdKV0sW10KIGZvciBjLGwgaW4gcToKICBpZltdPT1sOnJldHVybiBjCiAgKHgseSksKmw9bAogIGZvciB0IGluJ1NNJzoKICAgZT1ldmFsKHN0cihjKSk7ZVt4XVt5XT10CiAgIGlmIGFsbChhbGwobSozbm90IGluJycuam9pbihrKWZvciBrIGluIGUrWyp6aXAoKmUpXSlmb3IgbSBpbidTTScpYW5kIGFsbCgnLidpbiBqIG9yIGouY291bnQoJ00nKT09ai5jb3VudCgnUycpZm9yIGogaW4gZStbKnppcCgqZSldKWFuZCBlIG5vdCBpbiBTOgogICAgRj0xCiAgICBpZih4LHkpaW4gQTpYLFk9QVsoeCx5KV07Rj1lW1hdW1ldaW5bJy4nLHRdCiAgICBlbGlmKHgseSlpbiBCOlgsWT1CWyh4LHkpXTtGPWVbWF1bWV09PScuJ29yIGVbWF1bWV0hPXQKICAgIGlmIEY6cSs9WyhlLGwpXTtTKz1lLAogICAgCnMxPSAiIiIKLk1TU00uCk0uLi4uTQpTLi4uLk0KUy4uLi5TCk0uLi4uUwouU01NUy4KIiIiCgpzMiA9ICIiIgpNUy4uLi4KTS4uLlNNClNNLi5NLgouUy4uTVMKU00uLi5NCi4uLi5NUwoiIiIKCnMzID0gIiIiCi4uLi4uLgouLi4uLi4KLi5TLlMuCi5NLlMuLgouLi4uLi4KLi4uLi4uCiIiIgoKczQgPSAiIiIKLi5TUy4uCi4uLi4uLgouLi4uLi4KLi4uLi4uCi4uLi4uLgouLi4uLi4KIiIiCgpkZWYgdG9fYm9hcmQocyk6CglyZXR1cm4gW1sqaV0gZm9yIGkgaW4gZmlsdGVyKE5vbmUsIHMuc3BsaXQoJ1xuJykpXQoKZGVmIGdldF9ib2FyZChzKToKCXJldHVybiAnXG4nLmpvaW4obWFwKCcnLmpvaW4scykpCgpwcmludChnZXRfYm9hcmQoZihbKDEsMSksICgyLDEpLCAoMywxKSwgKDMsMildLFsoMSwyKSwgKDIsMiksICgxLDMpLCAoMSw0KSwgKDIsMyksICgyLDQpLCAoMywzKSwgKDQsMyksICgzLDQpLCAoNCw0KSwgKDQsMSksICg0LDIpXSx0b19ib2FyZChzMSkpKSkKcHJpbnQoJy0nKjQwKQpwcmludChnZXRfYm9hcmQoZihbKDIsMiksICgyLDMpLCAoMiwzKSwgKDMsMyldLFsoMywyKSwgKDMsMyksICgyLDIpLCAoMywyKV0sdG9fYm9hcmQoczIpKSkpCnByaW50KCctJyo0MCkKcHJpbnQoZ2V0X2JvYXJkKGYoWygwLDEpLCAoMSwxKSwgKDEsMCksICgyLDApLCAoMiw1KSwgKDMsNSksICgzLDApLCAoNCwwKSwgKDQsMCksICg0LDEpXSxbKDAsMSksICgwLDIpLCAoMCwzKSwgKDAsNCksICgwLDQpLCAoMSw0KSwgKDEsMCksICgxLDEpLCAoMSw0KSwgKDEsNSksICgxLDUpLCAoMiw1KSwgKDIsMCksICgzLDApLCAoMyw1KSwgKDQsNSksICg0LDQpLCAoNCw1KSwgKDQsNCksICg1LDQpLCAoNSwzKSwgKDUsNCksICg1LDEpLCAoNSwyKSwgKDQsMSksICg1LDEpXSx0b19ib2FyZChzMykpKSkKcHJpbnQoJy0nKjQwKQpwcmludChnZXRfYm9hcmQoZihbKDEsMiksICgyLDIpLCAoMiwxKSwgKDMsMSksICgzLDIpLCAoMywzKSwgKDQsMCksICg1LDApLCAoNSwxKSwgKDUsMiksICg1LDMpLCAoNSw0KSwgKDQsNSksICg1LDUpXSxbKDEsMyksICgyLDMpLCAoMiw0KSwgKDMsNCksICg0LDEpLCAoNCwyKSwgKDQsMyksICg0LDQpXSx0b19ib2FyZChzNCkpKSk=