10827 - Maximum sum on a torus

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

more test data ?

Post by Sedefcho » Sat Jul 16, 2005 4:53 pm

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!

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

A variation of the "Maximum Contiguous Subarray Problem

Post by Sedefcho » Sat Jul 16, 2005 7:06 pm

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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Re: A variation of the "Maximum Contiguous Subarray Pro

Post by misof » Sat Jul 16, 2005 9:26 pm

Sedefcho wrote: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)

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sun Jul 17, 2005 4:29 pm

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
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Post by Chok » Sat Aug 13, 2005 7:43 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sat Aug 13, 2005 11:12 pm

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
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

WA again

Post by Moha » Sat Aug 13, 2005 11:38 pm

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??

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Aug 14, 2005 10:10 am

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

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

About negative output

Post by Moha » Sun Aug 14, 2005 10:30 am

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
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Post by Chok » Sun Aug 14, 2005 7:59 pm

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

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Please test these test case with a accepted code

Post by Moha » Mon Aug 15, 2005 1:19 pm

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

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Mon Aug 15, 2005 2:48 pm

My AC program outputs:

Code: Select all

10126
2682
3632
2626
1549
4379
1277
5474
3887
2789
Good luck :D

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

At last I Got Accepted !!

Post by Moha » Tue Aug 16, 2005 8:34 am

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

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Wed Jan 04, 2006 7:59 am

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
Last edited by emotional blind on Tue Apr 25, 2006 7:37 pm, edited 1 time in total.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Fri Jan 06, 2006 8:04 am

no one can help a bit to speed up my code?
Last edited by emotional blind on Tue Apr 25, 2006 7:42 pm, edited 1 time in total.

Post Reply

Return to “Volume 108 (10800-10899)”