Page 2 of 2

Re: 10360 - Rat Attack

Posted: Sun Apr 14, 2013 6:28 pm
by ahmed ameen
please help me and give me some inputs to try ,, i tried all cases in this topic and i still get WA

Re: 10360 - Rat Attack

Posted: Thu Apr 18, 2013 11:48 pm
by brianfry713
Input:

Code: Select all

20
11
14
457 967 123
963 412 10
240 652 229
626 519 41
573 341 133
419 760 224
687 588 252
183 202 130
410 464 249
64 544 79
774 1003 18
682 942 227
883 159 154
926 785 61
9
12
23 128 80
783 768 88
347 474 198
551 894 188
1015 684 195
534 882 199
513 1 198
430 558 207
589 741 188
349 423 82
684 447 107
414 207 101
7
4
631 410 18
502 400 183
161 454 228
20 257 123
46
13
527 580 214
93 298 146
444 722 99
103 146 206
517 353 178
327 912 139
738 994 92
115 44 155
569 653 26
828 750 230
550 254 102
620 347 177
936 791 134
45
12
161 498 80
517 640 47
404 389 137
375 642 27
419 31 38
47 468 114
799 929 196
28 945 237
377 237 40
143 252 196
15 416 175
406 935 202
40
5
975 531 72
592 54 22
626 149 196
69 47 208
999 497 211
46
2
318 135 170
463 390 111
32
16
921 886 97
482 986 218
435 494 161
4 550 182
630 701 250
702 748 74
678 223 29
574 770 14
712 250 245
77 202 120
885 98 102
578 580 235
587 1015 146
262 1020 243
26 627 55
952 304 75
33
6
494 520 200
240 594 187
490 108 246
692 104 158
792 987 38
347 808 135
49
11
568 337 229
594 964 28
521 244 229
263 203 219
784 737 126
353 960 121
463 237 185
567 401 92
532 118 71
315 424 83
414 993 75
40
10
339 846 134
585 581 242
788 809 118
503 256 158
440 191 96
680 822 51
56 195 123
177 943 163
603 1005 189
573 380 188
20
19
870 178 252
427 506 52
213 594 62
470 11 213
663 919 110
463 344 38
658 303 35
576 577 106
557 243 4
939 265 49
635 113 227
916 542 136
962 757 35
489 202 91
458 868 115
82 306 61
791 966 1
651 520 104
93 54 139
44
17
1005 237 139
93 543 252
637 333 161
370 719 5
572 90 60
417 381 224
725 1019 171
667 934 24
164 404 237
218 117 70
186 98 207
791 191 61
262 829 176
697 176 71
599 750 183
960 143 154
379 868 58
13
5
204 429 127
608 360 180
726 399 253
826 676 81
1017 473 160
6
4
787 1001 133
363 727 60
298 870 86
679 715 15
31
11
123 674 192
734 11 244
437 411 113
238 64 194
232 539 225
33 119 242
9 554 247
736 903 173
583 530 242
276 450 243
481 575 197
37
13
718 67 194
106 880 232
172 495 150
711 199 13
832 693 109
361 526 246
242 658 141
772 445 47
199 479 18
775 160 181
36 880 75
760 988 210
698 135 27
49
10
178 48 197
873 262 255
374 189 177
8 699 175
455 461 134
934 703 31
71 260 193
954 910 165
917 391 240
30 370 210
49
4
302 509 172
564 504 158
753 740 208
430 726 53
36
17
123 569 226
197 832 35
126 719 71
18 85 56
48 457 137
927 1005 199
413 378 96
919 128 71
637 910 11
338 100 89
225 223 196
48 420 128
867 548 87
375 567 154
292 617 102
463 521 124
938 937 190
AC output:

Code: Select all

676 577 252
542 885 387
154 447 228
523 607 240
2 423 289
959 491 283
272 89 170
680 218 274
457 75 246
519 288 458
463 216 254
850 158 252
174 73 277
713 386 253
781 995 133
0 523 247
69 843 307
824 213 255
704 691 208
902 969 389

Re: 10360 - Rat Attack

Posted: Sat Aug 31, 2013 8:52 am
by sith
Hi I've got WA,

My solution gives correct answers for posted examples.
Could somebody help me, why am I getting WA, for which input my solution gives wrong answer

Code: Select all

import java.io.*;
import java.util.*;

class Main {


    public static final XComparator X_COMPARATOR = new XComparator();
    public static final YComparator Y_COMPARATOR = new YComparator();

