10827 - Maximum sum on a torus

[Sedefcho]

Can someone post more test data ?
I first had one O(N^4) solution which was getting TLE.

I rewrote everything so that I use now an O(N^3) algorithm.
The problem is that this algorithm now gets WA and I don't
find any bugs in my code. My code produces same output
as the one posted by liulike.

I also tried the strategy where we do not allow empty subrectangles
( that is we allow only subrectangles with both sizes >= 1).
If this strategy is followed I have the following output:

Code: Select all

1
15
9
-2
-10
-2
-10
1000
15
15
10
15
45

Now the point is ... Are there some critical cases or not really ?
Is somewhere on the web some test data posted ?

Thanks in advance!

[Sedefcho]

I fixed my solution but in such a way that it makes my time complexity
O(N^4) in some special cases. With that fix I managed to get ACC
but of course my runtime is bad ( about 4 secs ).

Now I have the following question which arised from
the problem I had and from the way I fixed that problem.

1) The so-called "Maximum Contiguous Subarray Problem" is quite
well known and it is also well known that there is an O(N) solution
for it ( where N is the size ot the array ).

2) Suppose we change slightly the classical problem in the following
way: a) we treat our array as cyclic ; b) we are interested in the
"Maximum Contiguous Subarray" BUT we allow that subarray to
have a lenght of at most N. That means we do not want in our
subarray some elements of the original array to be included twice.

3) Now my question is : how do we decently modify the original
linear time algorithm so that it solves the changed problem and
so that it still remains a linear time algorithm.

Does anyone know some sources on the web on that particular
problem ( on that variation of the original "Maximum Contiguous Subarray Problem" ) ?

[misof]

3) Now my question is : how do we decently modify the original
linear time algorithm so that it solves the changed problem and
so that it still remains a linear time algorithm.

Either the sequence you seek or the rest of the numbers form a contiguous part of the original sequence.
I.e. the situation looks either this way

Code: Select all

BBBGGGGGGBB

or this way:

Code: Select all

GGGBBBBBGGG

(G are the good numbers forming the maximum-sum subsequence).

The first case is exactly the original problem, the best solution for the second case is (sum of all numbers) minus (subsequence with the smallest sum, found using the same algorithm)

[Sedefcho]

Pretty simple ! Although not so obvious at first sight.

Thank you.

I implemented that idea and it made my running time 4 times
faster which is normal as now my whole algorithm really
has a O(N^3) time complexity. Now I get ACC in about
0.900 secs which is pretty good for me.

Thanks once again for the nice idea.

[Chok]

Hi all,
There is lots of input in this thread, but i'm confuced abt the ouput. Please anyone provide the output for those case or other input. Another thing, if i got neg value then what should i print -(neg) or 0 (zero). My idea for this problem is generate all of the combination sum by row then generate circular/coloum-wise best sum. is it ok ? thankx in advance.

[Sedefcho]

Chok,

Right now I do not remember a lot of details about
that problem. I just remember it was difficult for me
to get ACC on it. Here is some sample I/O from
my ACC program.


INPUT

Code: Select all

13 
2 
-1 1 
1 -1 
5 
1 2 4 3 -3 
-1 3 1 -2 2 
0 -2 -1 1 4 
0 -3 5 -3 1 
-4 2 0 2 -4 
4 
1 0 0 1 
0 -1 -1 0 
0 4 -1 0 
1 0 0 2 
2 
-2 -5 
-4 -3 
1 
-10 
2 
-2 -3 
-4 -5 
1 
-10 
1 
1000 

5 
1 -1 0 0 -4 
2 3 -2 -3 2 
4 1 -1 5 0 
3 -2 1 -3 2 
-3 2 4 1 -4 
5 
1 2 4 3 -3 
-1 3 1 -2 2 
0 -2 -1 1 4 
0 -3 5 -3 1 
-4 2 0 2 -4 
2 
1 2 
3 4 
5 
1 -1 0 0 -4 
2 3 -2 -3 2 
4 1 -1 5 0 
3 -2 1 -3 2 
-3 2 4 1 -4 
3 
1 2 3 
4 5 6 
7 8 9

OUTPUT

Code: Select all

1
15
9
-2
-10
-2
-10
1000
15
15
10
15
45

Try these test cases.

[Moha]

My code passed all of these test cases, but still WA? can anybody help me?
Please!!!
My code is above and I think I have a misunderstanding in this problem, because my source code seemes to be correct.
this is my algorithm:
i double the input array, then i preform a simple 2d maximum sum in rectangle.
Oh my God, Where is the BUG??

[shamim]

Another thing, if i got neg value then what should i print -(neg) or 0 (zero).

It should be 0.

[Moha]

Due to Shamim and Sedefcho posts, I think there is no test case in judge test data, which all the board filled by negative numbers. we shouldn`t envolve us with such these test cases. But this problem has a very nasty point, which i don`t find it out yet. i really want to know judge test case, because I believe( some how) my solution is ok!!

But the question is Where is the problem with my code?

[Chok]

Hi all,
Thanks Sedefcho and Shamim. I've got accepted with O(n^4). now i'll try it for O(n^3). Thanks again.

[Moha]

Can anybody test these testcases with a accepted code?
Input

