Codeforces Round 423 (Div. 1, rated, based on VK Cup Finals)


A. String Reconstruction
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
a 4 1 3 5 7
ab 2 1 5
ca 1 4
Output
abacaba
Input
1
a 1 3
Output
aaa
Input
3
ab 1 1
aba 1 3
ab 2 3 5
Output
ababab
----------------------------------------------------------------------------------------------------
B. High Load
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 2
Output
2
1 2
2 3
Input
5 3
Output
3
1 2
2 3
3 4
3 5
----------------------------------------------------------------------------------------------------
C. DNA Evolution
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
ATGCATGC
4
2 1 8 ATGC
2 2 6 TTT
1 4 T
2 2 6 TA
Output
8
2
4
Input
GAGTTGTTAA
6
2 3 4 TATGGTG
1 1 T
1 6 G
2 5 9 AGTAATA
1 10 G
2 2 6 TTGT
Output
0
3
1
----------------------------------------------------------------------------------------------------
D. Best Edge Weight
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 4
1 2 2
2 3 2
3 4 2
4 1 3
Output
2 2 2 1 
Input
4 3
1 2 2
2 3 2
3 4 2
Output
-1 -1 -1 
----------------------------------------------------------------------------------------------------
E. Rusty String
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
 
5
V??VK
 
6
??????
 
4
?VK?
Output
2
3 5
6
1 2 3 4 5 6
3
2 3 4
----------------------------------------------------------------------------------------------------
F. Dirty Arkady's Kitchen
time limit per test: 6 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5 6
1 2 0 1
2 5 2 3
2 5 0 1
1 3 0 1
3 4 1 2
4 5 2 3
Output
3
Input
2 1
1 2 1 100
Output
-1
----------------------------------------------------------------------------------------------------
