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