Codeforces Round 371 (Div. 1)


A. Sonya and Queries
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
12
+ 1
+ 241
? 1
+ 361
- 241
? 0101
+ 101
? 101
- 101
? 101
+ 4000
? 0
Output
2
1
2
1
1
Input
4
+ 200
+ 200
- 200
? 0
Output
1
----------------------------------------------------------------------------------------------------
B. Searching Rectangles
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
1
0
1
1
1
0
1
Output
? 1 1 5 5
? 1 1 3 3
? 1 1 3 1
? 2 2 2 2
? 3 3 5 5
? 3 3 3 5
? 3 3 3 4
? 3 4 3 5
! 2 2 2 2 3 4 3 5
----------------------------------------------------------------------------------------------------
C. Sonya and Problem Wihtout a Legend
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
2 1 5 11 5 9 11
Output
9
Input
5
5 4 3 2 1
Output
12
----------------------------------------------------------------------------------------------------
D. Animals and Puzzle
time limit per test: 5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 4
1 1 0 1
0 1 1 0
0 1 1 0
5
1 1 2 3
2 1 3 2
3 2 3 4
1 1 3 4
1 2 3 4
Output
1
1
1
2
2
----------------------------------------------------------------------------------------------------
E. Sonya Partymaker
time limit per test: 1.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
3
1 3 5
Output
1
Input
6
2
1 6
Output
2
Input
406
6
1 2 3 204 205 206
Output
100
----------------------------------------------------------------------------------------------------