• 10
  59
  54 -52 -8 44 -44 -65 -51 1 89 25 20 -38 30 -20 -51 43 97 -26 57 65 -75 -86 -87 64 88 100 40 -38 44 -46 -43 -32 -15 -77 -95 -38 -37 -27 77 31 80 37 33 -21 -100 37 22 81 94 -76 65 89 -4 24 7 78 17 -39 -22
  -93 -94 -97 -65 -20 -67 78 -42 -32 -49 60 -44 -75 -17 11 -40 -95 0 -82 0 -56 30 64 66 18 19 2 81 -91 -91 70 -73 97 -21 -70 -46 -54 -92 47 -46 -38 75 -61 84 86 19 37 -86 97 -44 -60 -58 -31 63 -73 76 73 83 -4
  51 -7 77 -95 10 0 23 -9 39 -97 84 44 -11 8 83 -27 34 35 -10 39 -53 -40 66 90 -55 -39 88 -97 32 -60 83 80 53 94 -77 16 3 71 4 -6 13 -30 -27 66 -64 -5 44 -29 -65 59 87 36 29 -92 -34 59 76 13 -48
  -27 37 -25 83 77 -9 55 -76 18 -64 4 -74 77 18 -84 -36 -10 75 -87 22 37 -65 59 -14 79 54 8 12 -9 42 95 70 -83 40 -34 66 -59 -95 3 -62 19 98 -8 80 -72 43 -65 71 89 -49 -5 59 -11 -49 28 -29 92 41 -1
  -50 7 -4 -37 86 -19 -14 15 -55 93 73 80 -100 94 3 -27 -33 -78 -73 -80 5 59 -22 59 32 47 3 39 97 -9 60 85 38 -63 -8 35 -6 100 -66 -39 41 -34 -11 80 4 74 -92 89 -19 -6 26 -8 67 -95 -99 96 51 -83 -35
  71 16 -69 -35 3 -41 -49 -83 67 -97 13 60 -33 -71 -39 -43 -77 -53 33 34 -8 79 9 -46 43 2 -70 31 -4 -84 39 -52 -52 93 -59 21 35 -57 -28 -86 78 -94 48 83 59 28 25 46 51 -62 -32 43 -15 -77 -68 -47 82 -26 -98
  -13 -7 55 -55 76 5 -15 53 36 -23 -10 -6 -69 29 -49 36 -84 71 8 -71 -97 88 -46 35 7 27 -82 40 -88 44 62 32 -55 49 94 14 63 -68 75 -23 27 65 85 -57 39 7 46 -12 -41 -31 14 91 -12 -17 -26 0 92 60 1
  46 -84 -8 -93 64 14 0 72 -71 81 -70 -96 -26 -1 95 -70 -9 94 -15 -71 -87 -5 -13 -10 -94 -38 98 -99 86 -43 -35 20 -98 -61 66 -24 -82 72 39 11 -38 27 49 -59 58 81 -80 -70 46 56 -27 63 -77 -36 -48 81 -62 55 100
  -78 81 -83 -91 2 14 47 -72 83 10 -96 -65 78 -16 -70 11 -5 -71 84 73 -96 -77 95 -19 -62 -61 -20 -66 85 96 -64 -67 -30 23 97 66 50 0 -57 54 82 -8 73 -66 22 43 0 -21 79 -44 -40 -99 17 67 -51 -25 0 0 -40
  96 93 81 13 90 46 32 -75 -8 -97 99 -61 -46 -89 -34 -78 24 -34 -96 73 -72 50 36 67 -82 51 43 35 39 0 -86 34 46 80 -48 -92 36 -55 -31 49 -51 59 44 -48 85 -21 58 -45 -90 -11 43 -89 77 -84 66 88 -66 77 6
  59 39 26 -68 0 -28 -27 -48 82 60 -32 65 -74 -32 -72 -41 96 43 42 25 34 -88 -56 -44 -25 69 27 -9 -96 -84 12 -30 -36 -95 16 53 -71 -44 -7 -30 23 -23 -65 -17 -73 60 57 92 96 36 -4 -61 96 -68 -25 -69 28 -31 -56
  -86 -81 12 1 29 89 41 20 67 73 52 -64 78 78 -17 -22 95 -48 39 -43 -79 66 -23 -54 34 -57 56 72 79 -42 15 65 67 -82 -95 -6 21 92 -91 -67 -38 -43 -76 28 63 84 0 53 94 -40 -92 -93 17 -23 30 64 45 -28 20
  7 59 26 -5 26 -79 52 11 -83 95 -1 27 -25 4 24 -8 -73 89 25 77 -24 -16 -58 -53 -55 -78 -38 -88 -8 48 -48 97 89 18 78 99 48 44 -42 11 -10 19 25 77 30 99 -13 98 -12 -82 -8 93 61 28 -66 65 -61 -90 22
  52 -22 -96 -10 -70 40 80 -98 37 40 60 -2 -47 -7 -15 34 -48 83 24 -69 48 11 90 31 32 -90 -9 48 -55 -25 51 69 83 -74 -76 67 17 -17 -18 -65 -87 -7 11 85 -77 68 70 24 53 24 6 -86 67 62 -17 34 -46 32 63
  -56 -26 -65 -26 -80 -52 -6 27 -47 -61 -45 -67 -14 53 -36 28 -87 47 83 72 -85 -33 -48 49 53 -36 53 -10 -82 79 45 -41 95 82 27 5 77 -69 -98 -53 -93 81 58 12 -54 90 64 -62 86 -1 -63 91 -44 30 8 -23 -38 -45 -61
  -1 81 45 -89 -69 83 -52 75 -85 -100 92 30 -74 52 -96 -8 94 55 100 -11 83 3 39 9 63 -37 -83 -1 -67 7 66 -25 71 63 -89 3 35 38 51 -30 -21 100 100 -26 87 27 -15 -43 -99 22 -47 24 99 21 -75 -95 84 -66 28
  14 -58 -33 61 92 -48 79 6 76 98 -87 14 1 7 81 -92 -16 3 54 57 55 -93 100 70 69 39 5 -2 51 40 78 60 -79 -75 59 -10 2 80 67 10 -16 -23 -68 95 68 -84 -64 -71 -72 -40 -42 76 -86 80 -4 -88 -4 -75 69
  -23 -35 80 -15 6 -61 -49 -29 80 47 -34 14 -38 98 -57 13 0 53 -12 -29 -54 30 -25 94 41 -30 -58 62 96 40 58 -64 67 -4 17 -63 56 -39 18 -51 -5 100 58 24 87 -37 83 -34 -50 27 4 70 15 -6 -40 59 -4 -75 86
  81 -29 48 84 -27 87 -32 77 16 -9 92 79 95 -40 -10 -35 -29 74 -8 -92 23 -23 0 56 -58 4 -14 -31 32 10 63 100 42 -1 -97 -18 36 75 -7 18 -96 -12 71 -50 -80 78 -72 0 -15 30 60 31 -56 98 1 26 -3 -72 -81
  76 -15 -35 96 -67 69 -21 10 90 23 -61 -34 -88 91 9 81 64 3 -82 100 42 -10 -62 -48 19 70 28 100 73 8 -94 33 84 -21 1 -46 -20 4 -9 99 -56 8 3 66 64 24 -28 81 59 -9 -55 1 -77 -23 24 82 22 30 -63
  -34 -36 -51 47 -8 -100 99 -72 -97 73 34 -74 -43 -37 -55 34 -94 80 -67 7 65 -92 95 30 77 -42 -65 -59 45 46 63 20 -83 32 -59 90 12 -53 -9 -29 17 64 -54 -90 -85 -30 -83 35 -83 14 73 97 51 -24 -65 -79 -91 65 98
  -41 -22 62 -54 -36 30 9 -86 53 88 -29 97 -1 83 -30 52 94 -42 45 85 -98 97 83 44 85 45 85 -54 -60 84 48 61 -42 96 30 0 26 -32 -46 42 -7 -43 94 9 99 -43 61 -19 -4 -22 -26 -60 -53 -93 -68 61 88 33 66
  35 68 8 81 63 -8 -86 -41 53 3 -58 13 -11 55 -82 19 84 27 -81 -86 -58 -27 -62 21 61 93 -61 70 73 -16 -77 3 88 -18 3 -9 30 37 4 73 -48 83 3 -80 8 62 63 -78 27 50 32 24 63 -20 51 65 -90 73 -66
  0 47 -26 94 59 -66 -17 0 25 -68 97 70 -49 -8 18 -6 15 48 -61 -10 -62 95 5 53 -58 8 5 81 4 -8 -97 74 -100 18 -29 -46 37 -2 -1 -5 43 79 -59 -35 -81 84 24 20 -45 -17 100 31 -3 -44 55 -96 -30 12 -65
  50 57 55 -91 38 -46 76 17 81 6 57 41 25 92 -92 16 -35 40 21 98 -100 80 89 -82 50 -27 14 -25 -4 -8 5 69 -65 63 -72 10 -70 -12 -52 -95 13 -41 -55 100 -48 -53 -99 60 -62 14 -49 71 -46 77 42 -32 -24 -15 4
  36 -21 39 -76 49 -88 -4 54 20 -24 31 0 -54 69 -36 83 58 27 -56 -28 74 -35 17 18 88 0 41 14 59 -63 54 66 -81 -41 29 75 50 -46 30 71 -39 -2 4 -40 -98 -57 13 30 -82 -29 -6 -79 -79 -56 21 -94 63 72 45
  29 13 -94 75 -18 -27 -33 -17 55 -69 38 2 48 93 32 30 -46 -13 -1 -96 9 100 -21 20 -80 19 10 -14 19 77 -77 79 15 94 45 68 -43 63 -51 -39 -3 -13 -45 -3 100 -48 52 64 50 82 -45 82 -49 85 59 -96 81 7 -68
  90 -56 76 97 73 -30 40 35 29 -64 50 -37 -16 87 77 -100 55 -35 -95 -2 -10 -53 74 -70 -38 83 55 -67 71 60 40 45 -46 58 78 39 -93 70 11 0 72 -71 36 -29 -56 19 -80 -23 -43 -98 -41 40 60 -31 -14 -53 -47 -44 26
  -55 27 11 -70 -64 -82 -66 -29 -88 -15 -93 -82 82 -1 78 65 -42 -39 -31 -54 -89 22 90 60 6 27 72 -10 -70 -45 4 -13 69 66 27 61 -53 36 -35 -85 -37 40 53 -95 94 -36 -15 -10 34 -16 -28 43 60 -90 74 -2 18 18 -24
  60 -85 81 78 16 34 38 75 9 -59 62 6 -43 72 62 40 79 -49 90 84 3 -70 11 -89 46 53 -80 -38 83 15 -38 -31 45 8 73 73 -75 -51 -54 -40 86 -39 -17 19 -19 77 22 39 20 -35 -5 2 -16 -66 -91 -68 30 -40 83
  -79 27 24 96 -83 -78 41 -92 62 28 77 99 -95 -84 -41 60 -34 -41 -36 89 85 2 47 35 67 2 81 54 96 9 -36 23 -22 -62 33 8 48 -8 -70 -70 5 46 74 27 -70 -72 -37 42 -25 49 19 7 0 28 -92 -74 70 -14 -52
  -45 -43 -93 44 -72 4 -59 11 57 13 48 49 33 -40 -61 55 79 -54 -11 -72 32 70 -33 89 25 7 39 -27 -6 -53 -24 38 38 -73 56 99 54 11 48 -42 35 -11 -71 -45 -71 10 -38 63 41 -92 -47 51 -56 -53 -29 -76 -44 70 -58
  -58 45 -56 84 -59 21 87 -72 0 33 -31 47 -58 -26 -38 -75 -80 97 69 -20 -3 -43 -75 -27 8 27 88 78 -98 -71 55 -64 -99 1 -40 -61 -63 32 -51 79 18 -30 13 -49 78 79 99 -65 68 -96 -55 84 93 -88 -75 -34 72 -98 -37
  27 -99 80 -13 -92 -44 -55 9 -48 20 10 -1 86 -74 23 62 -93 -22 90 -15 49 -34 -23 -75 11 -40 -21 -32 13 -56 84 -52 44 -80 42 46 -20 27 -91 -48 29 -90 -95 -58 95 -9 -31 -19 1 -40 26 100 -32 23 -62 -91 -58 -41 68
  -25 79 5 27 83 56 37 -74 95 -97 95 -54 14 -31 -96 20 -27 -87 6 -23 -8 -77 26 82 -23 71 -68 -69 -2 3 64 -85 -21 -90 52 -83 -23 -38 10 -2 29 -16 65 -45 16 31 4 37 20 -20 -71 -64 62 9 -54 71 -51 -80 -4
  -83 39 68 -62 -35 -64 -19 -58 -95 -18 -58 81 55 -14 -47 92 6 76 40 -77 -19 30 -7 88 73 -71 78 58 -49 66 57 -58 54 -69 -37 1 18 60 51 59 -19 -87 -47 -28 -82 -58 17 68 15 -64 15 74 -62 92 14 2 -46 63 65
  20 50 -51 61 -72 89 -95 -67 -69 68 41 -77 -82 -98 47 0 74 -11 -84 77 -14 23 34 -42 -84 -63 58 -33 -94 15 -24 -6 -32 -56 56 70 97 -78 -48 99 -97 22 -32 -93 -52 31 90 6 -89 -35 60 -81 -63 -52 10 -8 44 94 -51
  -68 -59 -11 -70 -1 12 68 41 -95 73 47 29 56 -51 -16 67 71 -15 -6 66 -75 44 -15 -57 22 -89 -79 91 -57 82 -9 90 5 -28 22 19 3 -5 -81 61 -58 71 -67 -69 34 29 64 91 89 -47 -45 7 62 -100 41 -44 -9 -68 41
  -99 -87 -85 45 -53 26 10 -99 85 -62 -68 -11 -69 -92 96 39 -74 -87 -9 -100 -30 94 -62 90 17 -29 -55 -63 94 -92 -53 14 -23 17 98 26 7 34 -78 -13 41 -46 49 51 -97 -63 40 8 43 -61 -7 -68 -38 82 57 -43 37 93 -30
  -95 -19 -75 0 88 74 -50 67 -94 -51 -53 -69 -5 -16 -59 7 5 43 -17 -28 54 18 14 -88 -22 -48 -45 -2 -90 -14 31 -33 -81 49 -87 2 11 -76 -4 66 34 -33 98 -29 19 -67 30 20 8 -75 -79 33 96 49 38 -25 28 -51 59
  -44 -55 96 9 28 -50 -45 -11 86 53 73 -48 -29 22 34 -92 -25 -55 -64 68 -48 -93 -13 -2 -76 32 13 12 89 -89 -13 1 -59 -92 53 12 44 -92 -74 55 -15 -30 -99 71 75 -77 -4 -93 -66 -17 10 17 100 -77 -2 -89 50 -46 -93
  35 7 54 21 7 64 -38 87 -94 -64 -25 67 50 64 -30 10 -89 9 -95 -21 18 59 -24 78 97 -19 40 -67 68 -17 -52 30 -44 -49 -36 73 -21 -43 -42 -96 -28 -93 67 24 56 99 -35 -14 0 -51 -66 -57 -21 98 86 0 74 -15 -86
  40 47 -82 -100 95 -92 2 0 9 91 -17 -32 22 -43 -78 77 36 90 38 -46 -21 9 27 -14 98 77 46 99 -47 72 70 8 4 -55 53 -7 72 -63 26 1 13 -4 -19 -60 10 -22 -46 -17 95 -59 -5 -87 -48 -42 -58 31 -54 -97 4
  -37 -88 60 56 -50 81 -30 -6 -29 -99 96 47 -94 -27 5 -12 -11 67 66 -80 -6 23 47 -86 -51 80 74 -38 -59 -23 -29 38 -33 -44 -60 -48 -50 1 67 -5 -3 29 -77 10 -65 -65 0 32 -73 99 32 31 -84 -11 86 34 33 -32 -97
  -77 7 53 -76 -73 -27 -13 50 -73 9 -50 -32 -16 -12 6 89 1 -56 -35 39 46 -45 -57 -36 95 -80 73 -94 9 69 -47 -31 -18 69 18 -27 -5 55 -33 -58 -3 4 14 -31 37 -5 -23 99 -22 -61 -7 -2 -92 -41 -15 86 1 -60 87
  -5 -23 40 12 -19 -72 -7 -33 -59 34 16 31 -33 -23 47 -16 100 -29 -17 -44 43 -49 27 93 73 -18 -75 89 -13 -33 -55 80 20 -60 83 -5 17 8 -2 30 -27 63 -29 -42 96 -70 90 71 90 -79 66 64 4 -27 39 -80 4 100 60
  43 82 -5 27 46 38 89 -41 -52 57 -84 36 -27 -72 40 0 -18 95 -53 -31 -71 56 38 44 -7 2 97 87 -10 84 -21 -33 66 -96 82 -51 96 78 -70 90 -89 0 -28 42 10 -56 75 -2 49 59 -24 -15 48 18 81 61 -99 20 -13
  32 53 87 42 1 53 55 -1 28 29 33 53 -10 -87 45 -25 -89 97 -73 96 62 66 -91 -53 82 -98 90 -74 68 63 25 -55 33 20 -22 -11 -30 -67 -9 -72 -33 72 -86 -54 38 32 -72 76 71 -42 44 76 62 28 -27 27 -1 14 -10
  5 52 43 -91 -60 81 19 -87 -31 -3 18 -92 90 10 -45 -4 34 -54 11 62 -37 -4 99 -83 4 -55 49 0 38 74 97 -66 0 5 -62 15 41 87 9 -2 21 69 3 -40 -11 -23 92 -36 -40 -37 -75 32 -71 -89 19 -61 -13 8 -65
  -91 -62 -16 -34 78 -94 7 -33 -17 -56 -84 62 -48 -40 -58 71 12 94 -17 -81 67 -76 8 -45 79 -97 41 -39 -100 11 15 37 -46 -56 -90 -24 76 96 -41 -9 6 -14 -30 -2 -64 18 -27 -72 17 -1 96 -28 -59 56 96 -86 -3 15 -85
  96 63 59 1 -28 57 -92 -54 -23 -76 79 -43 -39 29 -12 37 60 -89 -55 -47 -75 -45 56 -19 -78 91 -99 86 45 -58 60 -32 -61 70 42 65 -20 83 -41 87 -28 40 76 98 -5 -11 16 -16 -29 -60 1 20 -67 29 -36 -25 -59 24 56
  -89 -42 58 -8 69 25 -40 85 81 96 58 -25 -63 -80 -52 -74 62 5 -73 -59 -16 1 -77 49 -3 66 43 -77 -8 -58 -92 66 -79 -39 84 59 -48 21 -80 47 82 10 -37 62 -10 71 -83 -88 6 -79 58 55 -98 -63 12 -25 -89 -50 56
  2 97 -100 75 73 47 -2 21 -42 -66 61 81 71 -89 27 32 -42 -69 -40 -95 -23 29 11 15 1 -24 -57 49 -40 48 13 -95 40 96 39 -58 98 53 71 29 -81 34 -24 -65 -52 29 -24 86 53 -77 -4 19 -55 -9 6 -63 -58 24 -79
  -78 -34 -28 -29 22 28 -39 -66 32 -97 78 46 -55 -71 51 1 46 34 26 -21 11 -80 -13 -75 99 -53 39 83 -35 40 69 81 8 21 11 49 57 5 -40 -14 -84 80 99 -84 48 87 97 64 48 -72 -60 -48 -82 -86 -66 -25 -32 39 0
  65 78 31 84 10 -11 -57 -70 20 -24 39 4 -5 1 33 66 16 81 49 -74 -97 -42 89 24 28 -13 70 -64 -86 -19 100 83 -61 -95 -95 -70 85 76 -55 -47 -80 -16 9 92 10 14 -28 91 -93 -32 -18 43 -45 42 85 48 82 -47 9
  -87 -81 96 29 -31 37 -75 -97 -92 -70 73 55 51 17 28 -68 79 -47 -91 27 30 16 52 56 -19 43 45 78 0 26 54 -75 76 73 -30 -86 -97 98 -80 92 -10 -56 -64 -85 95 -59 3 -46 88 77 51 10 -29 -96 94 73 53 25 62
  -47 53 -70 -73 68 0 -44 73 65 94 77 -79 23 -44 -14 -91 94 100 -31 -44 -32 9 -29 -96 -15 20 8 40 97 45 55 3 44 43 75 40 64 14 29 53 -31 69 -37 70 58 76 -16 -93 -49 68 89 -63 -56 11 -53 97 2 -89 6
  5 4 -43 -26 -13 -3 65 -88 -9 -70 29 16 72 56 -57 -50 93 8 7 2 42 -34 -63 66 -31 25 -91 51 -59 -55 -1 77 26 -95 -19 20 35 0 41 37 -34 99 -2 20 -23 77 -46 85 38 72 75 84 11 75 83 -91 -72 74 72
  36 -1 -85 -99 19 47 59 -48 -31 -59 -77 49 -91 56 96 -57 -88 76 4 74 -43 46 -7 -11 -18 -77 78 -62 47 30 -10 -72 -44 1 -54 4 -61 100 10 74 46 -23 -42 -23 -68 29 40 41 -14 66 -84 31 -53 45 6 25 1 42 65
  34
  32 -94 25 -83 -8 -74 -40 74 63 62 77 50 -48 3 28 -21 -20 -68 -9 54 74 92 4 -30 1 93 -5 -39 73 9 -78 -94 12 76
  44 37 -24 -97 60 61 -86 -4 62 9 -17 0 82 -25 -21 13 -30 -48 45 -48 37 -98 -62 -45 -43 -23 -5 -21 -17 -13 12 69 43 -29
  -94 -24 87 86 55 -4 51 57 -17 -8 56 -39 14 44 23 10 50 13 -55 -17 -95 6 -14 0 74 -33 97 30 79 33 47 -85 77 -66
  -62 73 -70 -68 75 -82 44 9 19 -84 -80 -66 60 90 14 -34 3 100 -18 -89 1 6 17 85 -88 67 -50 60 15 12 70 -73 85 -11
  -71 -95 -3 -16 -15 90 -34 36 20 94 -11 -32 84 -87 75 37 31 -50 31 -20 100 15 98 18 -80 20 -16 -72 55 -34 89 6 36 86
  -56 80 48 55 -78 30 -84 48 -34 -65 -43 84 37 -17 -79 -5 76 22 -45 -35 -83 13 -14 31 -46 -2 -61 -87 -8 2 74 -54 93 38
  85 94 -4 -99 -33 100 58 -33 -20 -49 -91 -14 25 -79 76 -89 22 -94 54 79 -54 -31 -12 62 -84 -94 28 37 -41 70 31 -43 -5 -12
  94 11 69 91 6 80 29 30 13 -9 15 -3 37 -31 -48 -34 34 -21 -54 16 -65 -15 -1 84 45 2 71 38 18 -49 12 74 94 -15
  -74 -6 -94 64 100 42 72 70 16 83 -77 66 80 1 1 20 81 45 48 -1 89 -58 54 -69 -1 -70 15 -99 7 -35 50 -15 14 -37
  -35 76 -47 -49 -60 2 2 71 6 -79 -36 89 -1 82 -30 44 -22 -54 52 -69 53 5 76 -73 11 -62 98 99 19 -80 65 46 8 -56
  -35 -4 62 -43 17 86 -65 42 -63 -26 -88 -64 -96 -72 -42 -64 -18 31 9 -84 21 -22 83 14 4 -61 -46 10 0 12 42 -86 -77 -5
  -22 79 -92 96 65 52 15 -94 3 -36 -17 -79 -90 -51 47 18 -79 -79 -98 76 -15 63 40 -25 -25 13 75 34 -22 97 75 72 77 -55
  -23 68 24 1 53 40 19 88 -78 -91 39 -1 -33 -32 22 16 -16 15 -81 37 76 -79 -63 21 86 -73 -30 -4 -46 5 56 79 -71 79
  -77 52 -25 -14 -95 61 13 4 74 39 -12 53 98 73 57 -52 -99 19 -66 79 34 -40 39 23 19 -64 38 32 -80 -69 88 -2 -91 -76
  -87 83 26 0 33 -9 -17 -16 -55 -56 -85 36 79 -90 93 58 86 -67 29 8 57 47 90 96 43 44 -75 -65 -52 55 86 -90 -53 15
  23 77 -41 19 86 -7 -65 21 31 -59 -73 59 25 62 4 -60 -34 39 -60 4 -72 6 -97 -76 -12 76 -13 -75 -83 -49 47 -47 -11 88
  -44 48 -71 -52 14 -94 27 -77 -69 10 54 72 0 -80 -37 -48 -93 -97 -16 96 -7 56 90 6 -50 -76 8 -3 -32 87 83 -16 98 -3
  93 44 86 -100 -65 -33 -88 16 22 -72 -35 -89 -59 -59 49 -70 -60 -40 11 -20 10 -22 -94 -61 -91 1 90 9 27 71 62 -50 -86 -33
  -62 39 -38 -37 33 -80 29 82 3 -100 91 -40 77 -6 -46 26 -58 -47 -59 59 47 -48 52 26 52 -52 63 26 48 68 37 -68 92 -56
  -64 -75 19 -52 84 -26 71 -43 2 4 68 76 -99 100 91 -73 -36 31 -1 93 28 52 -29 64 96 -13 -73 34 -65 -94 87 -77 -45 45
  91 -29 -22 49 74 -14 -47 65 48 -23 -64 -35 -15 40 18 5 -88 -26 -48 -59 54 -58 -32 -53 88 -60 -25 34 -5 34 91 -31 6 20
  33 -9 -18 -20 55 -31 -14 -26 -51 -13 0 -78 18 -1 -33 79 68 -85 -20 2 43 -84 56 -30 -35 -95 56 59 48 -31 82 12 97 -1
  -34 -58 -70 67 -16 99 -5 -19 -31 -68 37 -59 75 0 -67 20 38 -43 -85 -99 39 -84 -90 -38 46 100 -71 -35 28 -82 36 61 11 -47
  46 -28 8 63 81 -84 39 -43 40 20 -45 -28 -36 -20 -58 9 -45 22 -82 16 84 -22 -15 -98 8 -22 86 0 -4 -34 -20 99 47 -50
  -3 57 -31 -76 9 0 -91 -3 4 63 56 3 -6 73 -55 48 -54 11 16 -98 61 -76 53 60 48 32 -52 46 -3 78 -7 -48 -63 -12
  47 70 -75 91 -90 51 5 74 -85 -15 -3 -44 51 -38 52 -58 60 -38 39 28 11 -99 28 73 57 100 -14 3 -36 -79 -92 18 30 18
  -50 -98 -24 -43 0 -99 -37 -50 41 82 61 -97 29 2 -36 61 -66 -80 -87 41 -72 -9 3 -25 46 -54 100 58 -31 19 -80 -86 -71 -33
  -21 9 80 -67 11 94 -30 96 63 56 -79 27 89 -1 -44 49 -76 -23 -9 -4 13 -9 -77 -72 -91 -33 70 60 72 49 63 47 89 -25
  26 -85 25 16 -31 41 -48 58 100 -7 -45 19 -20 -78 3 -73 65 68 -16 -58 4 -36 -38 36 -43 75 -66 62 -60 27 -76 92 -22 63
  -9 -19 86 31 47 -61 -10 44 29 -95 79 -51 88 26 0 82 77 89 -88 52 53 -90 -14 72 6 -65 54 -4 23 -18 -52 -100 66 23
  -40 -19 20 89 42 -10 -93 -99 -22 -54 -66 -35 37 -12 -54 -54 76 -20 -48 -98 35 -4 15 -5 -38 -83 98 20 -84 -36 100 -64 -96 38
  25 -100 -8 -53 -38 27 -84 11 59 15 -97 -11 7 38 -58 -12 77 42 47 75 86 -94 43 -16 -3 -9 49 -62 -95 -92 41 35 48 69
  4 -47 -77 -25 -45 87 -5 14 -48 8 -76 -62 37 0 -6 80 10 -33 -33 -38 -32 93 52 -90 -48 -8 -64 -6 -33 -52 7 16 91 36
  -40 -67 -64 -41 -31 81 61 -35 25 -92 -80 -30 -6 36 -28 86 11 -6 78 -56 -10 55 -93 62 -98 75 28 -97 83 -98 71 80 -1 -23
  37
  45 -43 -76 -40 7 95 -31 -20 0 -84 51 -2 -40 1 -74 -91 -68 -67 80 -6 29 -46 5 61 -86 3 72 36 -57 -71 50 -14 61 93 20 25 -66
  76 -36 42 80 58 18 -30 97 -3 94 -96 -31 26 86 66 55 -89 -77 79 9 -74 96 -34 70 3 -20 84 -52 68 95 -55 7 6 7 73 87 -9
  -50 39 -12 -49 -73 -50 -76 27 -17 51 93 -7 74 -82 26 41 66 27 88 76 42 50 9 -53 26 84 -27 -50 -71 -27 -88 -4 -14 -97 -75 95 64
  -100 88 -65 -21 -64 -6 -15 10 -6 -42 -83 8 -91 -84 65 -27 -86 82 -61 65 84 71 14 73 -11 97 37 -72 54 -10 68 15 -19 70 -33 -37 -72
  -82 -56 -5 69 94 73 66 87 -79 14 -74 -57 45 -44 73 91 0 74 -79 39 -82 -71 5 90 -11 77 69 95 56 63 19 -48 -65 57 -98 14 8
  -58 42 63 50 -71 72 -66 -70 56 81 -75 59 87 -28 67 -86 -82 -71 47 82 6 -49 82 -66 -75 -74 23 -47 20 10 -43 44 90 0 -35 87 2
  -45 -87 53 -89 -43 92 88 -31 -65 93 -65 -23 -51 80 99 5 -31 87 19 -78 19 -17 -13 -2 -89 53 -44 50 -67 65 78 40 94 -60 34 -40 -38
  -92 -72 97 89 79 -58 26 92 -21 93 -44 -20 65 6 73 95 -29 23 -93 6 77 33 20 59 59 1 -3 -73 41 -4 57 9 32 43 10 28 80
  56 -17 40 -32 46 28 -35 30 -14 -39 -4 -55 61 97 19 83 74 -22 -77 -20 22 73 83 98 22 86 -39 -40 73 21 -44 -32 4 64 42 -1 65
  -88 9 -77 -53 92 3 -24 34 -33 15 28 52 99 -43 24 40 21 -63 -13 -61 40 2 -72 41 -80 -1 -8 67 80 73 -83 15 -28 69 92 -79 -25
  -27 -83 -67 -58 -36 -54 -5 -78 3 57 31 28 -59 61 17 -84 48 46 27 -14 35 -99 35 -86 70 23 94 -32 3 -55 -44 -32 3 72 47 -26 -87
  55 34 -26 49 36 -32 -60 -26 -23 52 -61 -65 51 84 25 35 -92 -53 -72 32 -9 -41 67 83 2 -43 55 61 51 -16 -14 89 19 -56 9 -30 -86
  -88 70 -74 -37 0 -56 -65 -37 -14 31 -91 44 -73 -67 -38 5 70 -29 12 -92 -58 72 -86 35 93 -2 48 -62 -99 89 -81 29 0 26 -90 -57 31
  2 -70 49 -70 11 -97 4 67 -65 -19 30 -17 -99 -39 -87 16 -53 60 -14 53 13 -64 77 78 44 34 -83 29 91 70 -4 99 -4 -24 -54 9 -59
  -51 -69 77 -58 86 61 54 -15 -60 8 -42 -49 -63 76 -36 77 -69 -14 -58 -55 -44 -91 32 -54 91 -49 40 30 67 -6 5 -22 -95 52 74 61 88
  -48 -89 44 -30 -77 57 -5 79 59 61 92 83 -73 -83 6 -17 56 22 -51 58 -90 68 5 73 63 11 -55 -30 -83 -95 -82 75 -84 2 16 -96 42
  -66 -75 -77 5 58 -14 20 -66 -17 93 -51 55 43 -47 -42 0 68 80 46 99 -77 -24 75 -78 37 -15 -79 -75 7 26 42 91 -34 -19 87 16 62
  93 -29 60 -73 -54 -12 -39 15 1 -23 32 -27 -70 35 -43 -92 -100 -72 87 -67 62 -34 31 98 38 -91 -45 20 -98 33 85 7 -78 -75 -57 -36 53
  52 17 -83 -70 24 22 -96 -99 -92 -18 -99 -11 59 48 18 -64 -51 -19 -2 -38 -70 -71 46 -59 18 35 -72 -56 46 59 71 34 70 20 8 66 84
  -8 71 -66 -76 72 -80 45 -98 -90 -92 -55 -43 0 -65 95 -34 -10 -35 -26 8 25 -91 13 -39 21 59 -24 -83 86 -22 62 -49 -94 80 62 -16 -42
  89 61 90 56 91 84 -71 -87 -15 15 -18 -15 -94 -51 -96 -83 -80 43 57 -85 45 -87 2 -76 19 -83 32 0 6 -1 -77 51 93 -58 24 29 42
  -18 20 -29 -83 -42 -41 6 25 48 57 -91 91 -30 23 -83 -6 76 26 -98 82 90 -13 -69 69 39 -13 -73 -10 17 -95 64 67 94 44 1 97 14
  -53 -82 -32 -46 -16 82 89 25 -99 -50 28 23 -35 -65 83 74 95 90 -42 39 -55 50 86 58 63 -81 -18 97 -95 -83 72 -79 -78 60 -70 9 85
  -66 -100 86 -65 -87 36 34 -76 74 39 -80 -52 -35 3 -79 3 -91 35 -32 41 -14 33 -40 30 21 -98 19 6 3 -65 -31 94 38 -30 -60 20 -81
  -21 61 -100 -53 -49 45 -93 99 97 -92 -83 50 -65 -17 -83 -3 18 -88 12 13 45 15 72 -26 75 -91 13 3 -50 96 17 -35 -29 52 -96 1 89
  -43 63 95 -53 61 -93 78 -50 74 38 35 98 -41 -84 -99 -25 -99 10 91 -10 -96 82 44 12 -66 93 -84 87 15 33 -8 55 78 31 61 -87 77
  62 -32 4 56 98 -19 -98 19 49 -21 -66 -1 33 5 50 87 -69 -17 -83 35 80 96 56 73 -75 -40 -25 3 69 44 -57 63 -14 64 -54 -8 -86
  42 -85 -44 -41 -99 92 90 77 -12 -96 -24 -55 73 -86 40 -51 -45 -29 -60 39 -68 27 58 -57 -70 -10 -28 14 -73 15 36 -27 68 2 -92 18 4
  -83 82 -64 57 77 -73 -53 -56 -24 -100 -5 -74 -94 82 -57 23 -14 44 88 -18 -19 21 2 38 -35 -44 -37 47 50 7 81 12 67 4 56 -85 -80
  -45 -48 41 -87 -57 -69 86 -99 58 90 72 -58 43 65 21 -99 -59 15 -96 -51 -57 22 -71 -35 31 -30 -79 44 34 -14 53 -55 25 78 -4 -5 80
  -70 -80 10 -61 -45 -95 -27 30 16 20 -61 74 -64 99 4 -62 61 -10 84 -78 43 50 -32 77 -96 -52 74 26 -35 -73 -68 -12 -8 66 -60 53 81
  -38 15 -94 -78 32 3 22 -82 78 -62 -44 79 -96 -52 7 -84 -10 61 -75 16 22 -64 -57 -5 26 -91 -3 -11 7 -46 27 -27 60 -75 92 6 42
  91 47 -100 -29 76 25 -64 16 13 -4 -47 94 64 44 32 5 -52 -85 91 7 -11 -53 -30 50 44 16 -50 45 28 49 76 48 72 44 11 -95 -49
  30 48 90 33 -50 -82 97 -84 69 66 -18 82 -67 80 -15 -41 -8 24 -81 69 -41 92 26 15 -67 -45 -52 -13 -18 -11 89 11 -7 -26 -59 85 11
  -70 16 -66 99 -68 -69 67 40 -53 -97 91 66 58 -78 -91 -84 -59 -10 83 0 25 97 -23 37 65 -6 36 -38 28 -68 71 -78 16 20 64 14 -56
  -13 14 88 83 67 98 -11 -20 -44 -96 -53 42 -77 59 -94 34 26 -90 -60 -73 90 98 -96 11 7 93 -84 -65 -73 84 -72 -5 99 -78 -66 -16 -87
  -88 65 53 71 -65 12 81 19 -84 47 -55 -83 -35 14 35 99 -14 20 67 -79 11 61 8 -88 37 -47 -12 56 -10 65 3 68 -92 -85 -11 56 86
  44
  95 33 -32 -100 -46 11 -73 -24 -50 -18 45 -18 -51 25 99 -86 -3 11 -18 -24 -39 -23 48 62 -100 32 -86 -80 -29 -76 -46 -87 -45 -50 -41 94 41 -91 -29 53 -66 -5 -67 -88
  -23 -23 90 84 -5 -64 39 -60 40 0 69 98 71 -52 54 -33 68 11 98 -57 60 16 -11 77 -92 -53 -98 27 19 -5 17 83 27 -74 -21 61 -85 -12 -85 12 -32 69 48 64
  75 -39 40 76 81 -59 13 49 -28 -59 15 20 -2 43 -52 50 -8 51 -76 82 43 24 92 19 -66 -98 -48 -62 74 -34 -44 17 39 66 -62 -37 -20 26 67 98 22 -81 80 -53
  -79 -78 70 6 -29 55 87 61 20 85 98 86 -44 -22 -40 42 -95 74 46 38 -19 -32 -51 -44 -79 91 78 62 -8 -77 92 33 70 -82 54 -57 -44 -44 82 -99 -83 -36 -31 -13
  14 19 74 23 93 25 90 18 3 -96 -15 -11 49 24 -78 51 27 -30 -55 -77 58 59 -83 -48 71 -37 -2 -51 -61 63 -79 -64 -16 -40 47 -51 17 -86 -19 51 -76 -8 -1 -62
  67 -34 71 17 91 -56 6 -76 -49 -22 60 -90 27 45 -56 23 -64 68 -54 -87 75 -15 15 70 84 -64 97 -44 -50 -85 -28 28 65 92 -13 96 -52 -34 33 97 27 92 -46 80
  -57 68 71 -42 -24 -87 -77 91 25 -62 -60 -74 51 43 67 -24 -86 74 -55 -91 14 83 -91 85 97 73 -37 76 10 83 -6 -66 65 -46 87 65 79 -23 -52 -17 -87 -71 -1 -9
  30 -55 65 26 26 -82 75 46 59 55 44 -25 28 -87 7 -8 -20 -72 50 -46 -69 -22 73 -63 3 8 56 -10 95 -47 24 71 -84 95 -39 43 -34 -84 -65 -4 29 48 -11 -2
  -87 -73 -70 21 85 53 -90 -64 -59 -63 -59 25 -12 -5 64 -62 -89 -61 -44 -11 31 -51 -59 76 -27 -7 -39 -6 -38 -74 52 -17 -3 65 -94 -8 72 -43 -6 -14 -90 -52 -53 -12
  2 24 88 -26 -86 4 99 1 4 -33 -29 11 -1 80 -88 77 -43 -76 74 88 25 71 37 -26 16 18 -73 -97 59 60 33 1 69 73 77 69 -85 58 -78 96 9 -72 -9 89
  -43 -80 17 18 -56 -62 50 -67 35 89 -7 -40 -30 66 46 -39 -69 98 31 -39 4 85 97 22 41 -43 -27 32 61 62 17 -27 85 -39 -72 -68 -10 -98 36 -36 96 58 -28 -45
  -53 -27 -39 -23 -45 -4 -72 -94 -23 -20 -9 -68 1 -94 15 -51 78 -72 -33 6 89 -61 -15 -74 10 -29 82 57 22 -80 20 -5 -75 -81 3 18 63 84 33 -48 49 -96 40 80
  -1 32 -22 -86 46 37 -18 6 -33 92 79 42 -83 24 89 50 -62 -43 -52 -12 -60 13 -70 92 -76 -1 88 48 -46 -92 8 -56 -57 19 60 -73 -47 30 73 -86 70 -69 97 27
  21 -9 -94 65 98 24 -48 9 50 -10 94 36 -50 -21 55 21 33 -72 -29 42 -53 15 -30 -61 98 -68 100 54 75 62 56 -72 80 -48 -11 0 22 -97 -74 64 95 -27 -1 9
  -55 -72 -86 -66 -52 40 -69 -60 -90 -76 13 66 3 67 -73 -13 -79 -4 -60 30 15 40 43 -8 -56 -94 -22 -8 -85 63 17 -17 93 60 24 -29 -59 57 -1 67 81 58 -86 96
  7 59 0 86 65 -78 68 -95 75 95 -82 -66 87 -99 -56 -40 17 53 -42 -9 51 -95 59 45 6 -77 -32 84 -32 23 -41 17 28 -8 76 76 70 -10 -93 -95 -26 53 80 -9
  17 -66 27 -49 20 -25 40 -54 4 70 -18 -61 1 -35 16 -93 8 24 -7 -91 -96 55 -50 -77 -72 -83 78 66 -90 -60 10 -73 76 54 -36 -43 93 66 39 -28 -55 -66 20 78
  -65 82 21 -60 17 12 57 16 -54 58 -91 -36 63 77 -100 -24 23 6 93 6 -79 95 -75 50 25 19 26 94 -57 70 -90 53 99 -22 24 67 -80 -3 5 81 -94 12 -55 -6
  -7 67 1 41 -11 58 23 37 -18 -56 92 87 3 36 36 -2 50 -72 54 18 -41 100 32 100 75 -73 -59 17 -23 -19 -28 -34 22 -97 17 -7 -22 -89 -76 -3 -9 84 -1 -29
  -20 83 -69 60 89 -68 -2 -97 -48 77 5 7 23 -49 91 48 -25 93 14 -86 -74 41 60 -99 89 -65 -21 -75 -62 68 33 -62 -12 -19 -38 -62 90 -86 40 -23 59 89 25 -57
  -52 38 39 -10 -87 10 -100 -69 75 3 -38 -76 -47 -42 -94 -92 89 64 -96 -12 -35 72 95 55 -61 15 -84 27 -22 -36 0 94 23 -83 -63 -32 -84 64 77 -79 9 -1 -85 -90
  63 89 -86 -18 5 -59 -95 -99 -60 88 13 39 25 -47 -34 83 -95 -93 -19 54 10 24 -69 48 -17 -98 -67 51 43 1 0 -7 -88 -41 -43 63 40 -23 8 -71 72 88 -4 29
  2 -58 -14 -30 30 -41 100 -92 -23 -14 85 23 53 60 -82 -37 -53 -19 59 -34 -19 28 -45 24 0 32 90 -7 66 98 -23 -64 -96 8 -64 -77 84 -68 57 95 -29 -9 15 -93
  -16 -94 91 -47 -5 74 -64 86 87 41 -44 34 28 -57 -92 90 71 -13 73 81 82 -81 36 58 17 65 0 -100 7 -4 -37 7 -9 -36 13 27 36 -73 72 -26 -96 16 90 57
  38 -63 -20 83 -22 -79 0 -30 45 -74 -100 -4 58 -23 2 -77 6 -81 75 90 -48 66 -39 -51 -64 66 -58 25 23 -95 95 -98 -10 -26 7 49 -49 -37 -42 -37 79 35 5 17
  -41 -19 -84 -34 60 45 8 -56 -40 -11 46 -54 50 27 48 -49 -57 56 16 100 83 -77 -4 -15 -91 93 7 27 -34 -79 100 -36 28 -62 -13 88 72 -54 28 -88 61 20 -59 -59
  69 -40 31 -56 100 37 -10 41 20 92 -29 -32 -91 -92 66 7 53 34 89 77 -73 -33 -70 99 1 -3 0 87 -19 -73 94 52 -94 -98 42 -69 19 -31 -7 44 51 5 -14 74
  -2 51 -59 42 22 -32 45 11 68 -18 -37 16 41 4 46 55 -57 -9 -41 -66 23 60 -65 -65 13 -41 11 4 45 74 19 71 -33 -24 -64 70 -55 -89 66 -85 -2 -62 49 -100
  -40 16 0 69 -32 -39 49 50 -70 -90 57 47 -32 -73 40 -6 77 73 75 -76 -100 35 90 18 55 -62 14 -71 84 93 -14 -36 87 -34 -82 100 -91 97 -18 6 89 -18 42 -14
  -31 15 4 68 59 -17 78 -88 50 14 31 8 -54 54 81 -88 40 22 87 0 -58 -51 32 -69 55 17 36 37 17 19 -58 -75 42 -7 -18 73 -23 -77 95 4 28 68 12 87
  96 93 79 84 96 -14 31 -22 -42 -77 -77 -19 -68 -35 -92 75 94 74 -66 58 -81 6 -24 -100 -94 -35 22 -7 -7 1 29 -18 -41 94 -82 -100 89 -73 67 -11 13 62 67 57
  -77 -38 -66 28 -81 -79 -5 57 16 -39 -68 8 -29 -49 -5 -35 63 -20 -62 1 3 -71 -24 -35 90 89 57 70 -99 -47 -23 18 21 -13 -53 92 61 -31 89 -57 -6 0 74 -15
  21 42 -77 29 30 -13 -90 -72 -100 -67 -69 -32 34 71 -36 46 -82 68 46 89 -72 -92 -72 44 -32 26 34 8 23 -8 -31 -83 -74 37 -12 -28 93 -79 49 -68 -33 -14 -85 35
  68 33 -64 -78 -31 -23 -5 60 36 27 -27 100 -55 -60 -2 -13 4 34 27 71 58 67 -77 -26 98 31 -82 -51 -9 -8 72 -13 -100 9 92 16 6 -79 -42 -28 58 64 -21 41
  58 -75 -2 -37 -2 -60 -58 -9 25 -13 -93 -73 -67 -55 -84 85 -78 2 14 14 17 -42 -83 -39 39 -40 60 -47 -83 -80 -29 40 -57 -19 -14 19 -39 6 45 95 -30 81 47 82
  -95 61 -93 -63 76 86 -47 20 31 -40 72 -60 69 -58 34 10 -67 -19 4 7 97 -35 -63 -28 14 71 -36 -20 37 -86 49 -67 32 -41 -100 -82 74 72 38 -31 0 71 98 73
  0 73 86 -31 57 -87 -54 -85 51 64 -88 74 -28 91 33 94 -54 48 37 91 -51 -82 -45 98 88 17 89 -30 -33 76 -83 -65 -67 9 92 -29 -76 -46 -77 -50 37 72 57 -9
  -55 56 19 -40 66 55 -48 -99 60 78 20 33 -26 -49 73 39 -8 -64 -81 -79 19 -70 -83 24 -45 11 95 89 49 -36 -62 -14 35 -98 14 -95 42 68 -66 100 59 8 55 -5
  66 -57 48 -64 82 -31 -2 -96 -22 1 -87 -31 11 -30 68 -2 76 94 -63 73 17 6 -62 -97 -64 4 64 -28 -6 -75 26 -39 -2 -93 -89 -76 35 -58 16 -46 -84 96 51 55
  -48 97 73 42 -68 -6 -66 95 -30 -29 4 92 -58 -68 43 -32 -52 -64 97 -65 -6 54 20 -4 -33 29 -40 -92 -40 -73 47 6 31 -55 -42 59 58 52 93 -60 21 -29 -76 -59
  -45 -65 68 -57 74 -93 -98 -96 -96 -65 -35 -46 -80 -17 -61 37 39 64 5 71 64 61 -47 -49 -36 64 -5 -94 -51 -40 -18 84 44 -29 100 -62 30 -91 11 86 -20 -52 -25 9
  22 -53 -58 -64 15 18 -25 44 34 -65 6 60 -32 -17 -22 -99 -8 17 20 -35 5 16 -65 18 -26 10 -66 92 -47 -20 -2 -46 1 -43 -9 23 97 79 31 26 -12 -22 73 -41
  -23 -21 11 -68 -97 -67 -55 -54 95 45 -27 48 -74 -49 51 31 16 31 -87 73 -42 55 -95 -48 39 -46 97 -72 30 -82 43 -20 -98 19 83 -33 30 88 29 79 -95 -34 85 -26
  -60 28 -18 95 -99 -32 72 -71 19 93 60 -15 62 -77 -55 60 8 -49 68 9 24 12 -73 -64 8 5 -95 -21 -2 35 33 37 -14 68 97 81 -85 -15 -42 14 -2 -17 -5 -18
  11
  -19 -68 -69 60 43 -17 89 -37 -52 56 -40
  -100 55 97 -47 -95 69 -12 -3 58 -46 -100
  -78 48 -28 -94 -41 25 -21 -55 59 -100 78
  30 50 94 28 97 -61 -67 13 -89 19 83
  -1 74 -53 -53 85 44 -36 62 -63 -1 -68
  79 95 -34 47 86 20 74 31 2 -75 -48
  50 6 -34 -35 7 15 -47 -13 32 7 23
  -58 73 -69 -6 23 94 34 -35 96 49 77
  60 -21 -21 10 41 98 95 60 50 23 10
  36 -94 -54 43 37 18 -27 -86 16 -71 40
  12 -33 15 37 46 37 72 81 53 49 -7
  37
  -93 59 -50 -25 -17 14 72 -83 -15 -67 94 0 76 -22 58 -89 77 35 18 7 51 80 -91 -52 50 -25 41 83 -76 -96 3 -50 -64 73 45 -83 68
  50 57 63 87 83 46 -77 70 -88 89 -86 -89 66 -70 -27 -76 61 -45 -5 44 -26 18 -44 -41 -94 1 -47 69 21 -26 42 25 34 -93 1 -59 -93
  -97 31 0 32 36 -24 -57 77 94 50 -88 55 55 83 -16 -57 -78 -82 -79 -12 -92 53 -83 63 13 -27 -63 -48 70 98 -72 -30 7 -59 24 -1 75
  -96 -49 65 -37 -29 39 -83 40 61 66 26 2 -60 22 -75 -47 86 -61 90 8 -63 28 -90 58 -79 -7 64 -89 -36 16 -40 13 91 42 -38 65 -31
  -13 61 -2 27 -43 -19 13 -8 31 -24 39 -86 61 99 -91 85 -82 7 -85 -60 92 25 -100 67 13 42 72 100 -16 90 59 -77 53 24 -51 30 -96
  12 87 25 -36 18 -60 72 -82 50 -68 47 43 57 -87 -35 -75 43 93 61 68 -68 -29 -70 -99 -83 -12 87 -32 -48 -98 67 -62 100 -10 -81 72 4
  86 43 -60 51 -88 -26 -47 72 55 49 -81 -3 41 68 -65 -46 45 -35 -48 -43 -55 -88 -76 45 97 -81 8 -33 0 95 71 16 -97 -21 69 78 100
  58 -57 -39 -97 96 -69 -87 -95 -35 -88 -82 34 60 99 92 70 40 19 46 -64 -53 -36 1 52 -62 -19 -56 78 21 20 -41 96 -48 92 62 -68 87
  -52 -100 57 -77 -37 62 14 24 96 22 11 -71 97 -23 -80 -33 30 1 -61 -97 -77 -45 74 -24 100 -25 83 45 61 -76 44 37 -8 -94 -16 99 81
  16 -79 90 -86 55 43 81 -34 -76 98 -85 -51 6 -34 -93 -15 34 14 72 4 -1 94 83 70 72 -36 -39 100 -88 17 80 -21 25 -3 -1 -57 -53
  -16 9 -59 87 2 15 -37 -68 -81 -52 62 3 -7 -72 -40 12 26 -75 -69 -12 -53 -5 -62 10 88 -10 72 46 51 75 -8 -45 75 -51 -47 -46 23
  -22 -92 -95 26 -94 51 -43 90 91 -37 98 21 20 10 0 85 86 87 20 16 78 -18 0 -71 71 93 -19 15 14 -73 -25 -70 99 -22 -36 98 -4
  33 -56 62 79 27 34 70 -33 29 -31 35 22 80 96 71 -25 71 -40 39 19 -49 -40 -68 -94 -99 -62 -87 90 -7 -76 -51 -14 -13 87 -5 51 25
  38 30 -22 -89 -28 0 73 69 18 -81 73 -18 45 -99 77 -86 -49 79 10 -87 74 -22 -61 -27 42 -43 0 6 -85 6 -95 8 75 -80 -20 -56 -19
  -74 0 -91 7 -89 -60 -19 -66 38 -85 -69 100 -42 -47 -47 41 78 19 15 33 -1 66 -70 -79 -24 -86 20 -74 -38 -60 18 -37 41 -96 83 -94 53
  -3 -22 -28 -78 -5 66 26 31 54 87 10 46 50 -100 -45 68 -74 -63 2 82 70 -18 16 -15 -64 -60 -28 -79 1 88 -29 61 -12 70 -29 -55 31
  61 89 17 -43 -26 -50 83 15 29 92 12 -79 85 66 -39 78 -11 -8 -18 -38 89 81 -71 -7 5 56 69 -32 -41 24 27 -12 68 66 37 62 24
  29 -38 -61 -1 60 85 -89 21 -72 80 -86 -70 65 21 -65 69 5 97 -48 -84 -67 65 59 100 -68 80 93 -71 -89 84 2 13 -91 74 74 -12 -57
  28 30 -79 7 83 40 -23 -77 14 -25 53 -3 -88 16 51 43 21 73 36 92 -12 -71 93 8 -93 -100 83 4 -13 -35 -25 8 17 -80 -60 72 0
  74 90 -31 82 -60 0 66 -50 -9 -46 -55 -31 -49 37 96 29 -63 -51 33 -91 63 23 -36 96 -82 -29 3 -2 -50 5 8 -14 -18 31 30 -11 79
  87 -40 26 -22 90 13 44 -97 9 -49 42 -21 85 -95 -9 29 53 10 23 100 -91 71 43 49 38 -41 31 -19 79 44 -52 16 74 50 92 -76 -96
  83 79 56 62 30 58 41 29 -91 -90 18 -99 26 -17 5 80 -83 52 41 -33 73 87 27 30 -28 56 -49 -82 77 8 43 70 11 -29 -1 56 53
  87 23 96 2 65 71 24 10 29 19 44 -53 16 0 -27 -81 -31 98 21 -43 -84 98 28 -6 26 -89 -89 -75 94 43 61 1 -93 51 -64 100 -75
  88 71 -25 -51 -66 -87 10 83 -68 -76 -68 67 49 80 -10 11 22 -57 79 -94 13 85 26 43 43 -62 54 96 92 16 -61 -65 43 63 61 -65 35
  -31 49 -21 -93 69 -78 81 -72 -36 -58 -48 54 -88 -66 22 -34 -95 -26 41 -100 98 40 79 42 9 -82 -66 -33 -16 3 -32 -91 -54 -42 69 -37 51
  77 54 -9 -50 53 -93 0 51 13 8 8 -53 -89 -24 54 1 36 82 -51 2 -13 -55 70 50 54 -18 86 46 93 -100 -78 -9 55 92 -21 -41 21
  -81 68 -5 55 -51 -62 -47 99 33 81 22 32 74 6 20 77 17 -63 -100 80 -91 -79 -61 50 -19 35 99 -87 -53 86 -88 -72 40 60 -85 -55 -80
  44 76 0 -57 -35 -35 26 82 59 7 5 -98 18 4 55 38 -92 59 -8 60 -37 -98 15 -8 -13 -71 61 85 48 -17 -39 68 -34 55 8 -18 76
  -42 61 66 98 59 -3 2 -65 -20 -40 67 -80 49 -1 0 82 -69 58 -83 69 -45 51 90 66 -51 29 11 -4 -63 93 -50 -71 83 -85 15 39 92
  73 -37 -22 -76 -5 -25 13 -82 17 47 -15 49 -94 19 -57 -88 -57 -34 11 62 30 -59 -41 -82 -4 80 91 52 92 82 -81 45 -59 48 -21 86 -28
  -27 83 61 3 -39 0 -9 61 -74 92 -77 63 52 66 -68 -80 96 -3 15 28 32 -10 54 98 10 11 -4 77 -91 -26 69 -53 68 -87 95 3 -76
  67 17 22 -52 -81 74 45 32 -89 42 -31 -30 26 64 -17 76 -35 14 -88 57 -55 92 27 -36 -91 90 55 -37 11 -76 74 -79 -45 -32 59 -66 -52
  -80 48 -27 -94 59 2 28 63 8 56 11 79 65 31 -51 -20 95 45 -39 -4 53 -59 87 18 -24 -13 73 -78 -29 100 -24 -42 -54 -73 -59 56 -84
  92 3 -30 49 62 -1 24 -80 -43 10 56 -39 -23 -72 41 60 57 8 -23 62 45 -56 27 26 5 -88 -100 -22 -22 -68 -47 63 -23 22 61 -97 46
  8 53 -42 -70 -18 89 -24 -66 40 -51 -48 -6 86 87 -39 66 38 47 10 -75 -18 1 74 -66 46 83 -57 97 -21 91 -47 40 -7 -30 -36 -79 34
  28 -12 88 77 18 -24 41 63 -38 20 -61 99 -78 28 -55 1 -36 9 -72 -59 -85 -70 61 -23 -74 43 -2 58 42 -35 81 11 -16 -6 72 43 14
  48 -77 -40 46 -17 -57 -28 -93 -61 32 57 -59 -1 28 53 -89 50 -37 -13 5 -30 -71 -26 -20 -3 -91 66 -89 -12 -43 -93 -31 28 31 -16 -38 -30
  13
  -56 23 -74 -65 -6 55 25 82 -97 53 73 35 -69
  -84 -67 50 -29 63 80 -35 41 91 -94 -88 50 61
  -26 -69 100 -41 77 21 30 8 44 -62 100 -16 91
  -49 43 96 -71 29 49 -2 -95 -64 -73 -67 -82 68
  -48 -72 -54 11 96 -99 70 -69 -65 -10 -60 15 79
  83 -78 39 -67 -96 98 51 13 -92 77 -68 98 -32
  -84 90 -97 54 54 65 70 -8 100 25 7 -62 78
  -24 73 65 -71 17 25 -6 -97 -67 97 -32 100 75
  40 -23 -31 -59 71 -59 -78 -40 12 -14 83 40 88
  7 62 -60 51 -86 -97 18 -33 -40 -18 -46 -58 -72
  40 52 -16 -81 -7 -80 -89 7 -75 -85 -2 -51 -37
  -17 -55 68 68 22 45 28 8 77 -4 -81 76 -18
  23 30 98 88 70 -47 41 53 -37 71 -54 -41 64
  40
  5 88 76 11 -20 -90 61 -86 -19 -17 24 41 -18 43 -18 -11 -17 38 87 61 41 11 -95 -32 51 -85 -79 -9 46 5 83 53 47 58 6 73 -69 -81 -13 -77
  94 -38 18 1 66 95 -55 13 4 -1 -22 90 -90 -20 49 -100 -56 82 51 -4 22 -30 80 45 -80 27 -86 -25 -19 -10 -74 78 80 -70 -74 -12 5 73 -51 1
  29 32 43 -88 35 -31 -75 -4 -33 -17 13 69 -4 36 -24 -18 98 66 -40 -3 -17 49 -75 12 -26 46 24 92 -21 -50 31 97 51 35 -82 31 38 57 -66 -86
  30 98 -12 -15 -83 11 65 7 -36 38 47 83 -82 -64 74 -4 -14 -23 -23 -26 -69 85 12 82 1 32 55 100 -19 49 -46 62 55 18 -90 50 -15 24 59 -41
  26 -8 -53 50 37 30 -85 -75 -43 -84 71 56 -100 -79 -53 -85 -25 92 33 -83 -6 86 71 63 86 -78 45 -74 -46 35 71 43 -79 5 -42 48 -33 72 -92 49
  80 -66 25 0 -91 36 22 -22 81 -79 48 -37 58 50 -42 93 -24 44 31 88 46 83 69 1 99 -38 -38 -94 -49 -44 -42 44 -62 -83 98 80 59 -10 33 -43
  -57 -10 21 56 -14 26 70 89 23 56 -39 64 -30 -59 86 -93 -49 70 -40 -40 -58 -76 -2 -91 -34 -79 14 -38 16 73 64 -76 34 -83 -37 -94 54 55 33 -14
  58 73 -1 -82 -73 -51 -51 15 4 -92 -18 68 -88 -61 -34 -19 34 96 35 85 -63 78 -94 -65 23 -4 -75 -46 -61 14 -48 -52 -58 49 -90 34 0 32 -70 58
  86 -67 68 88 19 -90 34 -82 55 -17 30 -63 62 -92 -90 57 -10 -1 -2 -39 90 21 -35 48 0 0 83 61 56 -75 68 -20 -21 -22 44 -78 55 -23 68 12
  68 65 7 -27 -44 7 -100 -21 49 -77 36 -92 -53 13 84 55 3 68 10 -73 29 98 -6 82 -95 13 79 54 18 -18 -58 54 -24 -37 -15 21 -89 -71 70 50
  -44 -28 -34 20 49 -21 -9 0 -28 100 13 86 38 62 -42 38 41 -74 -14 -94 64 1 -55 72 5 -25 24 52 0 70 25 -94 -6 -6 -27 15 -47 30 -85 -85
  73 -74 53 25 -4 61 -1 -61 -54 -60 67 -37 -57 48 35 -63 75 37 27 47 -23 -27 95 -64 89 -95 -64 -34 31 -95 47 -39 -60 -49 5 52 -69 -86 100 -77
  39 75 -35 56 24 98 -41 59 45 -20 69 -11 84 33 -78 -3 13 -52 19 -80 91 81 79 -99 12 -40 -23 16 80 55 92 -6 2 52 65 98 -74 -19 83 -76
  68 -7 -100 29 39 -70 -75 34 -33 -31 -49 -85 -72 40 87 14 65 -11 10 -76 92 45 20 76 63 16 0 -100 -4 -92 -89 -11 59 -49 -97 -85 2 -86 41 41
  -33 -82 -91 -71 -53 -17 -33 26 85 27 -33 34 6 -24 -47 -51 55 -80 45 72 -79 -5 84 70 74 -14 -74 7 0 94 29 -59 -8 61 21 17 -87 77 -21 71
  8 -33 66 95 -38 -79 -64 83 42 -91 -41 62 98 30 51 -45 53 -74 -17 -51 55 54 67 -56 -79 -38 -21 -80 -72 -2 -77 -14 24 81 -56 -29 60 -62 19 -69
  -98 -16 -39 -2 -71 -100 -17 9 68 -48 20 -1 26 40 13 -75 -81 95 -52 97 33 -37 -42 57 2 -33 14 69 -30 17 83 -20 49 50 -44 -91 8 60 -5 -25
  54 97 -25 -75 -40 99 -51 52 65 67 -14 18 -16 4 -60 -29 54 49 23 -34 48 -17 83 -31 3 89 -21 -72 -50 25 -72 91 -12 4 95 -30 -3 7 50 67
  2 -37 28 93 51 87 -5 47 48 52 23 -52 -96 79 64 -65 67 -21 76 -4 64 14 -34 19 -46 -92 -18 61 68 92 -51 -29 23 -78 30 -58 40 29 -67 89
  51 -13 -89 -15 46 20 -29 -47 66 18 -40 56 81 86 65 92 -20 -50 -11 99 39 53 -34 -53 92 -28 13 -43 34 -7 -69 -80 -36 -65 28 -2 -47 67 -22 14
  57 77 -93 97 -13 -92 -34 -38 -67 15 -98 27 40 -58 -81 7 47 -74 -69 31 5 -30 -60 -42 -2 21 41 -10 8 75 -39 26 31 91 1 -48 -77 78 79 -28
  -9 47 64 -98 23 27 20 13 51 -84 24 91 41 -2 20 -67 -46 79 69 13 81 87 92 -84 36 -60 30 -93 85 57 57 33 -69 44 -87 28 97 -33 -80 30
  -16 7 -6 -84 26 27 -30 -18 -4 35 -19 23 77 -3 71 -4 -57 -100 44 53 90 -20 -6 -52 -33 33 -50 -34 10 -15 -3 34 -99 56 -82 -79 -54 92 -70 2
  -96 88 -90 -4 -91 81 -5 20 -13 12 50 66 56 -97 -32 60 67 -5 0 -22 -62 52 83 3 81 -91 72 67 46 51 -29 38 91 -18 86 49 9 -47 -4 -54
  31 48 -100 -29 -78 -55 -91 35 -70 39 -60 69 -20 -95 31 -76 92 97 -3 -1 -5 20 82 9 -8 6 -68 -70 -22 79 11 -81 43 -59 69 -94 48 1 69 47
  -58 44 -60 -80 -10 0 78 -90 91 -67 74 99 -40 17 -9 -85 -84 -60 -75 92 -30 38 5 -95 41 20 53 1 -51 -1 -84 60 -47 10 -92 -4 27 -95 35 -28
  48 -56 33 -94 -76 -42 12 -26 -88 12 37 32 24 -63 -48 0 71 -30 -46 -19 -84 -47 -30 88 -7 -29 49 8 -20 -99 94 98 -88 34 -16 -20 -48 27 72 -27
  -47 -24 -50 -68 -2 -4 31 -60 95 84 81 -42 -37 72 50 54 88 92 9 6 -92 -6 -45 -39 94 49 93 1 27 36 -3 40 0 -94 57 53 -44 -3 -59 27
  -98 92 34 51 64 -37 44 -24 -75 -53 84 -12 98 49 92 -40 18 45 -56 -79 15 -53 -25 36 -60 -98 -60 -37 -58 -80 -95 -4 17 -98 77 -25 -24 -17 -87 -15
  -74 91 -21 -58 -46 -95 90 -85 13 80 91 48 15 30 -85 14 57 59 65 -23 -52 -83 -82 -82 15 -16 98 86 -97 81 -95 -72 32 96 79 -39 1 5 54 9
  -80 40 56 22 8 -32 29 -86 0 -90 -31 -42 15 81 -66 4 -82 89 -37 89 79 80 -23 1 -79 35 86 75 -57 -2 -11 0 -85 -62 -65 32 36 -83 8 -15
  -41 29 60 -59 91 71 35 93 25 6 71 65 -82 100 64 9 -31 29 40 -39 -16 -99 47 -2 -11 -28 79 22 39 82 1 6 -61 -89 -91 -98 -3 -90 -18 -88
  99 11 -7 -2 -20 -15 -7 -20 58 1 69 -87 -26 54 100 40 -56 40 50 -8 58 -24 79 -32 51 -16 -98 -23 44 33 17 -6 57 -1 -20 -76 66 -42 76 46
  73 79 -64 25 11 -16 -64 -67 0 -27 44 98 -69 20 79 3 -28 87 51 -32 1 -57 -3 -19 -58 57 14 -43 59 -60 -96 -88 -11 13 -17 91 -60 16 -2 -32
  13 94 75 43 66 -36 -99 -16 96 4 75 64 74 63 -48 2 -83 55 99 23 67 58 15 41 -71 -90 72 -12 -100 87 2 7 -17 -76 -27 -46 58 -25 -45 51
  -77 -93 26 25 -46 -38 -100 66 -40 -98 40 27 81 3 84 -73 -27 40 36 78 8 62 -93 23 35 -66 64 -5 10 1 -29 -19 -4 -75 90 54 -100 5 77 -91
  -49 -53 -15 -22 32 -19 -97 49 -64 -74 -7 18 -76 65 51 30 -78 11 6 -52 56 -66 42 52 -4 93 -85 85 -66 -45 36 -16 -90 40 27 0 28 -34 46 9
  -77 -28 -78 55 -27 -26 74 -9 3 92 6 12 90 -38 32 -52 14 -3 -24 -33 90 46 -35 93 71 -67 41 -11 26 98 -28 100 -61 32 26 1 91 -79 -70 -96
  -87 16 -8 -90 -42 58 2 44 26 -14 7 -69 97 -56 -17 -38 -80 64 14 88 -40 59 -36 -39 11 -14 35 83 29 -29 -55 82 55 -55 -99 92 55 13 87 18
  -72 -83 14 -71 -2 21 100 -58 14 -90 22 84 -30 100 -82 -81 -16 -25 27 6 62 52 -98 -48 -56 91 -50 -87 -2 -63 69 -2 -5 -83 90 94 83 -11 -89 58
  36
  14 -11 6 -22 21 26 -75 -36 60 25 -28 98 19 -95 68 5 -24 -1 41 88 62 59 92 72 61 99 -72 -95 -6 -1 25 21 90 45 11 92
  -12 77 -77 -53 -78 -93 -14 38 8 60 -12 -49 69 31 -93 -53 -39 -40 10 20 -45 -69 -32 45 -12 -7 51 -24 -83 -65 45 -12 -80 66 -12 76
  -65 48 -84 -70 29 52 66 31 -98 -90 -46 -93 -88 14 -44 -55 0 37 27 -45 -16 34 -5 63 26 11 87 -31 27 -39 1 -78 62 86 89 -43
  94 86 41 -68 32 -73 -81 -59 -81 -11 -24 -85 70 -74 67 96 94 -92 -95 -35 -36 -11 9 57 68 72 -89 44 -59 49 35 85 57 -96 -34 10
  -36 -19 -24 -35 9 -50 -62 -23 78 -78 -49 -40 -72 -90 99 8 -87 -46 -3 -35 19 -44 45 -33 71 -34 6 58 75 -49 -12 40 52 42 -99 -67
  -95 31 -43 95 75 66 -68 24 -36 48 64 13 -39 69 -65 20 12 65 15 -2 19 3 -92 -62 33 42 -63 10 76 -71 48 -67 -75 -82 -90 -11
  18 -62 -75 -69 65 37 -65 61 -59 48 54 -67 -78 -84 -65 42 -42 58 59 -24 37 -16 40 75 -40 5 -69 -89 53 -46 100 -66 -23 -58 15 71
  75 -87 -96 14 -50 -28 24 31 20 60 -31 -28 -48 -2 34 48 -26 90 -95 56 -56 -63 -66 22 -37 -73 6 90 52 49 -65 -27 97 -12 53 -1
  85 -20 91 69 90 -28 -7 -48 -76 -11 60 -30 88 -13 -43 81 11 9 -8 62 -19 25 -40 -19 35 54 -35 -17 -59 28 -78 -61 41 57 -15 -79
  -41 94 8 28 -9 4 -32 -99 84 25 67 -17 23 -22 -59 -38 -70 -46 10 -87 21 96 -10 -78 -86 22 55 -59 79 -82 -47 2 -85 -26 88 -47
  36 96 -2 7 -41 -40 0 40 46 83 75 42 -100 -86 47 28 41 -97 -62 -30 99 32 1 43 -26 72 10 -92 -14 -62 -76 10 80 25 -76 11
  -58 -4 -81 4 73 40 -22 58 76 64 77 0 -13 64 -13 -62 -50 29 13 -71 -77 35 8 -68 -46 -68 -37 -10 25 -38 82 -9 -65 -29 38 -31
  -76 -12 58 -34 -77 -58 1 -63 76 -99 66 -55 -78 75 -15 63 -71 76 87 99 -44 9 57 -4 -38 56 42 -100 94 -69 -79 -100 -39 -78 -51 55
  98 -5 1 -19 45 -75 -18 -74 -47 86 39 -41 -26 -70 60 3 54 -11 -52 -93 -72 -50 73 -33 -98 -12 -70 47 -72 -72 -6 88 17 -13 -29 98
  38 -22 70 -98 39 71 -62 -38 0 -64 51 -66 16 35 51 11 13 32 -54 -16 -4 34 71 99 -48 76 -13 100 -87 -40 100 -24 16 -62 18 -95
  31 22 67 71 83 46 -88 57 11 -43 -80 90 -56 -31 62 64 -20 93 -72 68 -8 -48 -91 68 -33 -80 -10 -40 -19 -6 63 -5 21 36 26 -80
  84 29 99 -43 74 -10 -23 15 -88 89 -92 66 -23 -39 72 83 -46 -63 -74 43 -26 97 -36 -58 0 6 39 -37 -6 10 -61 -66 -70 -17 32 -91
  46 40 65 -72 42 23 49 76 2 100 44 35 -93 22 -45 -15 -32 39 -18 28 21 -7 43 -25 34 40 22 57 -95 71 -58 30 40 -52 -45 -51
  63 -3 6 84 -52 -84 100 54 -18 -99 77 -65 29 74 63 74 48 99 -3 26 -72 -95 15 97 -5 42 22 64 90 59 27 11 -7 27 23 32
  28 -32 7 9 57 94 -90 63 -27 -65 -52 -62 -17 -36 -8 35 -26 79 -29 45 71 -63 95 -5 -80 41 11 -57 24 -69 -93 0 -70 18 -32 16
  0 -29 -72 82 71 -49 58 77 -31 -80 -81 -76 25 15 56 -93 44 -17 22 65 -89 -40 -53 95 94 -40 87 -58 8 -36 3 87 16 61 3 -97
  -6 3 -86 -75 4 -52 -63 69 82 -1 66 -65 58 -52 -17 -18 16 -48 18 -80 -4 -13 74 4 53 5 25 -32 -62 44 -98 -69 84 -48 39 24
  91 -43 -51 85 -85 54 -26 -93 69 -33 99 12 84 83 19 99 -42 -40 -20 29 -81 81 35 -27 -42 2 94 88 40 -67 9 35 -39 -11 -65 30
  90 86 15 62 5 30 -79 -42 -21 -44 -6 48 19 70 66 62 -42 12 93 82 38 28 96 -67 -11 -13 21 -95 53 57 -97 -5 -32 97 -58 -54
  -55 44 -85 -33 54 -46 40 -48 -72 -77 -23 73 -99 -11 -12 -85 79 85 -39 -26 -97 -34 79 95 -53 -85 51 -63 93 -73 -37 -4 18 80 39 16
  -43 -3 65 38 -34 60 12 0 -96 -41 -63 49 67 71 66 -73 -35 30 39 -85 -57 91 -66 39 97 -61 -59 72 -36 98 61 -76 12 -29 41 -57
  -90 33 -3 -50 85 24 -18 -35 4 -21 -68 -95 69 -64 2 -7 -67 -80 -44 -2 -72 -38 -89 -9 71 -92 -94 51 -75 38 -34 34 17 -3 -76 56
  98 -70 33 -12 -42 -76 -21 -64 7 -72 -12 -75 18 56 -15 75 -73 31 -90 -42 12 33 -77 95 98 91 71 -4 75 49 -39 35 -34 49 76 -21
  41 54 -17 -67 81 -57 55 -5 89 52 -44 4 -53 34 -10 48 -42 -1 -50 7 -93 -13 -92 -43 -5 -73 48 94 97 -61 49 -57 10 16 -27 89
  -20 -66 53 91 71 74 6 86 61 41 -21 67 23 -91 5 35 13 -35 76 91 89 -98 64 29 -61 0 0 47 49 -39 16 -45 -41 62 5 96
  49 87 -41 70 17 -50 -70 7 -34 72 -87 -46 63 10 -59 60 64 -53 27 72 -59 -28 -18 47 -15 69 -1 -96 -21 -64 9 -54 -35 9 -96 -39
  69 -49 35 72 -82 85 -54 -80 -84 -55 -100 31 -48 -63 -53 30 -34 -42 -7 52 -87 -38 -48 14 26 23 78 -26 26 -1 -22 68 8 -24 -89 71
  45 -81 92 91 -98 76 0 -32 89 73 -97 -100 15 -88 -66 -11 -33 -71 19 -75 -41 -23 -85 1 -55 50 -13 90 -39 98 -67 82 67 -91 -13 69
  82 28 13 73 -2 -53 -4 -9 51 -13 48 84 -13 67 4 47 59 52 -71 -74 -79 21 0 -58 70 34 100 -65 -57 5 99 -14 -93 97 56 69
  -62 -50 -86 79 -45 -6 97 57 69 81 -80 24 93 68 -22 -49 92 -11 72 65 35 27 -8 50 78 43 -58 62 -20 -65 -98 -93 44 -31 26 100
  -33 58 -43 84 -38 -10 27 -12 -33 56 23 85 86 50 10 39 -41 17 -37 37 95 37 85 34 -93 13 5 -84 -45 68 48 -66 70 -5 50 -48
  37
  -85 73 32 -93 69 -94 -58 -77 -17 4 30 -60 -64 29 80 -60 -37 -64 -88 -23 30 -54 -32 44 -96 -40 6 -5 31 -42 -6 41 0 45 93 -77 -17
  76 -28 66 33 -15 71 -77 -88 45 -87 -70 57 -75 -16 4 48 -49 32 -66 -86 -38 68 -91 65 14 21 -38 -32 27 29 13 -78 19 -43 8 32 -51
  -93 20 -77 41 51 -75 -57 -63 33 30 -72 53 -67 43 -39 64 -1 -21 -84 8 -74 -50 -51 49 -22 93 61 -7 39 -92 -78 -42 -71 -90 -92 -21 12
  -27 -51 -12 -21 -66 84 41 -56 -67 19 -79 38 -10 31 26 2 6 97 25 56 32 -97 -28 72 -52 -36 -81 -98 36 21 37 83 43 -61 28 58 89
  -33 -73 -43 -61 -20 87 31 -78 -17 9 -57 -10 19 100 65 98 70 -34 60 59 36 -29 -100 19 54 -49 12 94 65 42 47 -60 76 96 -55 -48 -31
  58 -16 81 71 46 -55 47 98 -82 -95 27 67 37 -9 -46 61 3 -80 79 -46 -65 -96 53 0 -70 41 -97 -51 96 -51 33 -10 -20 19 -72 -89 31
  -15 43 -17 77 41 99 73 85 68 68 -52 67 -53 -1 41 -92 -16 38 -12 -91 -19 -11 15 49 -79 -59 -37 68 -30 -32 -68 60 24 51 -10 22 63
  -54 95 93 -52 -35 -43 -79 38 -76 -67 56 -65 25 -81 -71 -46 53 -94 11 -28 -66 -15 -42 -88 -59 86 77 54 92 15 -9 19 34 -5 90 -59 37
  -66 27 63 40 -32 32 -86 86 -18 28 55 -82 75 -26 92 -6 -74 44 -51 -18 -67 -35 -39 19 -14 26 -76 96 44 -49 -50 26 21 -27 -19 -22 95
  71 -10 23 -3 61 57 -96 78 -69 -66 -17 97 26 -55 -35 -37 49 62 39 87 -9 -21 -77 -15 -59 73 0 -53 -51 6 -23 24 -92 -76 -16 -62 -38
  63 -48 92 -57 -14 -33 16 -7 -2 -67 0 -78 -20 -70 51 -30 -88 23 -16 9 -4 -97 -59 43 100 -53 -66 -41 56 -100 85 -87 -40 -85 -56 20 69
  -47 -20 20 -99 52 69 -16 -70 -97 -78 -60 25 41 70 -74 43 -98 42 82 -56 -71 -25 -81 -34 83 -59 97 52 98 64 93 -57 2 74 72 -83 87
  -27 -35 -77 39 -59 -86 38 31 19 41 -79 7 -59 14 -19 81 -100 -73 -33 -79 80 -1 80 -52 21 7 34 18 25 100 65 56 63 -7 6 -20 -15
  -71 20 -60 82 -8 47 -75 -92 48 87 20 -31 -78 79 91 -86 21 83 14 -80 12 14 -30 -93 28 47 27 8 -49 2 -13 -100 -60 48 -79 -62 20
  -43 -14 61 13 90 19 -11 16 -73 -68 98 86 -34 39 -20 4 -43 -98 94 78 84 12 97 -75 -92 73 69 66 -89 30 -98 -4 -87 76 -45 96 -83
  -90 -2 -14 39 14 46 76 18 76 7 21 -14 39 -16 20 -75 45 6 3 -12 -86 30 -25 0 29 47 33 -80 -87 -39 -27 83 56 -98 -33 -9 34
  13 -54 25 -53 100 -34 -23 -40 94 -41 -5 -63 89 -79 -82 3 3 74 39 0 -78 -83 -21 -96 23 22 -66 -98 47 18 -20 -89 -44 -17 -20 54 85
  -31 93 18 28 -9 92 -15 -48 -67 -88 57 50 81 -25 0 -4 14 -23 78 73 78 -60 68 -59 -42 -22 -43 5 -74 -92 -39 71 -24 -85 44 -20 19
  47 -54 -88 -17 26 -13 16 95 -94 1 -52 91 -59 26 -22 -25 100 -40 40 -29 -49 -65 -62 5 -59 87 99 13 -78 70 18 -34 -40 -70 -63 12 74
  -43 -69 91 -22 3 20 -10 90 -96 7 91 35 59 -92 8 -81 -100 -67 -42 -100 75 96 -15 64 58 -39 -84 -40 -37 47 62 64 9 85 85 29 36
  -43 -75 62 -78 46 -7 37 50 -56 43 -6 -82 -36 6 58 56 60 -7 96 54 -80 60 -38 66 -89 -46 27 17 -94 94 32 -17 -12 -45 43 -14 93
  -4 -51 -90 -44 -66 -63 100 -72 73 -75 -27 47 -94 -37 44 -49 59 50 71 84 98 85 34 57 93 -28 85 58 31 -52 -90 -90 32 -28 67 38 90
  61 -45 96 -82 -22 66 -76 40 -4 61 -9 67 -96 -82 -97 89 61 74 -36 47 -53 -71 -41 -23 -73 6 43 19 -72 5 38 -24 94 -22 -19 -20 13
  -1 -35 -66 -40 22 77 55 -8 -15 -19 11 37 75 -34 96 -52 68 -53 -61 72 8 57 -29 89 77 -49 -19 54 -76 -55 1 -100 -60 -2 10 -1 54
  -14 -89 59 -44 87 27 -23 -95 5 -16 -65 22 -28 -73 -84 54 -42 68 -41 8 -6 -100 70 -39 -91 79 98 55 -65 89 -20 13 17 -97 -24 17 -72
  -93 -78 82 53 55 -93 43 -3 5 -39 18 -65 47 51 -86 -81 63 8 58 -36 79 55 86 85 13 42 -12 79 62 23 -52 -91 27 -92 -93 -63 22
  58 -41 65 99 -53 45 2 27 -19 28 27 -41 5 79 71 -18 -75 -37 81 -78 78 -97 96 -5 -70 91 -21 -13 31 -28 -26 96 72 73 100 17 -39
  -24 -71 16 -62 -69 71 -77 -73 69 16 66 29 6 88 -38 71 28 58 -47 -16 -69 -29 -54 -82 67 19 87 36 8 -83 84 -8 60 -21 52 -88 91
  99 -52 -100 44 -84 -99 -90 -76 -19 -92 36 26 24 61 31 -61 -27 -41 64 77 -82 99 -48 -9 -66 61 84 -92 -31 52 35 23 58 88 16 0 -72
  -35 5 19 -77 -40 33 0 16 59 -30 46 80 41 65 -59 39 89 -3 -82 53 -6 -86 -84 -24 -18 -23 75 -99 64 56 -98 -16 -4 59 -100 -40 -31
  -44 -93 -55 -55 76 -47 -77 -35 0 -93 -85 -2 -50 88 6 48 31 85 51 98 34 -32 -88 9 66 -37 -66 -59 40 -37 -64 64 -25 14 20 -35 88
  98 0 96 -76 -82 -71 89 86 -23 -10 11 -68 -77 69 7 45 98 45 -43 -24 -94 -63 -72 -73 -65 48 84 -33 -69 -38 -57 13 -60 -47 -10 59 32
  51 37 64 -73 -9 93 84 -9 3 37 53 -7 -99 3 -88 11 4 95 -82 -46 91 -99 66 -27 40 -84 -94 25 75 -81 29 -32 -6 -67 -27 -45 -17
  23 84 -50 -47 49 91 64 34 -93 36 62 17 -64 -7 27 85 -5 33 58 54 52 -12 75 -59 -41 58 71 -64 -86 -8 -94 96 -28 53 -74 -59 84
  6 16 -58 -59 93 -56 96 25 87 30 -16 76 9 -74 -6 72 -48 76 -10 20 -30 57 84 63 -66 84 -16 -49 -6 -60 -46 -57 51 99 33 97 61
  -22 1 12 9 -82 20 -16 19 4 5 -25 59 84 75 -89 -65 78 61 66 85 -61 -9 -63 -52 61 -94 -80 -42 -78 8 -18 8 -5 -52 71 -50 -74
  -6 54 70 -82 67 15 90 92 -91 2 73 33 10 27 -67 86 -4 -31 20 3 5 -61 -43 -24 29 -98 0 -92 66 3 87 -5 60 64 -81 -99 18

this is my output:

• 10073
  2682
  3632
  2626
  1549
  4356
  1277
  5474
  3815
  2789

[angga888]

My AC program outputs:

Code: Select all

10126
2682
3632
2626
1549
4379
1277
5474
3887
2789

Good luck

[Moha]

I did a very nasty bug in this problem, now I got Accepted with O(n^4). special thanks to angga888.

[emotional blind]

i solved this problem using O(n^4) DP algorithm
and get TLE
but the people in forum says that it should be get accepted

where is my algorithm should be checked
my code says my algorithm and it is very easy to read..
C++

Code: Select all

ACCEPTED
}

plz chek a bit
thanks in advance

[emotional blind]

no one can help a bit to speed up my code?