#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int altura_maxima;
int num_caixas;
int max_dimensao;
int indice_i;
int indice_j;
typedef struct caixa
{
int altura, largura, profundidade, valor, rotacao, numero;
} Caixa;
int max (int x, int y)
{
return (x > y)? x : y;
}
Caixa* leCaixas(char *arquivo)
{
if (!arquivo)
{
fprintf (stderr, "Erro: argumento invalido.\n");
exit(EXIT_FAILURE);
}
FILE *in = fopen(arquivo, "r");
if(!in)
{
fprintf(stderr,"Erro: nao foi possivel abrir o arquivo de entrada.\n");
exit(EXIT_FAILURE);
}
int i=0;
int j=0;
int k=0;
int l=0;
int valor;
Caixa *caixas;
max_dimensao=0;
if((fscanf(in, "%d", &valor))!=EOF )
{
num_caixas=valor;
i++;
}
caixas = malloc(sizeof(Caixa)*2*num_caixas);
while( (fscanf(in, "%d", &valor))!=EOF )
{
if(i==1)
altura_maxima = valor;
if(i>=2 && i<num_caixas+2)
{
caixas[j].valor = valor;
j++;
}
if(i>=num_caixas+2)
{
if(k%3==0)
{
max_dimensao = max(max_dimensao, valor);
caixas[l].largura = valor;
}
if(k%3==1)
{
max_dimensao = max(max_dimensao, valor);
caixas[l].altura = valor;
}
if(k%3==2)
{
max_dimensao = max(max_dimensao, valor);
caixas[l].profundidade = valor;
}
caixas[l].rotacao = 1;
caixas[l].numero = l+1;
k++;
if(k%3==0)
l++;
}
i++;
}
fclose(in);
return caixas;
}
void geraRotacao(int num_caixas, Caixa *caixas)
{
int index=num_caixas;
for (int i = 0; i < num_caixas; i++)
{
caixas[index].altura = caixas[i].largura;
caixas[index].profundidade = caixas[i].profundidade;
caixas[index].largura = caixas[i].altura;
caixas[index].valor = caixas[i].valor;
caixas[index].rotacao = 2;
caixas[index].numero = caixas[i].numero;
index++;
}
}
void gravaTabela(int **soma, char* arquivo)
{
if (!arquivo)
{
fprintf (stderr, "Erro: argumento invalido.\n");
exit(EXIT_FAILURE);
}
FILE *tabela = fopen(arquivo, "a+");
if(!tabela)
{
fprintf(stderr,"Erro: nao foi possivel abrir o arquivo de entrada.\n");
exit(EXIT_FAILURE);
}
int linha = num_caixas*2+2;
int coluna = altura_maxima+1;
for(int j=0; j<coluna; j++)
fprintf(tabela, "%d,", j);
fprintf(tabela,"\n");
for(int i=0; i<linha; i++)
{
for(int j=0; j<coluna; j++)
fprintf(tabela, "%d,", soma[i][j]);
fprintf(tabela,"\n");
}
fclose(tabela);
return;
}
void imprimeCaixas(Caixa *caixas)
{
printf("\n\n%s\t%10s\t%10s\t%10s\t%10s\t%10s\t%10s\t\n\n", "Indice", "Largura", "Altura", "Profundidade", "Valor", "Rotacao", "Numero");
for(int i=0; i<num_caixas; i++)
{
printf("i==%d\t%10d\t%10d\t%10d\t%10d\t%10d\t%10d\t", i, caixas[i].largura, caixas[i].altura, caixas[i].profundidade, caixas[i].valor, caixas[i].rotacao, caixas[i].numero );
printf("\n");
}
printf("\n");
}
int **preencheMatriz(int valor)
{
int linha = num_caixas*2+2;
int coluna = altura_maxima+1;
int **m = malloc(linha * sizeof(int *));
for (int i=0; i<linha; i++)
m[i] = malloc(coluna * sizeof(int));
for(int i=0; i<linha; i++)
for(int j=0; j<coluna; j++)
m[i][j]=valor;
return m;
}
void freeMatriz(int ** matriz)
{
int linha = num_caixas*2+2;
for (int i=0; i<linha; i++)
free(matriz[i]);
free(matriz);
}
int compare (const void *a, const void * b)
{
return ( (*(Caixa *)b).profundidade * (*(Caixa *)b).largura ) -
( (*(Caixa *)a).profundidade * (*(Caixa *)a).largura );
}
char* concatenar(const char *s1, const char *s2)
{
char *result = malloc(strlen(s1)+strlen(s2)+1);
strcpy(result, s1);
strcat(result, s2);
return result;
}
char *remover(char* mystr)
{
char *retstr;
char *lastdot;
if (mystr == NULL)
return NULL;
if ((retstr = malloc (strlen (mystr) + 1)) == NULL)
return NULL;
strcpy (retstr, mystr);
lastdot = strrchr (retstr, '.');
if (lastdot != NULL)
*lastdot = '\0';
return retstr;
}
void escreveCaixas(char* arquivo, Caixa *caixas, int **soma, int **indexes)
{
int tamanho_vetor = num_caixas;
Caixa *resultado = malloc(sizeof(Caixa)*tamanho_vetor);
int i = 0;
int j = 0;
int valor = soma[i][j];
int total_caixas = 0;
int indice;
while(valor < soma[indice_i][indice_j])
{
if(total_caixas > tamanho_vetor-1)
{
tamanho_vetor = 2*tamanho_vetor;
resultado = realloc(resultado,sizeof(Caixa)*tamanho_vetor);
}
if(indexes[i][j] != -1)
{
indice = indexes[i][j];
resultado[total_caixas] = caixas[indice];
total_caixas++;
j=j+caixas[indice].altura;
valor=soma[i][j];
}
else
{
while(j<indice_j && indexes[i][j] == -1)
{
j++;
}
j--;
while(i<indice_i && indexes[i][j] == -1)
{
i++;
}
i--;
printf("%d i, %d j\n", i, j);
valor = soma[i][j];
}
}
indice = indexes[indice_i][indice_j];
resultado[total_caixas] = caixas[indice];
total_caixas++;
printf("%d\n", soma[indice_i][indice_j]);
printf("%d\n", total_caixas);
for(int i=0; i<total_caixas; i++)
{
printf("%d ", resultado[i].largura);
printf("%d ", resultado[i].altura);
printf("%d ", resultado[i].profundidade);
printf("%d ", resultado[i].valor);
printf("%d ", resultado[i].rotacao);
printf("%d\n", resultado[i].numero);
}
free(resultado);
return;
}
int empilhaCaixas(int capacidade, int profundidade, int largura, Caixa *caixas, int **m, int indice, int **indexes)
{
int m_linha;
int capacidade_linha;
int profundidade_linha;
int largura_linha;
if(m[indice][capacidade]!=0)
{
return m[indice][capacidade];
}
for(int i=0; i<num_caixas; i++)
{
capacidade_linha = capacidade - caixas[i].altura;
profundidade_linha = caixas[i].profundidade;
largura_linha = caixas[i].largura;
if(capacidade_linha >= 0)
{
if(profundidade_linha <= profundidade && largura_linha <= largura )
{
m_linha = empilhaCaixas(capacidade_linha, profundidade_linha, largura_linha, caixas,m, i, indexes)+ caixas[i].valor;
if (m_linha > m[indice][capacidade])
{
m[indice][capacidade] = m_linha;
indexes[indice][capacidade] = i;
}
}
}
}
indice_i = indice;
indice_j = capacidade;
return m[indice][capacidade];
}
int main(int argc, char *argv[] )
{
if(argc != 3)
{
fprintf(stderr,"Argumentos necessarios: \"entrada\" \"saida\"");
exit(EXIT_FAILURE);
}
Caixa *caixas = leCaixas(argv[1]);
char* nome_tabela;
geraRotacao(num_caixas, caixas);
num_caixas=2*num_caixas;
qsort(caixas, num_caixas, sizeof(caixas[0]), compare);
int **m=preencheMatriz(0);
int **indexes=preencheMatriz(-1);
//imprimeCaixas(caixas);
printf("Lucro: %d\n",empilhaCaixas(altura_maxima,max_dimensao,max_dimensao,caixas,m,num_caixas, indexes));
/*nome_tabela = remover(argv[1]);
nome_tabela = concatenar(nome_tabela, "i" );
gravaTabela(indexes,concatenar(nome_tabela,".csv"));
nome_tabela = remover(argv[1]);
nome_tabela = concatenar(nome_tabela, "v" );
gravaTabela(m,concatenar(nome_tabela,".csv"));*/
escreveCaixas(argv[2], caixas, m, indexes);
freeMatriz(m);
freeMatriz(indexes);
free(caixas);
return 0;
}
10
2349
742
360
200
596
385
564
114
137
728
154
135
634
704
715
783
325
267
31
523
495
375
86
250
875
653
763
590
705
155
885
755
515
36
362
926
629
713
425
297
930
50
426
582
585
974
103
253
143
557
712
53
553
77
943
879
637
397
195
102
12
809
872
718
926
921
611
271
763
345
649
796
715
567
807
883
923
976
215
544
537
649
772
134
601
273
981
877
231
452
585
875
614
710
817
348
517
142
344
722
641
160
494
576
841
698
773
775
952
652
368
82
774
708
202
735
608
206
466
125
980
390
676
236
629
682
135
441
369
460
742
588
76
483
289
97
300
538
445
33
700
947
185
525
486
969
369
621
489
856
645
283
650
683
37
873
747
222
456
253
238
119
578
307
66
242
144
264
987
20
527
690
545
709
33
42
640
122
983
488
586
962
302
546
303
221
241
833
816
370
699
26
138
466
457
440
284
270
505
622
641
377
572
20
523
643
583
353
552
21
886
112
737
691
261
489
162
427
435
659
504
180
24
660
530
810
745
836
97
580
889
350
362
416
402
346
161
459
489
643
832
385
232
100
2367
536
95
558
638
185
135
571
825
546
822
435
428
322
281
165
675
895
391
911
640
559
104
10
529
386
815
601
494
703
564
34
98
562
985
652
54
240
89
214
59
249
273
321
843
618
900
239
675
102
217
1
62
690
513
929
422
340
717
414
232
970
10
868
823
204
322
322
42
723
542
780
187
256
460
580
732
847
300
190
76
813
785
605
27
200
406
604
822
616
737
886
650
168
748
433
9
194
413
265
230
675
30
226
534
789
513
376
483
441
407
59
698
638
974
826
207
674
304
642
789
70
689
892
642
696
632
615
197
789
176
54
37
785
515
818
925
460
130
423
15
969
31
549
1
565
317
329
154
793
627
109
466
535
413
614
355
378
804
333
851
857
45
299
567
546
32
277
887
400
925
808
969
656
93
731
411
930
659
780
183
179
937
134
130
992
212
321
657
386
436
897
188
303
494
275
502
878
770
606
675
578
1000
609
341
860
70
140
525
126
771
521
163
509
2
377
246
822
614
338
716
331
510
294
105
782
351
528
648
1
277
97
660
161
365
21
420
379
661
814
928
302
236
526
202
853
776
576
951
544
466
624
892
88
776
400
752
607
405
499
162
353
320
951
369
206
521
988
677
133
343
146
424
886
97
307
923
195
169
816
962
886
218
31
826
808
417
548
266
555
222
41
952
7
619
51
219
775
380
590
937
988
939
615
37
973
885
743
864
187
466
17
341
986
866
78
168
716
868
715
775
46
954
517
131
144
63
536
972
444
856
781
290
59
49
400
154
228
688
519
819
184
877
781
641
768
269
48
253
404
314
197
821
287
494
890
946
121
912
613
538
356
840
973
405
753
997
947
339
105
76
786
106
379
602
397
70
597
467
600
128
183
755
983
519
891
939
632
495
402
384
807
287
392
969
692
736
311
519
727
438
300
1398
869
824
173
272
895
210
374
192
859
950
755
126
677
715
118
668
967
655
368
165
827
639
751
952
853
786
249
649
474
732
450
598
294
98
721
926
923
267
476
345
120
873
790
344
226
476
127
656
310
755
922
639
957
125
47
348
425
117
852
946
215
381
903
488
748
808
596
315
214
507
386
640
529
551
443
531
167
472
972
465
111
773
686
29
12
568
628
39
335
224
99
583
859
825
164
676
659
28
57
936
206
308
724
1
759
496
586
599
698
264
942
976
243
139
326
705
896
946
714
857
831
493
604
37
346
984
854
21
786
320
818
468
984
345
977
234
196
130
42
995
179
264
601
392
617
79
244
928
690
318
210
815
914
914
262
405
80
138
42
981
16
367
512
909
453
788
419
350
223
543
791
274
373
399
506
126
499
919
24
549
807
873
425
808
425
290
712
517
617
670
83
78
358
680
87
575
897
189
487
538
943
393
857
127
853
940
439
14
486
628
130
175
533
931
316
162
659
834
344
714
393
123
357
960
272
23
241
589
417
679
177
66
328
141
462
820
247
733
263
385
118
179
260
93
425
420
478
726
897
118
320
131
260
126
360
88
70
148
825
955
391
516
374
993
355
418
947
682
614
684
873
394
84
879
152
635
702
519
130
340
189
910
450
656
859
678
450
222
724
220
120
937
411
591
967
267
784
448
599
512
572
14
195
48
466
857
772
626
838
75
282
694
155
670
379
904
54
633
908
733
859
619
434
217
400
640
408
753
143
913
479
996
954
506
469
144
401
605
5
737
577
926
80
110
260
901
167
992
701
505
117
803
132
904
813
519
30
852
222
563
728
362
313
876
704
477
960
59
626
62
758
740
278
344
712
616
657
887
147
569
824
662
300
555
230
261
734
900
791
224
328
61
462
486
253
108
831
142
536
789
773
284
321
618
235
590
400
244
611
694
523
956
448
783
567
213
764
683
665
556
678
977
606
570
351
480
902
100
58
561
845
198
790
304
45
79
423
921
534
890
270
870
78
7
901
238
768
841
715
663
566
16
517
807
136
687
720
320
832
792
694
5
857
686
945
513
640
435
389
248
381
528
331
620
426
44
101
136
29
553
462
618
903
678
844
640
285
125
215
827
310
891
955
827
263
983
763
749
749
850
636
917
964
875
791
954
95
422
849
284
2
82
961
311
836
279
678
149
340
809
457
610
924
349
797
307
264
967
691
2
985
721
878
337
880
267
737
405
943
519
512
183
566
417
275
954
462
11
129
554
218
708
430
488
911
981
586
340
849
568
877
270
936
791
233
860
853
172
518
895
387
25
5
778
668
758
401
257
880
883
113
801
946
134
481
500
57
236
506
326
998
206
690
333
390
1
573
788
655
39
81
964
857
227
727
762
980
656
847
988
867
229
100
336
438
225
123
688
273
120
972
1000
242
697
447
63
91
54
750
14
220
487
996
36
95
107
529
387
716
87
512
653
412
350
949
726
2
227
133
698
473
532
937
112
805
812
173
429
679
874
478
610
394
14
129
120
880
191
423
460
13
808
811
726
594
961
126
147
215
673
188
971
502
371
275
737
213
82
413
447
50
12
259
426
627
417
199
851
706
27
295
681
170
551
923
533
665
576
885
789
767
956
126
777
794
38
709
652
632
101
429
101
170
436
824
579
687
114
956
715
381
493
687
348
358
865
434
878
856
212
731
177
420
25
669
613
605
446
983
552
948
287
102
400
25
545
557
622
122
86
677
902
947
957
659
875
995
61
195
213
946
865
901
342
10
924
568
780
817
160
453
235
788
83
727
469
92
880
713
961
432
108
976
855
760
476
162
237
837
79
120
962
111
582
867
89
411
648
100
136
296
861
536
751
65
109
779
448
809
784
438
41
669
411
984
494
506
832
14
106
378
494
202
842
842
112
57
50
618
247
895
946
921
958
49
688
556
797
382
603
898
859
582
776
96
142
642
544
854
370
908
361
450
363
336
786
458
388
545
864
974
104
23
776
101
147
259
585
150
444
894
323
511
851
3
319
933
262
306
463
202
720
360
100
792
39
923
503
778
483
913
967
585
287
891
359
489
728
150
105
520
354
98
731
510
124
665
284
97
511
62
687
118
188
285
179
110
939
706
118
520
379
7
47
964
761
739
988
466
81
298
536
410
196
794
206
494
16
662
898
380
330
440
449
760
902
724
957
69
66
53
227
695
491
445
847
94
864
260
733
663
671
833
591
775
551
393
966
753
658
496
368
940
746
895
756
384
144
47
291
207
882
572
727
957
244
465
963
292
683
361
464
904
869
739
62
647
492
429
563
948
554
877
836
282
965
120
134
455
668
57
174
18
87
665
718
912
850
356
372
54
129
979
329
683
575
200
933
49
284
197
742
829
727
250
819
319
928
223
84
398
59
329
491
306
289
163
576
385
849
877
569
778
445
719
669
970
452
505
582
54
890
774
186
339
795
231
304
115
945
40
406
192
64
500
144
718
977
196
342
502
792
491
816
70
346
714
777
70
998
247
374
425
772
539
400
885
51
419
49
902
941
790
693
505
40
249
953
992
853
124
386
780
840
248
851
22
363
534
292
940
955
260
554
213
333
798
862
310
550
549
641
647
995
113
53
163
96
491
347
580
486
679
463
284
137
55
583
578
891
503
574
545
794
615
191
178
822
16
678
758
310
372
996
109
385
30
742
857
172
426
465
546
970
266
353
168
997
700
979
195
106
6
812
623
217
999
884
419
673
400
2445
568
52
381
460
53
660
402
258
5
557
956
68
378
412
845
253
740
558
79
826
171
172
975
724
396
983
142
371
744
753
168
400
574
89
855
575
463
808
324
306
964
554
528
929
327
717
477
123
938
196
278
335
988
641
153
189
575
653
360
912
675
697
625
483
185
979
553
772
426
386
478
244
960
586
679
599
161
923
855
205
327
744
661
498
43
1000
274
820
799
978
800
983
296
994
588
174
820
225
392
884
455
549
514
402
220
350
812
153
239
195
684
120
280
528
103
153
539
48
798
172
733
880
845
26
715
8
299
630
524
879
461
633
380
29
529
745
150
880
380
540
206
248
537
581
516
181
963
684
423
50
843
231
39
993
789
168
691
190
109
129
129
559
315
996
132
758
564
662
42
692
323
711
57
478
774
642
138
472
369
324
620
672
470
994
793
134
34
636
505
594
499
731
264
319
330
202
971
343
784
284
815
191
354
785
162
870
96
616
739
237
944
412
87
764
741
186
995
979
606
46
195
963
48
813
662
30
619
263
404
251
821
617
320
918
488
401
470
745
65
814
952
466
428
303
332
109
809
516
11
954
169
390
495
814
162
39
213
53
886
996
791
516
226
775
755
370
384
29
251
459
265
659
594
933
228
304
387
836
27
979
648
944
667
192
548
471
686
275
460
911
890
573
349
858
51
248
873
572
566
781
824
971
959
192
418
419
633
325
38
313
492
897
851
926
434
355
566
895
184
300
560
51
490
117
525
193
751
82
893
659
293
13
376
83
675
880
212
482
241
217
859
999
940
846
536
140
75
963
558
554
272
624
439
62
220
150
929
358
100
185
924
632
916
89
103
761
398
862
422
492
649
721
290
877
369
855
539
287
888
295
796
378
563
489
211
344
881
368
915
847
264
444
198
962
452
227
943
419
972
863
731
132
418
376
815
791
540
100
275
866
263
681
366
732
540
119
126
319
786
888
126
807
652
676
204
198
458
3
345
9
221
769
92
297
96
471
364
744
144
724
819
266
160
232
448
630
233
655
585
707
766
982
429
480
577
342
828
495
949
815
578
442
239
882
463
212
979
785
486
668
830
986
38
2
283
937
859
232
920
367
121
626
383
514
675
62
940
262
335
678
661
311
633
575
940
132
691
828
154
769
242
163
843
119
167
646
897
528
673
208
874
576
37
804
758
339
762
274
779
274
875
809
71
916
928
242
831
38
928
54
790
400
857
763
150
186
796
606
606
464
554
592
149
420
549
842
650
982
840
882
199
437
343
868
708
244
937
907
616
420
518
982
407
88
266
54
538
863
641
618
627
491
185
406
905
293
280
43
638
952
805
521
919
853
36
157
916
936
980
602
643
304
975
701
5
120
489
688
627
200
787
113
122
66
229
473
319
220
982
864
346
740
844
867
423
610
779
956
875
86
68
247
214
386
965
396
189
730
141
562
272
159
863
371
308
820
291
941
281
185
754
334
13
709
550
129
145
609
82
641
160
856
448
271
319
973
862
582
226
815
798
87
273
855
479
507
690
704
321
649
813
651
764
609
134
738
658
672
308
721
865
98
482
156
116
376
673
962
153
594
630
330
383
751
758
622
443
929
885
835
198
452
760
238
827
917
9
229
203
747
707
121
854
17
191
71
496
445
30
645
965
623
605
542
950
941
82
274
362
189
855
24
325
425
372
836
437
755
940
910
660
331
307
385
259
592
77
140
495
645
448
819
229
293
276
816
612
590
931
691
717
68
901
438
38
756
274
943
171
878
78
827
279
2
679
293
836
609
885
11
560
700
287
910
73
191
788
770
276
188
842
638
667
229
802
990
497
983
942
698
692
947
494
471
51
859
308
119
721
737
166
901
601
235
80
695
948
205
669
486
675
648
623
639
731
873
73
281
376
220
676
771
352
216
698
506
173
760
832
196
727
572
281
811
46
862
201
121
859
959
496
642
377
812
728
490
407
136
967
17
475
37
605
267
270
930
239
854
247
640
442
610
122
494
600
542
992
7
454
876
154
317
372
383
949
305
112
504
347
5
470
362
678
443
54
593
710
828
947
831
160
526
320
758
969
929
129
475
174
673
91
249
217
572
307
311
207
422
162
391
69
662
656
181
932
874
887
237
603
597
977
450
516
948
628
590
952
436
771
710
175
783
942
342
82
728
359
175
954
632
159
951
687
979
675
516
609
886
135
92
693
148
917
151
122
782
591
722
482
96
896
312
559
803
486
162
625
566
158
455
521
394
176
84
736
965
146
811
613
641
198
798
611
231
984
891
30
400
17
869
316
105
15
476
903
252
912
307
782
544
446
903
502
370
466
912
286
775
193
553
91
522
360
864
64
47
171
610
628
966
243
796
652
247
143
158
874
103
471
533
513
986
25
223
648
562
545
959
322
430
163
844
928
677
747
177
312
963
844
873
470
286
674
177
380
930
456
700
585
256
43
74
922
361
328
525
431
786
818
148
832
317
746
540
640
649
253
293
815
395
439
916
951
814
689
687
229
46
123
341
888
269
703
443
934
948
16
81
425
348
946
304
142
492
862
950
486
342
128
61
783
898
893
78
736
328
676
239
755
675
421
496
302
742
644
344
776
32
876
649
663
508
379
954
513
754
304
390
149
432
154
581
725
30
621
447
549
800
680
268
750
388
350
777
171
962
600
99
985
104
588
651
504
433
981
521
785
892
712
580
716
188
543
621
55
279
112
707
613
390
272
906
671
572
842
86
251
970
8
848
687
586
355
382
38
843
451
356
42
602
386
561
682
221
473
434
586
568
260
427
4
103
143
692
146
319
857
995
148
594
752
76
7
641
948
22
40
308
377
496
83
419
931
462
479
845
840
665
162
363
990
431
672
863
299
704
517
489
225
172
989
207
278
348
482
142
924
734
130
463
572
311
73
135
20
43
504
776
826
157
955
579
752
332
465
575
632
882
705
379
314
275
953
482
457
809
474
120
292
102
768
436
854
513
987
46
966
520
400
710
992
450
313
444
10
192
724
927
724
577
1000
170
629
341
711
493
704
412
842
238
957
49
393
740
395
316
561
784
62
88
287
227
663
289
527
809
276
134
128
191
901
536
688
119
124
608
627
389
420
223
508
166
770
453
890
148
97
922
704
577
12
837
509
413
319
153
52
604
546
922
676
983
516
58
477
939
520
376
418
795
573
589
910
237
18
270
634
438
24
380
294
333
65
435
375
801
12
177
159
713
702
916
283
767
268
998
495
13
819
464
245
324
57
479
160
46
375
873
504
276
40
750
10
982
511
771
130
381
690
76
516
555
353
941
399
195
948
50
640
834
931
176
784
418
349
26
48
642
614
757
294
728
932
421
983
709
484
878
924
415
70
924
733
871
399
498
169
302
176
516
430
897
950
909
36
422
859
377
541
342
329
681
546
806
754
255
477
376
579
513
236
172
501
558
309
320
199
788
884
792
943
543
529
955
273
673
572
617
452
786
703
281
698
623
4
491
891
479
44
854
93
666
39
993
881
782
816
14
11
184
908
557
631
692
831
221
481
528
819
81
419
192
684
814
92
124
195
663
36
934
50
567
155
14
27
548
153
82
612
53
999
259
945
728
370
201
939
503
403
371
28
62
964
325
331
785
625
971
473
861
215
259
503
313
567
711
395
709
922
842
500
1812
194
63
849
53
245
182
217
108
443
349
471
580
199
324
182
36
26
787
512
13
771
302
35
649
219
481
355
774
831
853
561
801
702
24
954
403
884
490
287
895
852
304
13
478
979
46
395
556
517
33
323
240
188
298
521
402
296
282
230
836
930
868
540
491
153
849
676
419
793
578
428
766
529
417
492
36
170
689
590
837
255
730
120
974
504
479
579
167
463
967
5
880
629
36
649
367
513
372
701
213
268
715
857
476
99
563
311
841
638
394
964
176
598
925
31
666
215
895
226
414
798
814
211
206
378
428
176
880
903
767
189
192
833
376
64
705
141
83
859
786
51
569
243
511
454
957
581
545
325
341
731
297
17
771
861
374
621
246
403
746
130
467
585
410
515
906
847
91
43
837
568
357
239
144
685
953
162
298
513
39
979
760
54
354
718
738
136
842
328
165
296
547
281
977
622
176
508
636
303
470
753
822
266
763
231
90
765
420
940
622
191
473
303
217
903
99
825
548
412
710
887
174
952
147
322
505
412
217
247
847
629
643
795
275
661
534
770
398
507
755
637
560
104
592
623
334
657
356
731
29
311
237
877
167
821
796
244
735
964
162
637
481
889
959
363
70
236
20
243
815
473
843
403
620
959
16
632
953
765
860
532
169
620
346
550
254
221
341
930
935
757
829
179
252
120
508
308
521
381
301
22
780
561
376
891
182
976
843
531
844
630
696
688
911
128
358
690
203
187
362
878
882
931
415
711
757
83
209
21
274
564
692
481
562
876
291
603
936
152
326
999
384
959
805
361
808
38
436
678
299
523
826
321
824
508
630
678
960
810
934
75
628
967
687
671
795
801
542
818
859
235
691
133
926
544
876
373
946
481
908
118
140
509
263
737
758
602
275
424
751
43
932
24
542
638
207
94
393
941
871
849
441
392
377
367
631
931
461
211
996
982
236
169
506
755
848
203
609
102
879
783
484
458
200
970
115
755
849
983
195
632
859
131
167
215
154
911
440
239
406
608
245
967
902
795
376
58
36
69
70
967
881
739
270
669
8
696
714
683
565
721
754
790
569
433
49
646
547
519
691
25
937
536
511
392
194
226
985
741
453
392
355
182
852
137
401
35
771
251
310
924
664
671
978
164
951
935
717
220
150
796
805
529
885
604
117
744
171
367
388
608
466
216
693
164
216
73
229
547
797
288
617
469
230
707
392
239
882
692
332
67
988
307
699
125
950
919
346
783
530
220
506
205
547
343
357
277
450
957
789
204
761
564
604
475
759
522
458
295
85
355
979
885
909
445
394
467
374
769
413
1000
750
868
953
830
811
491
378
475
894
623
368
641
94
930
802
674
904
255
438
628
589
591
84
580
758
164
185
190
940
68
890
889
252
731
833
112
205
499
928
174
241
634
888
921
442
934
680
846
980
97
725
9
862
819
642
636
391
799
39
716
647
892
361
76
501
360
548
514
782
968
708
708
257
983
658
237
950
727
462
92
321
827
194
472
187
24
523
150
372
140
694
231
352
691
119
741
435
47
192
496
664
891
266
479
573
458
354
426
976
87
616
677
707
670
691
847
179
112
711
452
987
437
459
133
580
91
163
813
952
649
379
82
991
19
310
940
486
279
113
936
806
346
203
650
416
613
342
116
902
972
756
310
217
408
752
352
755
818
426
719
440
757
478
27
604
799
863
649
929
538
929
214
766
16
757
501
281
681
756
278
96
608
930
913
501
78
376
331
50
826
643
76
73
758
839
503
502
846
310
167
348
921
795
756
400
427
252
285
82
950
765
101
592
192
40
404
943
315
103
379
120
57
882
970
450
574
358
123
880
852
187
863
812
208
209
88
677
431
235
784
795
291
655
826
241
953
446
801
992
228
743
698
714
254
544
987
901
484
282
768
745
152
384
870
61
651
88
741
859
599
539
209
970
164
394
570
243
419
862
575
558
623
714
287
994
68
971
366
424
258
663
490
477
493
227
636
248
640
560
940
444
895
82
532
770
873
288
67
795
740
37
649
603
221
3
801
359
159
286
410
68
284
630
580
433
669
573
176
999
297
211
302
134
865
550
31
182
390
16
526
758
740
917
766
169
846
148
42
68
110
353
715
790
70
216
565
927
89
784
944
403
216
373
43
258
694
203
237
351
606
123
883
21
918
728
539
789
959
708
398
722
356
719
89
939
959
115
905
778
177
432
969
750
253
661
167
346
206
700
507
237
120
369
463
105
326
521
445
172
481
618
645
538
834
762
454
598
653
220
516
645
653
744
613
368
707
567
206
518
396
401
800
728
821
986
138
719
775
944
864
916
463
421
707
683
919
509
471
975
295
76
164
600
178
792
245
735
524
303
95
893
248
564
136
334
242
195
9
991
758
728
80
642
585
684
550
987
460
671
217
14
21
599
952
193
151
769
172
749
660
36
872
710
751
108
878
983
347
408
497
399
234
180
641
884
221
489
251
834
569
448
501
643
236
300
73
481
587
99
966
276
446
767
565
114
385
572
915
198
143
642
683
762
621
40
819
744
722
660
327
229
895
506
950
423
391
36
823
948
610
121
132
629
667
297
694
915
685
646
265
86
106
277
731
796
958
685
870
274
644
549
289
86
133
456
134
558
540
304
114
495
38
465
126
324
326
482
840
485
561
751
517
953
536
785
584
319
377
921
240
610
857
928
553
962
602
324
923
548
866
64
467
514
769
886
539
71
595
741
479
679
221
199
483
44
202
303
161
638
402
244
888
625
646
368
61
656
230
978
740
115
626
750
661
293
991
580
210
998
925
199
916
623
750
489
370
113
951
237
440
140
410
211
689
183
220
683
322
774
430
681
263
762
398
708
498
27
510
713
446
132
588
456
577
989
159
789
82
70
435
564
269
580
464
765
501
957
370
124
383
232
444
932
73
650
61
253
556
277
104
501
930
445
75
491
757
520
152
662
278
151
547
594
496
794
936
17
351
395
842
437
528
28
917
898
168
260
86
920
810
752
219
11
584
664
495
300
384
489
982
688
830
181
65
673
595
767
166
786
328
297
4
331
397
436
225
50
380
945
347
151
616
953
897
962
72
321
759
282
557
65
236
259
532
163
738
62
905
473
569
742
266
585
599
530
87
114
403
686
85
710
261
419
875
597
560
725
432
672
958
151
512
398
426
534
120
277
203
541
658
233
878
914
732
831
401
589
948
110
729
501
132
367
10
993
366
828
781
869
152
51
136
851
420
712
667
548
713
365
267
533
716
603
91
593
106
521
916
550
535
80
38
486
234
207
292
238
245
327
69
695
356
135
597
164
665
313
799
177
278
359
170
776
740
289
837
723
737
722
617
486
887
533
66
993
733
488
648
462
86
924
682
354
180
613
710
874
912
583
382
190
756
860
871
136
403
728
330
992
331
216
789
155
199
301
487
643
606
482
792
351
320
585
85
524
975
87
596
845
272
900
754
14
435
899
154
252
139
400
331
855
367
166
786
864
378
851
197
415
403
799
312
32
50
770
239
96
905
921
540
927
229
903
520
935
639
613
109
622
13
760
192
903
504
896
831
305
145
636
799
487
751
940
978
108
486
576
224
633
142
13
609
74
335
86
750
658
208
208
535
828
944
457
495
89
876
604
701
192
776
371
286
985
410
182
121
599
369
608
857
952
46
440
812
92
955
338
443
853
403
284
978
112
724
177
642
581
914
863
163
547
893
677
414
980
98
517
208
812
213
104
84
44
237
898
591
258
328
893
860
928
755
347
484
550
379
11
11
173
511
114
358
640
303
368
122
671
726
578
473
662
440
464
611
556
923
126
886
269
79
556
643
324
160
171
364
730
998
848
823
48
478
206
112
650
938
128
310
110
706
851
480
59
427
692
602
648
49
327
805
255
340
618
611
864
472
458
458
450
370
680
535
987
748
386
385
765
418
93
66
731
991
563
357
726
55
990
790
783
132
898
459
205
890
163
359
340
503
632
301
598
230
987
460
606
654
530
71
712
159
582
593
66
960
181
370
903
728
59
33
601
655
404
879
598
581
923
606
732
6
783
77
611
17
866
955
368
486
647
634
11
346
98
274
105
958
475
392
518
823
137
673
756
678
1
751
571
591
608
848
680
157
958
680
484
221
363
328
713
253
917
657
103
303
665
749
651
292
155
296
467
863
451
246
255
207
207
174
179
304
186
315
551
836
351
873
682
488
673
876
64
93
428
803
678
35
822
166
664
845
468
302
831
987
601
515
411
528
345
917
646
458
923
216
935
998
518
508
402
248
795
601
76
42
435
437
891
764
477
315
288
236
899
230
107
152
134
30
108
878
143
899
52
376
203
836
597
811
915
945
535
255
96
515
249
621
812
502
265
720
885
740
266
628
8
817
113
163
782
415
909
277
254
400
502
237
526
372
198
330
106
37
660
224
247
463
79
425
491
920
967
990
604
793
16
360
185
483
141
346
654
226
354
69
149
78
444
255
361
844
819
572
787
675
699
631
417
124
941
818
1
378
307
589
861
724
578
293
128
52
214
721
140
184
432
35
286
739
232
777
419
760
45
779
218
849
815
306
195
600
2091
470
618
725
779
153
902
759
113
939
817
2
968
416
748
353
940
834
35
124
290
699
787
592
725
543
739
225
388
761
4
340
913
687
748
475
557
497
872
969
169
548
793
193
384
337
967
334
6
649
925
628
873
928
355
436
396
605
277
324
729
763
495
129
305
168
50
849
522
504
812
884
232
325
88
119
247
998
169
848
745
568
965
937
283
125
914
898
778
736
84
55
294
603
892
740
446
91
125
599
572
800
965
180
32
928
575
801
678
623
361
486
165
388
456
549
806
45
819
983
878
616
720
491
896
985
631
732
550
970
175
655
385
65
809
893
640
262
487
994
20
579
657
118
952
824
392
447
181
677
736
599
727
850
65
95
253
52
597
63
85
322
448
330
858
621
877
454
312
193
591
894
416
685
328
703
58
853
669
993
234
398
533
210
583
977
128
640
313
572
298
676
267
586
596
839
969
155
661
959
611
828
61
737
932
60
513
582
194
843
45
670
699
809
197
952
758
859
888
575
581
747
866
23
156
180
278
376
613
489
665
244
741
75
953
915
387
204
301
463
598
744
490
464
981
81
800
435
931
253
500
957
52
606
322
173
989
202
136
316
335
232
976
288
598
761
943
952
772
958
185
261
614
599
486
456
620
704
966
250
707
301
739
952
485
502
519
668
169
202
534
247
725
60
435
905
958
581
737
207
964
395
848
724
49
247
532
569
831
638
421
309
677
915
999
984
292
335
859
832
824
152
575
115
276
660
291
562
984
469
321
808
549
961
105
568
575
332
959
278
320
577
454
763
614
133
941
57
864
723
997
774
392
594
433
933
658
461
555
526
556
971
557
349
149
877
845
195
183
287
863
946
911
172
855
104
27
673
189
225
34
417
96
785
822
261
954
383
167
167
430
37
944
342
678
977
669
39
374
97
945
608
897
16
337
88
92
215
375
637
813
737
457
247
131
273
674
804
311
61
148
969
257
749
540
552
884
378
716
845
909
993
179
508
68
193
939
789
714
80
114
701
549
583
469
476
381
845
133
792
300
75
972
214
326
131
634
322
756
535
320
365
853
72
324
340
365
996
326
850
859
510
676
882
519
644
468
615
689
285
633
135
721
844
222
15
938
357
993
150
797
85
890
690
523
667
605
310
484
663
63
547
187
445
516
59
837
105
406
636
582
464
921
434
910
892
482
723
109
817
974
552
576
305
231
198
272
366
901
499
414
667
945
768
187
869
950
455
913
515
140
40
858
170
159
996
522
420
575
14
980
430
737
652
606
455
775
67
939
600
266
636
790
458
208
443
438
959
728
271
765
899
583
610
823
692
493
526
731
264
477
278
721
912
133
756
55
59
257
192
257
599
790
850
364
492
606
629
337
744
876
304
421
590
995
697
905
283
24
411
830
171
532
781
946
107
597
650
518
990
600
169
278
525
924
434
547
420
320
645
243
443
4
737
576
952
754
943
768
18
215
638
991
795
376
648
941
159
738
51
420
981
284
126
121
397
876
658
986
111
661
9
682
509
802
47
218
612
354
734
216
669
913
891
310
870
109
640
561
380
906
317
968
847
531
784
846
119
461
464
707
296
13
767
755
316
145
342
194
25
57
471
39
470
642
248
89
913
894
883
320
3
845
964
717
723
33
435
347
571
129
435
194
284
22
601
41
121
452
906
702
816
116
296
381
651
52
61
651
317
208
99
105
785
436
803
756
489
673
390
806
912
970
342
609
689
221
81
483
629
936
994
818
799
380
471
975
219
635
760
610
698
254
624
984
962
680
623
289
313
304
85
659
456
564
453
479
502
293
324
421
149
976
758
883
748
356
318
77
447
41
437
328
464
620
522
715
983
578
524
94
971
557
775
765
544
207
180
542
434
672
54
577
310
109
147
127
450
731
658
84
522
250
379
544
476
777
709
509
814
687
687
855
865
621
125
627
616
736
182
477
790
114
732
773
541
510
984
961
545
280
329
77
563
778
457
16
280
770
143
764
696
759
991
249
130
926
407
904
849
622
547
971
268
962
320
137
719
241
734
837
264
960
569
272
178
499
442
950
848
25
633
240
512
145
189
418
30
108
772
343
931
74
307
425
722
292
403
55
417
878
721
278
746
949
498
934
41
879
335
622
301
588
749
211
16
349
580
539
854
257
677
396
319
633
987
827
168
339
309
347
326
589
943
533
663
457
854
872
539
819
578
915
268
573
304
933
517
69
917
658
971
284
197
401
184
268
104
515
101
573
347
154
133
81
859
102
76
91
430
209
469
892
61
867
917
593
179
935
843
592
70
281
961
867
259
384
37
26
862
144
196
943
524
24
210
907
834
343
626
727
970
720
871
267
339
768
531
370
544
547
994
802
967
444
410
830
609
994
616
445
716
353
528
481
31
7
35
649
76
200
800
416
708
836
948
351
138
848
438
348
24
641
310
997
74
378
610
988
554
115
308
674
672
897
893
338
731
587
554
979
982
720
398
487
388
76
201
120
481
139
870
618
981
327
754
273
926
363
761
15
44
699
386
701
170
482
471
581
409
127
660
594
541
652
530
175
127
909
535
451
279
596
382
927
638
161
943
667
247
850
78
865
23
160
764
287
312
299
212
763
292
850
175
595
521
117
319
751
833
744
901
322
162
307
511
719
217
80
379
893
83
499
905
993
874
587
22
53
821
4
556
187
117
224
536
322
970
949
251
254
335
594
610
481
916
152
800
16
755
655
666
488
507
878
854
64
92
381
716
96
940
768
750
74
338
366
250
536
896
833
800
888
495
952
568
702
115
512
643
93
655
546
491
245
112
163
952
313
458
666
543
617
898
21
551
70
335
658
514
159
373
241
406
186
626
508
147
172
807
395
563
462
190
159
125
533
593
401
555
770
1
489
344
687
977
394
958
459
640
181
991
647
510
256
945
569
818
838
964
657
595
969
824
903
146
838
394
619
718
525
914
63
407
101
36
490
210
916
919
176
71
936
904
250
193
865
432
231
940
335
556
481
325
906
729
168
7
113
255
849
511
16
430
530
543
581
48
15
158
153
457
885
243
346
570
722
895
855
916
781
899
250
835
292
81
525
471
529
452
304
956
958
679
475
315
388
678
75
543
952
603
90
345
204
983
58
614
416
998
355
193
425
176
905
658
455
106
306
57
125
599
52
125
790
316
810
996
855
312
296
218
257
522
882
202
652
964
482
886
466
714
821
611
568
448
566
728
835
395
873
450
691
247
453
397
339
573
144
33
786
866
638
625
962
588
146
885
337
522
526
208
446
178
690
728
709
696
538
160
331
625
125
594
601
135
320
665
725
133
236
291
803
257
9
597
559
568
659
327
39
900
943
521
166
93
218
6
220
958
878
173
39
67
141
813
934
311
147
9
239
258
84
424
946
289
441
515
804
354
286
462
720
869
619
310
731
773
290
446
55
905
134
622
202
414
851
123
797
856
260
927
411
25
765
429
98
601
183
437
985
15
557
604
953
923
375
137
821
784
305
154
517
418
875
342
812
766
167
212
319
502
871
84
253
400
682
34
600
456
506
496
374
429
528
121
950
951
518
65
105
828
407
959
162
209
717
469
492
830
875
381
58
976
915
861
308
501
908
642
811
635
24
63
113
406
403
517
720
309
487
130
197
456
889
281
209
1000
14
554
532
946
179
29
120
176
677
405
695
86
125
778
701
24
455
877
567
576
924
524
157
620
118
733
635
820
43
235
411
421
173
447
664
262
913
687
220
441
998
410
722
256
419
377
284
302
433
903
609
186
618
991
601
275
15
786
412
767
671
927
574
983
122
545
428
140
925
962
5
802
945
467
225
526
250
725
912
145
384
444
731
858
822
930
928
476
756
66
875
833
915
710
496
471
669
359
239
730
374
89
162
70
154
322
321
130
681
377
100
219
327
546
161
657
142
940
701
862
666
626
185
570
944
365
878
973
125
379
662
476
211
539
848
848
627
631
269
465
78
891
784
945
354
636
983
794
483
183
722
134
147
854
835
182
300
1000
671
43
953
825
274
664
824
875
252
393
144
367
829
75
801
319
722
307
221
982
547
433
701
298
586
864
637
940
558
986
137
149
69
272
211
788
651
121
136
299
879
207
665
687
646
598
590
426
118
142
385
852
930
631
600
195
465
132
35
627
362
191
91
443
296
345
230
74
880
972
756
519
216
284
506
423
836
976
627
850
622
220
179
780
297
586
393
717
65
533
735
113
568
911
578
465
850
455
338
353
742
116
27
717
677
546
400
920
454
647
819
949
966
69
265
616
875
862
922
811
887
65
960
379
636
990
297
535
453
191
22
124
232
208
450
846
668
94
412
198
117
516
250
786
798
145
287
886
956
888
553
50
669
361
852
492
241
634
203
812
971
752
474
580
573
230
607
377
141
107
912
504
584
337
827
354
892
94
810
506
456
889
81
898
578
582
201
204
548
76
227
313
40
384
147
745
382
857
559
660
826
285
14
414
378
640
277
370
883
262
147
254
556
27
804
485
95
135
688
559
920
164
800
975
705
738
689
915
903
478
872
475
218
516
191
820
591
502
873
460
712
740
627
711
396
70
316
814
951
847
373
425
276
912
431
1
19
607
584
863
642
876
922
849
872
354
612
725
370
272
84
260
255
419
128
829
340
820
423
787
304
518
14
506
214
260
923
402
139
240
494
568
713
637
868
794
332
877
422
456
500
515
613
633
856
230
753
491
400
482
867
804
968
700
358
835
423
767
432
579
537
437
854
35
369
313
709
851
78
958
499
613
619
696
310
704
52
605
670
230
318
239
182
313
674
25
165
480
751
791
244
520
622
548
716
200
982
921
497
473
387
254
273
496
322
535
869
205
42
575
416
763
868
746
94
965
811
119
687
12
401
403
559
859
725
392
621
64
69
277
484
648
887
784
51
791
947
116
520
109
475
537
748
584
306
624
415
310
150
230
552
626
815
228
531
786
175
259
260
203
925
55
509
293
800
458
621
339
678
321
128
227
69
579
180
112
165
723
394
274
230
251
810
251
804
614
982
279
693
52
743
411
727
245
373
948
176
572
958
643
598
363
399
219
889
525
952
663
653
884
339
682
844
345
47
668
849
573
566
862
522
237
540
241
277
536
379
897
23
417
37
620
62
727
603
582
109
170
606
823
924
884
492
592
604
899
74
421
182
745
958
202
388
938
455
770
834
937
46
826
135
236
49
983
71
937
235
401
25
490
785
233
149
424
151
135
458
246
628
181
780
256
688
585
837
688
52
161
61
40
862
700
746
932
241
337
880
361
942
792
671
385
187
672
685
439
121
931
469
636
160
667
873
529
827
969
230
508
942
613
881
253
401
351
358
992
865
173
204
873
838
44
22
603
268
579
850
423
197
885
963
360
642
105
404
313
996
593
491
109
568
179
280
848
828
607
390
221
281
499
63
326
535
369
2
504
317
820
742
8
853
670
706
74
971
78
630
385
717
565
84
670
584
94
148
200
1140
178
814
50
475
646
566
596
279
196
482
761
894
568
836
664
449
118
343
409
108
125
725
981
590
516
774
35
252
48
65
155
775
755
250
753
472
487
346
864
794
932
664
965
74
456
710
104
792
718
804
81
834
449
766
727
40
158
813
372
49
92
539
245
99
502
919
526
520
63
207
619
149
212
409
114
261
532
960
433
863
243
429
201
213
997
451
332
566
616
77
764
343
331
696
426
703
936
76
586
933
195
14
93
25
578
553
302
359
926
804
933
4
40
412
447
710
122
658
903
510
700
179
297
461
77
883
59
186
899
3
344
859
594
587
723
859
697
8
239
677
988
87
490
395
523
627
821
998
387
935
125
852
667
331
490
298
750
607
555
608
493
681
357
197
167
777
317
568
461
802
823
194
939
383
859
148
45
554
705
377
370
656
562
166
504
103
516
484
170
708
497
466
219
756
115
158
122
452
904
848
781
633
972
285
380
998
836
225
624
686
780
477
840
746
259
373
184
363
171
833
716
541
841
232
135
619
922
565
895
144
71
202
386
322
548
600
631
105
374
206
250
59
291
911
862
977
125
405
498
782
681
291
468
792
311
476
784
451
608
578
503
625
298
636
570
750
968
281
343
863
209
363
926
630
483
864
363
418
821
991
165
677
7
602
834
870
869
546
885
475
225
12
46
613
666
443
474
97
526
67
475
852
371
95
174
175
451
243
497
450
188
750
83
455
458
227
411
452
578
90
24
153
70
633
901
569
721
787
50
835
346
278
438
934
172
366
564
935
113
197
530
767
531
175
542
263
908
40
88
174
905
687
750
709
96
650
501
274
843
803
921
182
567
876
598
103
149
831
334
556
141
565
918
670
826
854
787
279
863
25
111
985
498
744
160
221
792
26
305
978
689
28
962
8
716
379
297
812
167
596
130
779
56
983
626
761
762
211
366
549
469
989
913
257
59
345
724
576
671
921
810
305
467
922
980
525
561
665
658
800
266
169
118
191
251
500
155
832
598
79
831
964
25
966
100
994
589
391
364
63
322
187
24
402
299
831
972
470
943
604
240
499
682
972
899
214
853
86
126
443
808
719
873
971
5
564
35
790
674
428
505
383
147
43
214
312
297
247
787
704
741
395
984
753
793
524
314
364
912
279
36
521
539
138
215
392
360
635
596
304
115
732
744
87
982
573
623
886
325
57
887
210
983
207
843
888
118
267
381
661
745
763
579
344
810
13
940
517
982
259
424
679
375
756
936
149
258
730
523
946
201
646
28
61
790
770
6
170
460
369
705
245
559
974
607
948
991
383
644
333
816
696
111
258
391
723
49
891
278
696
288
154
414
759
78
334
310
3
505
947
192
258
365
763
959
362
714
914
385
595
811
103
215
985
794
50
359
402
452
42
440
62
712
18
146
359
581
422
302
38
115
466
973
868
983
837
657
436
970
308
446
289
443
258
840
921
611
728
526
783
612
709
905
624
31
222
601
101
563
177
226
940
716
381
458
943
440
578
684
864
290
903
294
26
519
112
269
415
975
326
982
57
399
248
319
246
773
230
453
16
19
165
300
874
479
57
833
101
5
430
860
746
327
523
305
437
196
217
849
571
18
441
191
999
291
456
924
369
618
719
377
97
725
965
830
229
752
566
19
616
177
38
633
460
171
684
891
236
191
579
46
529
102
923
393
970
523
774
453
96
682
591
719
852
386
185
538
522
364
753
662
576
585
666
427
997
57
537
435
764
954
891
176
689
181
694
863
738
375
226
88
237
481
593
558
640
414
374
140
530
73
41
213
955
773
853
724
889
885
985
366
280
632
495
107
5
799
654
958
7
5
21
39
53
34
38
91
13
3
4
13
4
4
7
4
4
7
5
2
13
8
2
7
28
35
29
29
56
48
159
115
13
3
4
7
4
2
7
4
2
13
5
2
5
8
2
13
14
2
5
15
4
50
28
34
32
22
22
23
53
47
40
63
43
45
45
28
43
71
71
46
92
89
48
55
69
65
95
95
69
114
81
78
73
127
127
140
146
81
84
131
84
99
131
75
143
104
106
106
106
149
167
170
178
13
3
2
13
3
2
5
3
4
7
3
2
7
3
2
13
4
4
13
4
2
7
5
4
13
5
4
7
5
4
7
5
4
7
5
4
5
5
2
7
5
4
13
6
4
13
6
4
7
6
2
13
7
4
13
7
4
5
7
4
7
8
2
7
8
4
7
8
4
13
8
2
13
8
2
7
8
4
13
9
4
7
9
4
7
9
4
7
9
4
13
10
4
13
10
4
13
11
4
13
11
4
7
11
2
7
11
2
13
11
4
5
11
4
7
11
4
13
11
4
5
12
2
13
12
4
7
12
4
7
13
4
7
13
4
7
13
4
13
14
2
13
14
4
13
15
2
13
15
2