Codeforces Round 459 (Div. 1)


A. The Monster
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
((?))
Output
4
Input
??()??
Output
7
----------------------------------------------------------------------------------------------------
B. MADMAX
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 4
1 2 b
1 3 a
2 4 c
3 4 b
Output
BAAA
ABAA
BBBA
BBBB
Input
5 8
5 3 h
1 2 c
3 1 c
3 2 r
5 1 r
4 3 z
5 4 r
5 2 h
Output
BABBB
BBBBB
AABBB
AAABA
AAAAB
----------------------------------------------------------------------------------------------------
C. Pollywog
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 3 10 2
1 2 3
5 -10
6 1000
Output
6
Input
4 7 85 3
17 5 28 4 52 46 6
59 -76
33 -69
19 2018
Output
135
----------------------------------------------------------------------------------------------------
D. Stranger Trees
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
1 2
1 3
Output
0 2 1 
Input
4
1 2
2 3
3 4
Output
1 7 7 1 
Input
4
1 2
1 3
1 4
Output
0 9 6 1 
----------------------------------------------------------------------------------------------------
E. Upside Down
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
6 4 5
1 6 b
2 3 a
1 2 b
5 3 b
4 5 b
a
b
bb
aa
1 2 1
6 2 3
1 6 2
4 5 4
1 6 2
Output
0
1
1
0
1
Input
10 6 7
1 3 s
10 1 d
2 6 s
5 2 d
7 4 l
8 9 d
8 10 l
7 2 d
8 7 l
dl
dssld
d
d
l
sl
4 5 4
3 7 5
10 6 2
3 1 4
7 5 6
10 9 4
9 8 4
Output
2
2
0
0
0
1
1
----------------------------------------------------------------------------------------------------
