Codeforces Round 470 (rated, Div. 2, based on VK Cup 2018 Round 1)


A. Protect Sheep
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6 6
..S...
..S.W.
.S....
..W...
...W..
......
Output
Yes
..SD..
..SDW.
.SD...
.DW...
DD.W..
......
Input
1 2
SW
Output
No
Input
5 5
.S...
...S.
S....
...S.
.S...
Output
Yes
.S...
...S.
S.D..
...S.
.S...
----------------------------------------------------------------------------------------------------
B. Primal Sport
time limit per test: 1.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
14
Output
6
Input
20
Output
15
Input
8192
Output
8191
----------------------------------------------------------------------------------------------------
C. Producing Snow
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
10 10 5
5 7 2
Output
5 12 4
Input
5
30 25 20 15 10
9 10 12 4 13
Output
9 20 35 11 25
----------------------------------------------------------------------------------------------------
D. Perfect Security
time limit per test: 3.5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
8 4 13
17 2 7
Output
10 3 28
Input
5
12 7 87 22 11
18 39 9 12 16
Output
0 14 69 6 44
Input
10
331415699 278745619 998190004 423175621 42983144 166555524 843586353 802130100 337889448 685310951
226011312 266003835 342809544 504667531 529814910 684873393 817026985 844010788 993949858 1031395667
Output
128965467 243912600 4281110 112029883 223689619 76924724 429589 119397893 613490433 362863284
----------------------------------------------------------------------------------------------------
E. Picking Strings
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
AABCCBAAB
ABCB
5
1 3 1 2
2 2 2 4
7 9 1 1
3 4 2 3
4 5 1 3
Output
10011
----------------------------------------------------------------------------------------------------
