2016 TCO Round 1A, 500-Pointer (EllysSocks)

James S. Plank

Sat Nov 19 10:11:08 EST 2016

Problem Statement.
A main() with the examples compiled in (Including my Example 5 below)
A skeleton that compiles with main.cpp.
tests.sh - MD5 hash: 43814f8f242bc38d69679170221c89ff
answers.txt - MD5 hash: 603eadadf6dafeeccb2170446b8c13ab
Problem Given in Topcoder: 2016
Competitors who opened the problem: 892
Competitors who submitted a solution: 585
Number of correct solutions: 508
Accuracy (percentage correct vs those who opened): 57.0%
Average Correct Time: 19 minutes, 45 seconds.

In case topcoder's servers are down, here is a summary of the problem:

You are given a vector of integers, S and a number P.
The elements of S are called "socks" in the topcoder writeup. You don't need to care about why.
Your goal is to choose P distinct pairs of numbers from S such that the maximum difference between socks in a pair is minimized.
You are to return the biggest difference among those pairs.
S's size is ≤ 1000.
The elements of S are between 1 and 10⁹.
P times two is ≤ S.

Examples:

Example	Input: S and P	Output	Comments
0	{42, 37, 84, 36, 41, 42}, 2	1	Choose (36,37), and (42,42)
1	{42, 37, 84, 36, 41, 42}, 3	42	All socks have to be included, so the best you can do is include (84,42).
2	{5, 2, 8, 8, 6, 7, 3, 7, 4, 2, 4, 5, 3, 6}, 7	0	You can match every pair perfectly.
3	{17, 3, 13, 3, 2, 17, 11, 5, 5, 7, 11, 7, 13, 19}, 7	4
4	This is a big one -- just read the main.	12866316
5	{ 20, 1000, 1050, 1099, 1500, 3000, 3010, 3022, 6000}, 3	401

Testing yourself

Standard tests.sh and answers.txt. Random test cases are generated when the command line is > 5.

Hints

Your temptation here is to solve this with a greedy algorithm. Something like: choosing the best pair of socks, and removing them from the Sock array, and then maybe putting them back and matching them with the socks around them.

Don't give into that temptation, because this problem has a really straightforward dynamic programming solution. First, sort the socks. Now, let's consider the first sock. Either you are going to match that sock with the next one, or you are not going to match it at all. Let's consider both cases:

If you do match it with the next one, then you can remove the socks, and solve the problem where you have to match P-1 pairs of socks.
If you do not match it, then you can remove it, and solve the problem by finding P pairs of socks from the remaining socks.

The better of these two cases will be your answer.

So, what I did was sort the socks and make the sock vector a member of my class. Then, I wrote the following method:

int GD(int index, int npairs)

This method returns the best answer when I need npairs pairs of socks, and I'm ignoring any socks whose indices are less than index. I'll solve getDifference() by returning GD(0,P).

I have two base cases. If npairs is zero, then my answer is zero, because I have not more matches to make. If index is too big, and I don't have enough socks to make even one pair of socks, then I return a large sentinel -- 1,000,000,001.

Otherwise, I have two cases to try:

Matching S[index] with S[index+1], and calling GD(index+2, pairs-1).
Ignoring S[index] and simply calling GD(index+1).

The better of these two is my answer.

Below, I'm going to show you the memoization cache for each of the example problems. I've added and example #5 to the mix too: { 20, 1000, 1050, 1099, 1500, 3000, 3010, 3022, 6000}. This is a nice example to step through by hand if you're having problems. Use the printouts below to help you.

Example 5 - Answer is 401

Socks: 20 1000 1050 1099 1500 3000 3010 3022 6000

Index / Pairs	1	2	3
0	-1	-1	401
1	-1	-1	401
2	-1	49	1500
3	-1	401	2978
4	10	1500	1000000001
5	10	2978	1000000001
6	12	1000000001	1000000001
7	2978	1000000001	1000000001
8	-1	-1	-1

Example 0

Socks: 36 37 41 42 42 84

Index / Pairs	1	2
0	-1	1
1	-1	4
2	0	42
3	0	1000000001
4	42	1000000001
5	-1	-1

Example 1

Socks: 36 37 41 42 42 84

Index / Pairs	1	2	3
0	-1	-1	42
1	-1	-1	1000000001
2	-1	42	1000000001
3	-1	1000000001	1000000001
4	42	1000000001	1000000001
5	-1	-1	-1

