Hello 2022


A. Stable Arrangement of Rooks
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
3 2
3 3
1 1
5 2
40 33
Output
..R
...
R..
-1
R
.....
R....
.....
....R
.....
-1
----------------------------------------------------------------------------------------------------
B. Integers Shop
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
2
2 4 20
7 8 22
2
5 11 42
5 11 42
6
1 4 4
5 8 9
7 8 7
2 10 252
1 11 271
1 10 1
Output
20
42
42
42
4
13
11
256
271
271
----------------------------------------------------------------------------------------------------
C. Hidden Permutations
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
4
3
2
1
4
2
4
4
Output
? 3
? 2
? 4
! 4 2 1 3
? 2
? 3
? 2
! 1 3 4 2
----------------------------------------------------------------------------------------------------
D. The Winter Hike
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1
0 8
1 99
2
0 0 0 0
0 0 0 0
9 9 2 2
9 9 9 9
2
0 0 4 2
0 0 2 4
4 2 4 2
2 4 2 4
4
0 0 0 0 0 0 0 2
0 0 0 0 0 0 2 0
0 0 0 0 0 2 0 0
0 0 0 0 2 0 0 0
0 0 0 2 2 0 2 2
0 0 2 0 1 6 2 1
0 2 0 0 2 4 7 4
2 0 0 0 2 0 1 6
Output
100
22
14
42
----------------------------------------------------------------------------------------------------
E. New School
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
1 1
30
3
25 16 37
4 2
9 12 12 6
2
4 5
3
111 11 11
Output
101
00100
----------------------------------------------------------------------------------------------------
F. Strange Instructions
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
5 2 2 1
01101
6 4 3 5
110001
6 3 2 1
011110
Output
3
11
4
----------------------------------------------------------------------------------------------------
G. Weighted Increasing Subsequences
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
5
6 4 8 6 5
4
1 2 3 4
3
3 2 2
4
4 5 6 5
Output
4
12
0
6
----------------------------------------------------------------------------------------------------
H. Trains and Airplanes
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
8
1 2 7
2 3 4
2 4 3
4 5 1
5 6 6
4 7 10
6 8 6
4
AABABBDB
11 12 10 42
16 15 15 30
4
6
3 2
1 A 10
3 3
2 A 3
3 7
3 6
Output
0
10
6
6
----------------------------------------------------------------------------------------------------
I. Two Sequences
time limit per test: 8 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
2 1 3 1
4
1 1
1 2
1 3
1 4
Output
2
1
1
3
----------------------------------------------------------------------------------------------------
