Codeforces Round 504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)


A. Single Wildcard Pattern Matching
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6 10
code*s
codeforces
Output
YES
Input
6 5
vk*cup
vkcup
Output
YES
Input
1 1
v
k
Output
NO
Input
9 6
gfgf*gfgf
gfgfgf
Output
NO
----------------------------------------------------------------------------------------------------
B. Pair of Toys
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8 5
Output
2
Input
8 15
Output
1
Input
7 20
Output
0
Input
1000000000000 1000000000001
Output
500000000000
----------------------------------------------------------------------------------------------------
C. Bracket Subsequence
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6 4
()(())
Output
()()
Input
8 8
(()(()))
Output
(()(()))
----------------------------------------------------------------------------------------------------
D. Array Restoration
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 3
1 0 2 3
Output
YES
1 2 2 3
Input
3 10
10 10 10
Output
YES
10 10 10 
Input
5 6
6 5 6 2 2
Output
NO
Input
3 5
0 0 0
Output
YES
5 4 2
----------------------------------------------------------------------------------------------------
E. Down or Right
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
 
YES
 
NO
 
YES
 
YES
 
Output
 
? 1 1 4 4
 
? 1 2 4 3
 
? 4 1 4 4
 
? 1 4 4 4
 
! RDRRDD
----------------------------------------------------------------------------------------------------
F. Mobile Phone Network
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 3 6
1 2
3 4
1 3
2 3 3
3 1 4
1 2 4
4 2 8
4 3 8
4 1 10
Output
14
Input
3 2 1
1 2
2 3
1 2 30
Output
-1
Input
4 3 3
1 2
1 3
1 4
4 1 1000000000
4 2 1000000000
4 3 1000000000
Output
3000000000
----------------------------------------------------------------------------------------------------
G. Pisces
time limit per test: 5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4
1 2 1
1 3 1
1 4 1
5
1 1 2
1 1 3
2 2 1
3 1 4
3 1 2
Output
2
Input
5
1 2 1
1 3 1
1 4 1
1 5 1
4
1 1 2
2 1 3
3 1 4
4 1 5
Output
2
Input
5
2 5 1
5 1 1
2 4 1
5 3 3
6
5 2 4
2 1 1
2 1 3
2 2 4
4 7 5
4 1 2
Output
10
----------------------------------------------------------------------------------------------------