Example 2

Socks: 2 2 3 3 4 4 5 5 6 6 7 7 8 8

Index / Pairs	1	2	3	4	5	6	7
0	-1	-1	-1	-1	-1	-1	0
1	-1	-1	-1	-1	-1	-1	1000000001
2	-1	-1	-1	-1	-1	0	1000000001
3	-1	-1	-1	-1	-1	1000000001	1000000001
4	-1	-1	-1	-1	0	1000000001	1000000001
5	-1	-1	-1	-1	1000000001	1000000001	1000000001
6	-1	-1	-1	0	1000000001	1000000001	1000000001
7	-1	-1	-1	1000000001	1000000001	1000000001	1000000001
8	-1	-1	0	1000000001	1000000001	1000000001	1000000001
9	-1	-1	1000000001	1000000001	1000000001	1000000001	1000000001
10	-1	0	1000000001	1000000001	1000000001	1000000001	1000000001
11	-1	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
12	0	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
13	-1	-1	-1	-1	-1	-1	-1

Example 3

Socks: 2 3 3 5 5 7 7 11 11 13 13 17 17 19

Index / Pairs	1	2	3	4	5	6	7
0	-1	-1	-1	-1	-1	-1	4
1	-1	-1	-1	-1	-1	-1	1000000001
2	-1	-1	-1	-1	-1	4	1000000001
3	-1	-1	-1	-1	-1	1000000001	1000000001
4	-1	-1	-1	-1	4	1000000001	1000000001
5	-1	-1	-1	-1	1000000001	1000000001	1000000001
6	-1	-1	-1	4	1000000001	1000000001	1000000001
7	-1	-1	-1	1000000001	1000000001	1000000001	1000000001
8	-1	-1	4	1000000001	1000000001	1000000001	1000000001
9	-1	-1	1000000001	1000000001	1000000001	1000000001	1000000001
10	-1	4	1000000001	1000000001	1000000001	1000000001	1000000001
11	-1	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
12	2	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
13	-1	-1	-1	-1	-1	-1	-1

Example 4

Socks: 7097711 14685971 15198493 20544910 25475624 30574577 39073007 40498239 53612697 81133258 84672537 94092596 103237637 103522060 107063881 113911604 126303054 131752569 133711906 136721027 138749191 147944789 150802600 153380496 156513984 173978710 177512688 182506778 183966551 189375153 196140741 198304613 213794688 219972874 248268555 262522458 275731772 283496852 296707007 310701088 323567404 339840186 359573809 361913171 361931892 368550363 372047868 379821990 404620563 417177802 418932836 444803289 471852627 478582453 479711181 483031419 519074050 522136404 537655880 540721924 545404205 547204602 547914047 551745921 579004999 581869303 609397213 638781100 640439653 647984700 676943010 684602223 708632712 712568903 735241235 746745228 755486970 758242872 764919655 795755685 802611721 809094427 811450930 812852787 826647953 857788837 867128744 867889991 870676136 879609715 884392679 884870761 892462744 902841101 910208077 913778155 944672732 946129058 949333986 967048445

