Pinely Round 3 (Div. 1 + Div. 2)


A. Distinct Buttons
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
3
1 -1
0 0
1 -1
4
-3 -2
-3 -1
-3 0
-3 1
4
1 1
-1 -1
1 -1
-1 1
6
-4 14
-9 -13
-14 5
14 15
-8 -4
19 9
6
82 64
39 91
3 46
87 83
74 21
7 25
1
100 -100
Output
YES
YES
NO
NO
YES
YES
----------------------------------------------------------------------------------------------------
B. Make Almost Equal With Mod
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
4
8 15 22 30
5
60 90 98 120 308
6
328 769 541 986 215 734
5
1000 2000 7000 11000 16000
2
2 1
Output
7
30
3
5000
1000000000000000000
----------------------------------------------------------------------------------------------------
C. Heavy Intervals
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
2
8 3
12 23
100 100
4
20 1 2 5
30 4 3 10
2 3 2 3
Output
2400
42
----------------------------------------------------------------------------------------------------
D. Split Plus K
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
9
2 1
3 4
2 3
7 11
3 10
100 40 100
2 1
1 2
2 2
1 2
1 327869541
327869541
5 26250314066
439986238782 581370817372 409476934981 287439719777 737637983182
5 616753575719
321037808624 222034505841 214063039282 441536506916 464097941819
5 431813672576
393004301966 405902283416 900951084746 672201172466 518769038906
Output
3
1
4
-1
-1
0
3119
28999960732
-1
----------------------------------------------------------------------------------------------------
E. Multiple Lamps
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
4 0
5 2
4 1
5 1
15 9
7 8
8 9
9 10
10 9
11 1
12 2
13 3
14 4
15 5
5 4
1 2
2 3
3 4
4 5
Output
-1
4
3 5 1 2
3
8 9 10
1
5
----------------------------------------------------------------------------------------------------
F1. Small Permutation Problem (Easy Version)
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
5
1 2 3 4 5
6
0 2 2 2 4 6
6
0 1 3 4 5 5
6
1 2 3 2 4 6
15
0 0 1 1 1 2 3 4 5 6 7 9 11 13 15
Output
1
4
0
0
532305727
----------------------------------------------------------------------------------------------------
F2. Small Permutation Problem (Hard Version)
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
10
5
-1 -1 -1 -1 -1
5
1 2 3 4 5
6
0 2 2 2 -1 -1
6
-1 -1 -1 -1 -1 5
6
-1 -1 3 2 -1 -1
15
0 0 -1 -1 -1 2 2 -1 -1 -1 -1 9 11 13 15
6
0 2 2 2 4 6
6
0 1 3 4 5 5
6
1 2 3 2 4 6
15
0 0 1 1 1 2 3 4 5 6 7 9 11 13 15
Output
120
1
4
0
0
494403526
4
0
0
532305727
----------------------------------------------------------------------------------------------------
G. Pumping Lemma
time limit per test: 2 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
4 8
abcd
abcbcbcd
Output
1
Input
3 5
aaa
aaaaa
Output
5
Input
12 16
abbababacaab
abbababababacaab
Output
8
----------------------------------------------------------------------------------------------------
H. Parallel Swaps Sort
time limit per test: 7 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
5
2 5 4 1 3
Output
5
1 4
1 2
2 5
1 4
4 5
Input
9
1 2 3 4 5 6 7 8 9
Output
0
Input
10
6 4 2 3 8 10 9 1 5 7
Output
15
1 8
6 9
1 8
3 10
1 10
1 10
1 6
6 9
6 9
2 7
9 10
5 10
1 6
2 9
1 10
----------------------------------------------------------------------------------------------------
I. Short Permutation Problem
time limit per test: 7 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
3 2
Output
77824
Input
4 1000000000
Output
30984329
Input
8 327869541
Output
85039220
Input
4000 1149333
Output
584870166
----------------------------------------------------------------------------------------------------
