萌新求助玄学问题

输入：1000 1
178 562 717 982 29 960 251 201 453 172 589 743 899 283 256 329 579 555 979 250 876 281 571 375 12 612 189 935 684 283 604 901 820 529 433 340 14 745 983 812 390 85 674 968 291 717 975 715 638 780 266 587 248 966 644 280 952 231 120 510 413 536 783 161 885 316 583 394 918 622 589 821 993 633 546 375 613 200 945 73 3 626 349 622 681 325 380 190 440 270 725 983 490 371 553 429 935 945 29 558 943 295 389 147 241 683 877 419 127 822 27 323 392 54 445 894 29 528 554 738 154 783 339 515 562 71 300 842 96 877 182 912 698 479 173 141 304 461 409 159 120 333 903 648 281 590 848 680 529 42 932 739 751 282 798 568 801 616 308 639 856 642 19 683 619 432 897 576 428 826 863 564 455 506 402 576 72 743 136 9 116 332 415 411 237 412 537 870 993 388 656 39 419 166 945 686 922 411 413 923 396 801 493 247 14 30 273 172 437 250 196 804 444 18 522 304 370 735 945 255 304 14 293 697 804 470 229 628 997 66 183 851 80 397 874 839 174 111 811 80 877 659 790 155 421 618 423 1000 547 371 302 523 908 445 464 49 678 312 824 506 585 956 108 959 610 772 214 436 437 668 818 394 139 323 518 786 791 574 940 217 839 402 802 698 718 925 578 425 719 346 776 729 757 38 491 914 860 936 937 318 704 355 481 884 981 284 143 387 704 571 502 926 166 457 484 217 305 332 51 761 297 20 788 770 567 878 111 838 555 449 966 404 451 429 897 157 881 119 69 719 261 83 753 382 214 657 292 848 11 853 833 402 915 401 897 197 622 452 977 65 785 841 675 577 214 309 992 250 902 231 756 208 941 653 1 197 75 199 315 195 402 520 878 413 525 14 382 675 509 771 684 407 369 460 888 227 29 69 936 219 719 269 577 160 579 571 327 811 437 219 561 450 437 217 825 238 698 744 179 974 365 407 251 345 508 531 649 828 748 919 513 476 849 77 665 352 932 739 243 627 422 696 223 345 495 572 854 213 235 365 314 516 862 922 777 810 669 731 300 730 293 694 976 306 291 617 254 572 928 46 758 235 952 406 14 604 763 500 963 221 930 792 109 500 536 535 266 658 41 693 74 921 193 432 797 574 196 836 189 980 915 292 847 616 755 79 985 571 981 499 143 492 693 628 520 396 114 731 456 573 883 18 303 378 308 29 723 324 319 383 957 419 891 349 285 32 261 732 751 295 589 100 661 264 710 140 513 237 803 107 309 132 383 664 845 162 776 991 246 450 996 555 734 671 322 691 14 641 706 972 148 440 549 679 294 867 13 556 493 581 240 793 92 417 33 665 285 762 220 154 361 684 208 450 704 663 99 899 133 73 256 474 212 964 401 121 325 803 976 376 945 579 168 235 92 673 241 944 519 254 585 262 701 636 505 224 779 149 222 98 348 625 96 746 51 902 205 782 253 425 965 403 791 423 865 33 653 135 169 252 795 393 960 624 93 633 381 572 319 615 969 676 324 776 485 464 938 541 757 139 824 299 290 667 973 201 799 384 30 539 758 274 277 455 774 511 241 306 741 355 109 605 899 876 620 965 723 251 807 791 897 634 689 205 41 268 530 597 498 383 499 443 923 678 982 84 748 727 928 557 906 413 953 876 600 785 653 584 751 659 543 735 432 183 898 803 477 779 513 894 980 724 497 513 959 671 658 160 967 443 528 141 285 31 973 138 498 510 694 399 299 1000 549 834 640 367 798 12 668 193 666 260 778 874 676 957 246 848 880 650 433 820 313 740 490 492 31 464 330 317 529 906 141 57 698 686 736 106 986 100 756 127 543 717 437 146 399 43 404 359 111 85 252 347 965 492 882 781 294 644 617 154 323 79 677 936 757 248 478 661 531 598 721 439 72 173 722 775 163 670 834 958 216 904 346 4 609 790 406 929 304 670 686 404 214 508 968 46 615 712 215 172 185 776 543 295 266 300 994 609 827 107 98 426 161 947 640 822 634 109 154 551 109 839 851 587 188 973 223 490 642 642 609 233 277 482 509 457 713 904 677 847 254 749 805 971 267 53 241 637 350 591 380 739 269 749 960 32 516 285 711 751 128 815 434 957 924 493 761 387 993 765 132 537 112 901 309 55 59 693 887 744 84 127 201 76 303 677 189 852 914 623 300 999 286 234 206 144 225 161 974 602 841 839 85 939 706 940 126 990 10 643 990 455 478 912 442 185 655 792 34 917 672 989 619 503 406 125 972 65 811 800 345 58 591 526 35 820 958
输出：150991

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=5000009;
ll n,m,pt,f[M],d[M],p[M],ans;
int main(){
	cin>>n>>m;
	if(m==1){
		for(ll i=1;i<n;i++){cin>>f[i]; d[f[i]]++;}
		for(ll i=1;i<n-1;i++){
			pt++; while(d[pt]) pt++;
			p[i]=f[pt];
			while(i<n-1&&!--d[p[i]]&&p[i]<pt) p[i+1]=f[p[i++]];
		}
		for(ll i=1;i<n-1;i++) ans^=(i*p[i]);
	}
	else{
		for(ll i=1;i<n-1;i++){cin>>p[i]; d[p[i]]++;} p[n-1]=n;
		for(ll i=1;i<n;i++){
			pt++; while(d[pt]) pt++; f[pt]=p[i];
			while(i<n&&!--d[p[i]]&&p[i]<pt) f[p[i++]]=p[i];
		}
		for(ll i=1;i<n;i++) ans^=(i*f[i]);
	}
	cout<<ans<<endl;
	return 0;
}