Index / Pairs	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42
0	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316
1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	13114458
2	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155
3	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	13114458	13210155
4	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166
5	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	13114458	13210155	13795166
6	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782
7	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	13114458	13210155	13795166	16272782
8	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459
9	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459
10	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17464726	17714459
11	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453
12	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17464726	17714459	25870453
13	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453	28958310
14	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17464726	17714459	25870453	28958310
15	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884
16	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17464726	17714459	25870453	28958310	31140884
17	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001
18	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17464726	17714459	25870453	28958310	31140884	1000000001
19	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001
20	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17464726	17714459	25870453	28958310	31140884	1000000001	1000000001
21	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001
22	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17464726	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001
23	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001
24	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17464726	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001
25	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001
26	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	9339907	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001
27	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
28	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	9339907	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
29	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
30	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	9339907	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
31	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
32	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	9339907	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
33	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
34	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	9339907	12866316	13210155	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
35	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	9339907	12866316	13210155	13795166	17714459	24798573	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
36	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	8741742	9339907	12866316	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
37	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	9339907	12866316	13210155	13795166	17714459	24798573	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
38	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	8741742	9339907	12866316	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
39	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	8741742	9339907	12866316	13795166	17714459	24798573	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
40	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7774122	8741742	9339907	13795166	16272782	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
41	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7774122	8741742	9339907	13795166	17714459	24798573	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
42	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7659213	7774122	8741742	9339907	13795166	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
43	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7659213	8741742	9339907	13795166	17714459	24798573	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
44	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7659213	7774122	8741742	9339907	13795166	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
45	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7659213	8741742	9339907	13795166	17714459	24798573	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
46	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7659213	7774122	8741742	9339907	13795166	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
47	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7659213	8741742	9339907	13795166	17714459	24798573	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
48	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7591983	7659213	8741742	9339907	13795166	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
49	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
50	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7591983	7659213	8741742	9339907	13795166	17714459	25870453	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
51	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
52	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	6729826	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
53	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
54	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	6482706	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
55	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
56	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	6482706	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
57	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7591983	7659213	8741742	9339907	13795166	17714459	27527910	28958310	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
58	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	6482706	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
59	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7591983	7659213	8741742	9339907	13795166	17714459	27527910	28958310	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
60	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	6482706	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
61	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7591983	7659213	8741742	9339907	13795166	17714459	27527910	28958310	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
62	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	6482706	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
63	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	7591983	7659213	8741742	9339907	13795166	17714459	27527910	28958310	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
64	-1	-1	-1	-1	-1	-1	-1	-1	-1	6482706	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
65	-1	-1	-1	-1	-1	-1	-1	-1	-1	7591983	7659213	8741742	9339907	13795166	17714459	27527910	28958310	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
66	-1	-1	-1	-1	-1	-1	-1	-1	6482706	7591983	7659213	8741742	9339907	13795166	17714459	28958310	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
67	-1	-1	-1	-1	-1	-1	-1	-1	6482706	7591983	7659213	8741742	9339907	13795166	17714459	28958310	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
68	-1	-1	-1	-1	-1	-1	-1	6482706	7545047	7591983	7659213	8741742	9339907	13795166	17714459	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
69	-1	-1	-1	-1	-1	-1	-1	6482706	7591983	7659213	8741742	9339907	13795166	17714459	28958310	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
70	-1	-1	-1	-1	-1	-1	3936191	6482706	7591983	7659213	8741742	9339907	13795166	17714459	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
71	-1	-1	-1	-1	-1	-1	3936191	6482706	7591983	8741742	9339907	13795166	17714459	24030489	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
72	-1	-1	-1	-1	-1	3570078	3936191	6482706	7591983	8741742	9339907	13795166	17714459	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
73	-1	-1	-1	-1	-1	3570078	6482706	7591983	8741742	9339907	13795166	17714459	22672332	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
74	-1	-1	-1	-1	2755902	3570078	6482706	7591983	8741742	9339907	13795166	17714459	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
75	-1	-1	-1	-1	2755902	3570078	6482706	7591983	8741742	9339907	13795166	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
76	-1	-1	-1	1456326	2755902	3570078	6482706	7591983	9339907	13795166	17714459	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
77	-1	-1	-1	1456326	3570078	6482706	6676783	7591983	9339907	13795166	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
78	-1	-1	1401857	1456326	3570078	6482706	7591983	9339907	13795166	17714459	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
79	-1	-1	1401857	1456326	3570078	6482706	7591983	9339907	13795166	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
80	-1	761247	1401857	1456326	3570078	6482706	7591983	9339907	17714459	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
81	-1	761247	1401857	1456326	3570078	7591983	9339907	13795166	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
82	478082	761247	1401857	1456326	3570078	7591983	9339907	17714459	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
83	478082	761247	1456326	3570078	7591983	9339907	13795166	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
84	478082	761247	1456326	3570078	7591983	9339907	17714459	31140884	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
85	478082	761247	1456326	3570078	7591983	9339907	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
86	478082	761247	1456326	3570078	7591983	10378357	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
87	478082	1456326	2786145	3570078	7591983	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
88	478082	1456326	3570078	7591983	10378357	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
89	478082	1456326	3570078	7591983	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
90	478082	1456326	3570078	10378357	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
91	1456326	3570078	7591983	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
92	1456326	3570078	10378357	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
93	1456326	3570078	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
94	1456326	3570078	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
95	1456326	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
96	1456326	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
97	3204928	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
98	17714459	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001	1000000001
99	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1