    public static void main(String[] args) {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        Scanner scanner = new Scanner(reader);

        try {

            int numberOfCases = scanner.nextInt();
            for (int i = 0; i < numberOfCases; i++) {
                int d = scanner.nextInt();
                int numberOfRatPopulations = scanner.nextInt();
                Region region = new Region(d);

                for (int j = 0; j < numberOfRatPopulations; j++) {

                    int x = scanner.nextInt();
                    int y = scanner.nextInt();
                    int size = scanner.nextInt();

                    RatPoint ratPoint = new RatPoint(x, y, size);
                    region.add(ratPoint);
                }

                List<Region> xRegions = region.split(X_COMPARATOR);

                List<Region> allRegions = new ArrayList<Region>();

                for (Region xRegion : xRegions) {
                    List<Region> regions = xRegion.split(Y_COMPARATOR);
                    allRegions.addAll(regions);
                }


                RatPoint best = getBestPoint(allRegions);


                writer.write(best.toString());

            }

            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static RatPoint getBestPoint(List<Region> regions) {

        List<RatPoint> result = new ArrayList<RatPoint>();
        for (Region allRegion : regions) {
            RatPoint ratPoint = allRegion.toResult();
            result.add(ratPoint);
        }

        Collections.sort(result, new Comparator<RatPoint>() {
            @Override
            public int compare(RatPoint o1, RatPoint o2) {
                int damageDiff = o2.size - o1.size;
                if (damageDiff != 0) {
                    return damageDiff;
                }

                int xDiff = o1.x - o2.x;
                if (xDiff != 0) {
                    return xDiff;
                }
                return o1.y - o2.y;
            }
        });
        return result.iterator().next();
    }

    static class Region {

        private List<RatPoint> points = new ArrayList<RatPoint>();
        private int d;

        public Region(int d) {
            this.d = d;
        }


        public void add(RatPoint ratPoint) {
            points.add(ratPoint);
        }

        void setPoints(List<RatPoint> points) {
            this.points = points;
        }

        public List<Region> split(Comparator<RatPoint> comparator) {
            Collections.sort(points, comparator);

            List<Region> result = new ArrayList<Region>();

            LinkedList<RatPoint> queue = new LinkedList<RatPoint>();

            Iterator<RatPoint> iterator = points.iterator();
            RatPoint first = iterator.next();
            queue.add(first);

            while (iterator.hasNext()) {
                RatPoint point = iterator.next();
                if (Math.abs(comparator.compare(first, point)) <= 2 * d) {
                    queue.add(point);
                } else {
                    addRegion(result, queue);

                    first = findNextFirst(queue, point, comparator);
                    queue.add(point);


                }
            }
            addRegion(result, queue);

            return result;
        }

        private void addRegion(List<Region> result, LinkedList<RatPoint> queue) {
            Region region = new Region(d);
            region.setPoints(new ArrayList<RatPoint>(queue));
            result.add(region);
        }

        private RatPoint findNextFirst(LinkedList<RatPoint> queue, RatPoint point, Comparator<RatPoint> comparator) {

            RatPoint newFirst;
            while ((newFirst = queue.poll()) != null) {
                if (Math.abs(comparator.compare(newFirst, point)) <= 2 * d) {
                    queue.addLast(newFirst);
                    return newFirst;
                }
            }

            return point;

        }


        public RatPoint toResult() {

            int damage = 0;
            int maxX = Integer.MIN_VALUE;
            int maxY = Integer.MIN_VALUE;
            for (RatPoint point : points) {
                damage += point.size;
                if (point.x > maxX) {
                    maxX = point.x;
                }
                if (point.y > maxY) {
                    maxY = point.y;
                }
            }
            return new RatPoint(Math.max(0, maxX - d), Math.max(0, maxY - d), damage);
        }
    }

    static class RatPoint {
        int x, y, size;

        RatPoint(int x, int y, int size) {
            this.x = x;
            this.y = y;
            this.size = size;
        }

        @Override
        public String toString() {
            return x + " " + y + " " + size + "\n";
        }
    }

    private static class XComparator implements Comparator<RatPoint> {
        @Override
        public int compare(RatPoint o1, RatPoint o2) {
            return o1.x - o2.x;
        }
    }

    private static class YComparator implements Comparator<RatPoint> {
        @Override
        public int compare(RatPoint o1, RatPoint o2) {
            return o1.y - o2.y;
        }
    }
}

Re: 10360 - Rat Attack

Posted: Tue Sep 03, 2013 10:51 pm
by brianfry713
Input:

Code: Select all

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

Code: Select all

804 351 3056
301 729 2007
679 914 2206
571 892 1429
427 460 788

Re: 10360 - Rat Attack

Posted: Fri Oct 02, 2015 8:25 am
by infinia249
I would like to know what caused my code to exceed the time limit. Tested the random input from uDebug and the outputs were fine.

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main () {
	long s, d, n, x[20000], y[20000], i[20000];
	// cin >> s;
	scanf( "%i", &s );
	for ( int j = 0; j < s; j++ ) {
		// cin >> d >> n;
		scanf( "%i %i", &d, &n );
		int xmin = 0, xmax = 0, ymin = 0, ymax = 0, xo = 0, yo = 0, st = 0;
		for ( int k = 0; k < n; k++ ) {
			// cin >> x[k] >> y[k] >> i[k];
			scanf( "%i %i %i", &x[k], &y[k], &i[k] );
			if ( x[k] < xmin ) {
				xmin = x[k];
			}
			if ( y[k] < ymin ) {
				ymin = y[k];
			}
			if ( k == 0 ) {
				xmin = x[k];
				ymin = y[k];
			}
			if ( x[k] > xmax ) {
				xmax = x[k];
			}
			if ( y[k] > ymax ) {
				ymax = y[k];
			}
		}
		xmin -= d;
		if ( xmin < 0 ) {
			xmin = 0;
		}
		ymin -= d;
		if ( ymin < 0 ) {
			ymin = 0;
		}
		xmax += d;
		if ( xmax > 1025 ) {
			xmax = 1025;
		}
		ymax += d;
		if ( ymax > 1025 ) {
			ymax = 1025;
		}
		for ( int ys = ymin; ys < ymax; ys++ ) {
			for ( int xs = xmin; xs < xmax; xs++ ) {
				int sizetemp = 0;
				for ( int l = 0; l < n; l++ ) {
					if ( max( abs( ys - y[l] ), abs( xs - x[l] ) ) <= d ) {
						sizetemp += i[l];
					}
				}
				if ( sizetemp > st ) {
					st = sizetemp;
					xo = xs;
					yo = ys;
				}
			}
		}
		// cout << xo << " " << yo << " " << st << endl;
		printf( "%i %i %i", xo, yo, st );
	}
	return 0;
}