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