Codeforces Round 616 (Div. 1)


A. Mind Control
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
6 4 2
2 9 2 3 8 5
4 4 1
2 13 60 4
4 1 3
1 2 2 1
2 2 0
1 2
Output
8
4
1
1
----------------------------------------------------------------------------------------------------
B. Irreducible Anagrams
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
aaaaa
3
1 1
2 4
5 5
Output
Yes
No
Yes
Input
aabbbbbbc
6
1 2
2 4
2 2
1 9
5 7
3 5
Output
No
Yes
Yes
Yes
No
No
----------------------------------------------------------------------------------------------------
C. Prefix Enlightenment
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7 3
0011100
3
1 4 6
3
3 4 7
2
2 3
Output
1
2
3
3
3
3
3
Input
8 6
00110011
3
1 3 8
5
1 2 5 6 7
2
6 8
2
3 5
2
4 7
1
2
Output
1
1
1
1
1
1
4
4
Input
5 3
00011
3
1 2 3
1
4
3
3 4 5
Output
1
1
1
1
1
Input
19 5
1001001001100000110
2
2 3
2
5 6
2
8 9
5
12 13 14 15 16
1
19
Output
0
1
1
1
2
2
2
3
3
3
3
4
4
4
4
4
4
4
5
----------------------------------------------------------------------------------------------------
D. Coffee Varieties (hard version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 2
N
N
Y
N
N
N
N
Output
? 1
? 2
? 3
? 4
R
? 4
? 1
? 2
! 3
Input
8 8
N
N
N
N
Y
Y
Output
? 2
? 6
? 4
? 5
? 2
? 5
! 6
----------------------------------------------------------------------------------------------------
E. Cartesian Tree
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2 4 1 5 3
Output
1
3
6
8
11
Input
6
1 2 4 5 6 3
Output
1
3
6
8
12
17
----------------------------------------------------------------------------------------------------
F. Making Shapes
time limit per test: 5 seconds
memory limit per test: 768 megabytes
input: standard input
output: standard output

Examples
Input
3 3
-1 0
1 1
0 -1
Output
3
Input
3 3
-1 0
2 2
0 -1
Output
1
Input
3 1776966
-1 0
3 3
0 -2
Output
296161
Input
4 15
-4 -4
-1 1
-1 -4
4 3
Output
1
Input
5 10
3 -4
4 -3
1 -3
2 -3
-3 -4
Output
0
Input
5 1000000000
-2 4
2 -3
0 -4
2 4
-1 -3
Output
9248783
----------------------------------------------------------------------------------------------------
