Kryssring

Simon och Måns sitter på tunnelbanan, och spelar ett spel. Simon ritar upp ett $n \times m$ rutnät och ritar in ett par kryss och ringar i rutorna. Han skriver även ett tal på varje rad.

Måns uppgift är nu att fylla i rutnätet så att varje ruta har ett kryss eller en ring, så att det finns lika många kryss på varje rad som talet som står där. Målet för Måns är att varje rad, kolumn och diagonal har högst $2$ kryss eller ringar i rad.

Simon har ritat ut kryssen och ringarna helt på måfå, så det är inte uppenbart att detta är möjligt. Vi kan dock ge Måns poäng beroende på hur väl han lyckats: vi definierar värdet för en utplacering som antalet gånger det förekommer tre kryss eller tre ringar i rad i någon rad, kolumn eller diagonal (åt båda hållen). Måns ska då försöka få så lågt värde han kan.

Hjälp Måns spela spelet så bra som möjligt!

Indata

Observera: testdatan på detta problem är öppen. Du kan ladda ner den på https://www.progolymp.se/uploads/kattis-attachments/kryssring.zip. Den första raden innehåller ett heltal $0 \le t \le 10$, ordningstalet för detta testfall. Fallet $t = 0$ representar exempelfallet, och ska ignoreras (du kan skriva ut vad du vill då).

Den andra raden innehåller två heltal $n$ och $m$ ($2 \le n, m \le 500$): höjden och bredden på rutnätet. Den tredje raden innehåller $n$ tal: antalet kryss som måste skrivas in på varje rad. Därefter följer $n$ rader, med $m$ tecken vardera: det ursprungliga rutnätet. Varje tecken kommer att vara antingen “.”, “o” eller “$\texttt{x}$”, där “.” betyder att rutan ännu inte fyllts i.

Det är garanterat att antalet kryss som finns i varje rad är högst lika med talet som Simon skrivit för den raden.

Utdata

Skriv ut $n$ rader med $m$ tecken vardera: det helt ifyllda rutnätet, där alla “.” bytts ut mot antingen “o” eller “x”.

Notera att Kattis har en storleksgräns på källkod på 128kB. För rutnäten av maximal storlek går det därmed inte att hårdkoda kompletta lösningar i koden.

Poängsättning

Din lösning kommer att få poäng på varje av de tio testfallen.

Varje testfall poängsätts på följande vis. Antag att värdet du åstadkommit på testfallet är $X$, och det minimala värdet någon deltagare lyckats åstadkomma är $X_{\min }$. Om $X_{\min } \ne 0$, låt $X_{\min }’ = X_{\min }$, annars låt $X_{\min }’$ vara den näst bästa deltagarens värde på det testfallet (som inte är 0). Om $X \ge 2X_{\min }’$ tilldelas testfallet $0$ poäng, annars tilldelas $10(1 - r)$ poäng, där $r = (X - X_{min}) / (2X_{\min }’ - X_{\min })$.

Under tävlingen kommer $X_{min}$ vara satt till ett av domarna framräknat värde. Det betyder att scoreboard kan temporärt visa poäng upp till 200, och det är möjligt att ens poäng på ett testfall kan räknas om till 0 efter tävlingen!

Förklaring av Sample 1

I lösningen på exemplet finns 26 st. vertikala tre-i-rad, 18 st. horisontella, och 32 st. diagonala. Totalt ger detta alltså ett värde på 76.

0
10 10
5 2 5 3 3 2 5 5 6 5
.....o..o.
..........
..o.......
.....o....
..........
...x......
.o..x.....
...o......
....xo....
.o........

oxxxxooxoo
oooooxxooo
oxoxooxoxx
ooxxooxooo
oxooxoxooo
oxoxoooooo
ooxoxoxxxo
ooxooxxxox
oxxxxoxxoo
ooxooxxxxo