gitzhou/director-random-distribute-via-weight-1.cpp

## director-random-distribute-via-weight-1.cpp
//
//  director-random-distribute-via-weight-1
//
//  有 N 个消费者，分别有相应的权值
//  随机分发消息队列中的消息
//  各个消费者消费的消息数量的比值，总体近似为权值的比值
//

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

class Consumer {
public:
    explicit Consumer(int weight = 0) : weight_(0) {}

    void set_id(char id) {
        id_ = id;
    }

    void set_weight(int weight) {
        weight_ = weight;
    }

    inline int weight() const {
        return weight_;
    }

    inline void consume(int message_id ) {
        message_id_list_.push_back(message_id);
    }

    inline size_t consumed_messages_count() const {
        return message_id_list_.size();
    }

    void display_consumed_messages() const {
        const int MESSAGE_ID_COUNT_PER_LINE = 15;
        cout << id_ << ": " << message_id_list_.size();
        for (int i = 0; i < message_id_list_.size(); ++i) {
            if (i % MESSAGE_ID_COUNT_PER_LINE == 0) {
                cout << endl;
            }
            cout << message_id_list_[i] << ' ';
        }
        cout << endl;
    }

private:
    char id_;
    int weight_;
    vector<int> message_id_list_;
};

void distribute(vector<Consumer> &consumers, int message_id) {
    int total_weight = 0;
    for (int i = 0; i < consumers.size(); ++i) {
        total_weight += consumers[i].weight();
    }

    int weight_random = rand() % total_weight;
    // locate weight_random's period
    int index = 0, period_weight = 0;
    while (index < consumers.size()) {
    	period_weight += consumers[index].weight();
    	if (weight_random < period_weight) {
    		break;
		}
    	++index;
	}
	consumers[index].consume(message_id);
}

int main(int argc, const char * argv[]) {
	const int TOTAL_MESSAGE_COUNT = 1000;
    srand((unsigned int)time(NULL));

    int consumer_count;
    cin >> consumer_count;

    vector<Consumer> consumers(consumer_count);
    for (int i = 0; i < consumer_count; ++i) {
        int weight;
        cin >> weight;
        consumers[i].set_id('A' + i);
        consumers[i].set_weight(weight);
    }

    for (int i = 0; i < TOTAL_MESSAGE_COUNT; ++i) {
        distribute(consumers, i);
    }

    for (int i = 0; i < consumer_count; ++i) {
        consumers[i].display_consumed_messages();
        cout << endl;
    }

    return 0;
}

## run-result-0.txt
7 3 8 2 1 4 3 2
A: 139
6 22 24 36 43 70 72 78 91 97 119 123 129 145 164
165 173 185 198 199 200 203 209 210 212 216 235 237 241 246
259 283 284 285 286 287 295 301 302 328 330 333 339 340 347
369 373 375 376 379 388 391 395 409 422 430 433 434 442 470
480 481 490 509 513 514 520 524 531 533 539 548 549 550 557
569 574 579 605 616 617 619 621 629 636 640 645 649 650 665
666 667 672 685 688 701 705 715 722 725 732 739 741 749 751
767 789 796 807 812 813 814 817 819 830 843 844 855 856 864
866 868 869 871 885 887 892 901 918 924 926 929 938 941 949
960 976 985 986

B: 341
0 3 4 7 9 11 12 15 17 20 21 29 32 37 38
39 40 41 42 45 52 56 58 62 63 65 66 67 73 83
85 89 93 94 95 96 99 103 105 110 111 113 118 120 126
128 131 135 136 137 138 139 141 143 146 147 148 151 153 154
156 160 161 163 166 167 169 170 172 178 179 184 188 190 191
193 195 197 201 206 208 211 217 218 219 232 239 240 242 243
244 245 250 254 255 256 257 258 260 262 265 266 269 271 272
273 274 277 278 279 282 290 292 293 297 305 308 309 311 314
316 317 319 320 321 322 323 325 329 335 337 350 352 358 359
361 364 367 368 374 377 378 380 382 387 393 394 399 401 403
404 406 411 412 415 424 432 435 438 439 440 441 445 446 452
457 461 465 466 467 473 477 478 479 485 489 491 492 496 497
507 511 515 517 518 521 526 530 534 535 540 541 542 544 556
561 566 568 570 580 584 585 587 595 600 604 609 622 623 625
627 628 634 635 638 641 642 643 644 646 647 653 656 658 660
661 663 676 677 680 681 684 692 693 699 702 703 704 709 717
720 721 723 724 729 731 740 742 744 746 748 755 756 757 759
760 764 768 769 772 773 774 777 779 780 782 785 786 790 792
793 794 795 797 798 800 802 805 816 821 822 823 824 828 833
835 839 840 841 847 849 851 854 857 859 862 873 874 876 878
893 895 896 902 905 907 908 909 910 912 913 919 922 925 928
931 936 939 943 947 953 957 958 959 962 967 968 969 970 971
974 975 978 980 981 984 988 991 992 993 996

C: 99
14 16 25 57 60 61 64 68 69 112 121 158 159 177 186
187 196 222 230 231 252 268 270 275 280 298 318 343 353 354
381 383 398 405 423 428 429 436 443 447 449 459 460 462 464
471 483 500 506 510 523 554 578 581 583 592 601 608 611 613
614 620 624 648 652 654 657 662 664 670 675 682 690 691 695
696 698 708 712 716 735 737 753 765 787 827 848 879 883 890
894 904 906 916 930 934 964 979 994

D: 55
35 50 76 80 84 101 117 144 213 215 247 248 288 300 304
349 363 372 396 397 400 408 410 419 474 475 484 522 525 527
536 545 546 552 589 591 598 639 673 689 711 714 775 788 791
810 837 838 850 889 921 935 948 973 999

E: 194
8 10 19 27 28 31 34 44 46 51 53 59 71 77 81
82 88 90 92 100 106 107 114 115 122 124 130 140 149 152
157 162 171 174 183 192 194 202 220 225 226 227 228 229 233
234 236 238 249 251 253 263 264 267 276 294 296 303 307 310
312 313 315 326 338 342 344 345 356 360 362 365 366 384 390
392 414 417 421 426 427 451 453 454 456 463 468 469 472 487
493 494 498 501 503 504 508 529 538 553 555 558 559 563 564
565 567 571 572 582 590 596 597 599 602 603 606 610 612 615
618 626 630 631 632 637 655 671 678 686 697 700 706 707 718
719 726 727 728 733 734 745 750 761 762 763 770 778 781 784
803 809 811 815 818 825 829 834 836 842 846 852 860 861 863
865 870 872 875 877 880 881 882 884 897 903 911 914 917 933
940 944 945 946 950 951 952 955 963 966 982 983 989 998

F: 102
1 2 13 18 23 26 30 33 47 49 54 55 75 79 86
87 98 104 109 127 134 142 150 189 204 214 223 224 281 289
291 306 324 331 332 334 336 348 355 371 385 389 407 413 420
425 431 437 448 450 455 458 482 499 512 516 547 551 562 575
577 586 607 633 651 659 668 669 679 694 710 713 738 743 747
758 766 771 776 799 804 808 832 845 858 867 888 891 900 923
927 932 937 942 954 956 961 972 977 990 995 997

G: 70
5 48 74 102 108 116 125 132 133 155 168 175 176 180 181
182 205 207 221 261 299 327 341 346 351 357 370 386 402 416
418 444 476 486 488 495 502 505 519 528 532 537 543 560 573
576 588 593 594 674 683 687 730 736 752 754 783 801 806 820
826 831 853 886 898 899 915 920 965 987

## run-result-1.txt
7 3 8 2 1 4 3 2
A: 115
2 5 6 16 17 45 46 49 77 78 87 93 94 96 112
128 160 169 173 201 207 225 227 232 242 244 253 258 274 284
289 307 320 321 329 332 342 364 377 381 388 405 412 415 417
420 436 466 481 485 488 500 503 505 520 524 529 532 548 551
555 561 567 577 588 589 598 602 610 612 625 626 641 658 659
663 666 672 675 679 686 689 692 712 724 735 737 740 745 755
777 782 785 797 799 803 816 818 841 860 866 877 888 900 934
938 948 950 953 954 962 973 993 994 996

B: 340
3 4 10 11 12 14 18 19 27 28 30 36 38 40 51
52 54 58 59 61 63 66 71 74 79 81 84 88 89 91
95 97 99 101 103 104 106 108 117 122 123 130 136 138 139
141 143 147 150 156 157 158 161 164 166 172 175 178 183 185
187 189 190 197 198 204 206 209 210 211 216 218 220 226 229
230 231 235 248 252 256 259 260 265 267 268 269 273 276 279
282 285 287 288 299 302 303 305 309 312 315 317 318 319 322
325 326 328 331 335 339 340 346 348 349 358 359 360 361 362
366 373 374 378 379 383 384 387 391 392 397 399 400 403 407
408 411 421 423 427 428 432 434 437 438 443 444 447 450 452
453 455 456 457 459 460 461 467 469 471 472 476 482 483 484
490 492 494 496 512 519 522 525 527 531 535 539 540 544 549
550 556 557 558 560 566 570 578 580 581 586 587 591 595 599
600 601 604 605 609 611 613 614 616 622 623 624 628 634 635
639 645 649 650 651 660 661 670 677 678 680 683 684 695 696
704 705 708 710 711 713 714 717 719 721 725 728 730 736 738
739 741 742 743 744 751 752 756 759 760 763 766 767 770 772
773 774 775 786 788 789 790 791 794 798 801 804 805 809 811
819 820 822 823 824 830 831 837 838 843 848 854 855 856 857
859 861 862 863 864 868 869 870 871 876 878 884 886 891 895
897 899 906 908 909 912 913 917 919 926 927 929 930 931 932
936 937 940 941 942 943 944 945 946 949 957 961 971 975 976
977 979 982 983 985 988 989 990 991 995

C: 77
20 31 35 42 48 50 55 57 68 76 116 121 126 132 137
144 149 167 195 203 214 221 222 246 250 251 275 283 301 316
341 343 353 363 376 390 414 418 424 426 448 463 473 486 508
513 534 565 571 575 582 593 662 664 694 729 764 769 781 807
815 817 829 835 847 851 858 881 883 890 911 916 955 965 968
978 998

D: 41
8 21 56 72 119 124 146 151 155 182 199 264 298 314 327
334 338 350 413 430 441 502 545 584 637 674 682 688 746 784
806 821 832 873 885 918 920 922 939 947 984

E: 188
1 22 23 24 43 53 60 64 65 69 73 85 92 100 102
105 109 111 125 129 133 134 135 142 148 162 163 165 170 171
174 176 184 186 191 193 194 196 200 212 219 224 234 237 239
240 255 261 271 277 290 292 293 294 295 324 333 336 344 345
347 356 357 365 367 368 370 371 386 393 394 398 401 402 404
409 429 433 435 439 445 449 454 458 464 465 468 475 477 480
495 497 501 504 509 511 514 515 517 518 523 528 530 533 536
542 546 547 552 564 568 573 574 583 585 627 629 630 638 640
642 644 646 647 648 655 656 665 668 673 685 690 691 693 697
698 700 701 703 706 709 720 722 726 733 734 748 749 753 754
757 765 771 776 780 812 813 825 833 836 839 840 842 845 846
852 875 879 887 892 893 896 903 905 907 910 914 925 928 933
951 952 964 966 970 980 992 999

F: 153
0 7 9 15 25 26 29 32 33 39 41 44 47 62 67
75 83 110 113 114 118 127 140 145 154 159 177 179 180 181
188 192 202 205 213 217 223 228 236 249 254 257 262 263 266
281 286 296 300 304 308 310 313 323 330 351 352 355 372 382
385 389 395 396 406 410 416 419 425 431 440 470 474 478 479
491 493 506 507 510 516 521 538 541 553 559 562 563 569 579
590 597 603 606 615 620 621 633 636 643 653 654 657 667 669
671 676 681 687 702 707 715 718 723 732 747 750 758 761 762
778 779 787 792 795 796 800 814 826 827 828 834 844 850 867
880 894 902 921 923 924 935 956 958 959 960 967 969 972 974
981 987 997

G: 86
13 34 37 70 80 82 86 90 98 107 115 120 131 152 153
168 208 215 233 238 241 243 245 247 270 272 278 280 291 297
306 311 337 354 369 375 380 422 442 446 451 462 487 489 498
499 526 537 543 554 572 576 592 594 596 607 608 617 618 619
631 632 652 699 716 727 731 768 783 793 802 808 810 849 853
865 872 874 882 889 898 901 904 915 963 986
	//
	// director-random-distribute-via-weight-1
	//
	// 有 N 个消费者，分别有相应的权值
	// 随机分发消息队列中的消息
	// 各个消费者消费的消息数量的比值，总体近似为权值的比值
	//

	#include <iostream>
	#include <vector>
	#include <ctime>
	#include <cstdlib>
	using namespace std;

	class Consumer {
	public:
	explicit Consumer(int weight = 0) : weight_(0) {}

	void set_id(char id) {
	id_ = id;
	}

	void set_weight(int weight) {
	weight_ = weight;
	}

	inline int weight() const {
	return weight_;
	}

	inline void consume(int message_id ) {
	message_id_list_.push_back(message_id);
	}

	inline size_t consumed_messages_count() const {
	return message_id_list_.size();
	}

	void display_consumed_messages() const {
	const int MESSAGE_ID_COUNT_PER_LINE = 15;
	cout << id_ << ": " << message_id_list_.size();
	for (int i = 0; i < message_id_list_.size(); ++i) {
	if (i % MESSAGE_ID_COUNT_PER_LINE == 0) {
	cout << endl;
	}
	cout << message_id_list_[i] << ' ';
	}
	cout << endl;
	}

	private:
	char id_;
	int weight_;
	vector<int> message_id_list_;
	};

	void distribute(vector<Consumer> &consumers, int message_id) {
	int total_weight = 0;
	for (int i = 0; i < consumers.size(); ++i) {
	total_weight += consumers[i].weight();
	}

	int weight_random = rand() % total_weight;
	// locate weight_random's period
	int index = 0, period_weight = 0;
	while (index < consumers.size()) {
	period_weight += consumers[index].weight();
	if (weight_random < period_weight) {
	break;
	}
	++index;
	}
	consumers[index].consume(message_id);
	}

	int main(int argc, const char * argv[]) {
	const int TOTAL_MESSAGE_COUNT = 1000;
	srand((unsigned int)time(NULL));

	int consumer_count;
	cin >> consumer_count;

	vector<Consumer> consumers(consumer_count);
	for (int i = 0; i < consumer_count; ++i) {
	int weight;
	cin >> weight;
	consumers[i].set_id('A' + i);
	consumers[i].set_weight(weight);
	}

	for (int i = 0; i < TOTAL_MESSAGE_COUNT; ++i) {
	distribute(consumers, i);
	}

	for (int i = 0; i < consumer_count; ++i) {
	consumers[i].display_consumed_messages();
	cout << endl;
	}

	return 0;
	}
	7 3 8 2 1 4 3 2
	A: 139
	6 22 24 36 43 70 72 78 91 97 119 123 129 145 164
	165 173 185 198 199 200 203 209 210 212 216 235 237 241 246
	259 283 284 285 286 287 295 301 302 328 330 333 339 340 347
	369 373 375 376 379 388 391 395 409 422 430 433 434 442 470
	480 481 490 509 513 514 520 524 531 533 539 548 549 550 557
	569 574 579 605 616 617 619 621 629 636 640 645 649 650 665
	666 667 672 685 688 701 705 715 722 725 732 739 741 749 751
	767 789 796 807 812 813 814 817 819 830 843 844 855 856 864
	866 868 869 871 885 887 892 901 918 924 926 929 938 941 949
	960 976 985 986

	B: 341
	0 3 4 7 9 11 12 15 17 20 21 29 32 37 38
	39 40 41 42 45 52 56 58 62 63 65 66 67 73 83
	85 89 93 94 95 96 99 103 105 110 111 113 118 120 126
	128 131 135 136 137 138 139 141 143 146 147 148 151 153 154
	156 160 161 163 166 167 169 170 172 178 179 184 188 190 191
	193 195 197 201 206 208 211 217 218 219 232 239 240 242 243
	244 245 250 254 255 256 257 258 260 262 265 266 269 271 272
	273 274 277 278 279 282 290 292 293 297 305 308 309 311 314
	316 317 319 320 321 322 323 325 329 335 337 350 352 358 359
	361 364 367 368 374 377 378 380 382 387 393 394 399 401 403
	404 406 411 412 415 424 432 435 438 439 440 441 445 446 452
	457 461 465 466 467 473 477 478 479 485 489 491 492 496 497
	507 511 515 517 518 521 526 530 534 535 540 541 542 544 556
	561 566 568 570 580 584 585 587 595 600 604 609 622 623 625
	627 628 634 635 638 641 642 643 644 646 647 653 656 658 660
	661 663 676 677 680 681 684 692 693 699 702 703 704 709 717
	720 721 723 724 729 731 740 742 744 746 748 755 756 757 759
	760 764 768 769 772 773 774 777 779 780 782 785 786 790 792
	793 794 795 797 798 800 802 805 816 821 822 823 824 828 833
	835 839 840 841 847 849 851 854 857 859 862 873 874 876 878
	893 895 896 902 905 907 908 909 910 912 913 919 922 925 928
	931 936 939 943 947 953 957 958 959 962 967 968 969 970 971
	974 975 978 980 981 984 988 991 992 993 996

	C: 99
	14 16 25 57 60 61 64 68 69 112 121 158 159 177 186
	187 196 222 230 231 252 268 270 275 280 298 318 343 353 354
	381 383 398 405 423 428 429 436 443 447 449 459 460 462 464
	471 483 500 506 510 523 554 578 581 583 592 601 608 611 613
	614 620 624 648 652 654 657 662 664 670 675 682 690 691 695
	696 698 708 712 716 735 737 753 765 787 827 848 879 883 890
	894 904 906 916 930 934 964 979 994

	D: 55
	35 50 76 80 84 101 117 144 213 215 247 248 288 300 304
	349 363 372 396 397 400 408 410 419 474 475 484 522 525 527
	536 545 546 552 589 591 598 639 673 689 711 714 775 788 791
	810 837 838 850 889 921 935 948 973 999

	E: 194
	8 10 19 27 28 31 34 44 46 51 53 59 71 77 81
	82 88 90 92 100 106 107 114 115 122 124 130 140 149 152
	157 162 171 174 183 192 194 202 220 225 226 227 228 229 233
	234 236 238 249 251 253 263 264 267 276 294 296 303 307 310
	312 313 315 326 338 342 344 345 356 360 362 365 366 384 390
	392 414 417 421 426 427 451 453 454 456 463 468 469 472 487
	493 494 498 501 503 504 508 529 538 553 555 558 559 563 564
	565 567 571 572 582 590 596 597 599 602 603 606 610 612 615
	618 626 630 631 632 637 655 671 678 686 697 700 706 707 718
	719 726 727 728 733 734 745 750 761 762 763 770 778 781 784
	803 809 811 815 818 825 829 834 836 842 846 852 860 861 863
	865 870 872 875 877 880 881 882 884 897 903 911 914 917 933
	940 944 945 946 950 951 952 955 963 966 982 983 989 998

	F: 102
	1 2 13 18 23 26 30 33 47 49 54 55 75 79 86
	87 98 104 109 127 134 142 150 189 204 214 223 224 281 289
	291 306 324 331 332 334 336 348 355 371 385 389 407 413 420
	425 431 437 448 450 455 458 482 499 512 516 547 551 562 575
	577 586 607 633 651 659 668 669 679 694 710 713 738 743 747
	758 766 771 776 799 804 808 832 845 858 867 888 891 900 923
	927 932 937 942 954 956 961 972 977 990 995 997

	G: 70
	5 48 74 102 108 116 125 132 133 155 168 175 176 180 181
	182 205 207 221 261 299 327 341 346 351 357 370 386 402 416
	418 444 476 486 488 495 502 505 519 528 532 537 543 560 573
	576 588 593 594 674 683 687 730 736 752 754 783 801 806 820
	826 831 853 886 898 899 915 920 965 987
	7 3 8 2 1 4 3 2
	A: 115
	2 5 6 16 17 45 46 49 77 78 87 93 94 96 112
	128 160 169 173 201 207 225 227 232 242 244 253 258 274 284
	289 307 320 321 329 332 342 364 377 381 388 405 412 415 417
	420 436 466 481 485 488 500 503 505 520 524 529 532 548 551
	555 561 567 577 588 589 598 602 610 612 625 626 641 658 659
	663 666 672 675 679 686 689 692 712 724 735 737 740 745 755
	777 782 785 797 799 803 816 818 841 860 866 877 888 900 934
	938 948 950 953 954 962 973 993 994 996

	B: 340
	3 4 10 11 12 14 18 19 27 28 30 36 38 40 51
	52 54 58 59 61 63 66 71 74 79 81 84 88 89 91
	95 97 99 101 103 104 106 108 117 122 123 130 136 138 139
	141 143 147 150 156 157 158 161 164 166 172 175 178 183 185
	187 189 190 197 198 204 206 209 210 211 216 218 220 226 229
	230 231 235 248 252 256 259 260 265 267 268 269 273 276 279
	282 285 287 288 299 302 303 305 309 312 315 317 318 319 322
	325 326 328 331 335 339 340 346 348 349 358 359 360 361 362
	366 373 374 378 379 383 384 387 391 392 397 399 400 403 407
	408 411 421 423 427 428 432 434 437 438 443 444 447 450 452
	453 455 456 457 459 460 461 467 469 471 472 476 482 483 484
	490 492 494 496 512 519 522 525 527 531 535 539 540 544 549
	550 556 557 558 560 566 570 578 580 581 586 587 591 595 599
	600 601 604 605 609 611 613 614 616 622 623 624 628 634 635
	639 645 649 650 651 660 661 670 677 678 680 683 684 695 696
	704 705 708 710 711 713 714 717 719 721 725 728 730 736 738
	739 741 742 743 744 751 752 756 759 760 763 766 767 770 772
	773 774 775 786 788 789 790 791 794 798 801 804 805 809 811
	819 820 822 823 824 830 831 837 838 843 848 854 855 856 857
	859 861 862 863 864 868 869 870 871 876 878 884 886 891 895
	897 899 906 908 909 912 913 917 919 926 927 929 930 931 932
	936 937 940 941 942 943 944 945 946 949 957 961 971 975 976
	977 979 982 983 985 988 989 990 991 995

	C: 77
	20 31 35 42 48 50 55 57 68 76 116 121 126 132 137
	144 149 167 195 203 214 221 222 246 250 251 275 283 301 316
	341 343 353 363 376 390 414 418 424 426 448 463 473 486 508
	513 534 565 571 575 582 593 662 664 694 729 764 769 781 807
	815 817 829 835 847 851 858 881 883 890 911 916 955 965 968
	978 998

	D: 41
	8 21 56 72 119 124 146 151 155 182 199 264 298 314 327
	334 338 350 413 430 441 502 545 584 637 674 682 688 746 784
	806 821 832 873 885 918 920 922 939 947 984

	E: 188
	1 22 23 24 43 53 60 64 65 69 73 85 92 100 102
	105 109 111 125 129 133 134 135 142 148 162 163 165 170 171
	174 176 184 186 191 193 194 196 200 212 219 224 234 237 239
	240 255 261 271 277 290 292 293 294 295 324 333 336 344 345
	347 356 357 365 367 368 370 371 386 393 394 398 401 402 404
	409 429 433 435 439 445 449 454 458 464 465 468 475 477 480
	495 497 501 504 509 511 514 515 517 518 523 528 530 533 536
	542 546 547 552 564 568 573 574 583 585 627 629 630 638 640
	642 644 646 647 648 655 656 665 668 673 685 690 691 693 697
	698 700 701 703 706 709 720 722 726 733 734 748 749 753 754
	757 765 771 776 780 812 813 825 833 836 839 840 842 845 846
	852 875 879 887 892 893 896 903 905 907 910 914 925 928 933
	951 952 964 966 970 980 992 999

	F: 153
	0 7 9 15 25 26 29 32 33 39 41 44 47 62 67
	75 83 110 113 114 118 127 140 145 154 159 177 179 180 181
	188 192 202 205 213 217 223 228 236 249 254 257 262 263 266
	281 286 296 300 304 308 310 313 323 330 351 352 355 372 382
	385 389 395 396 406 410 416 419 425 431 440 470 474 478 479
	491 493 506 507 510 516 521 538 541 553 559 562 563 569 579
	590 597 603 606 615 620 621 633 636 643 653 654 657 667 669
	671 676 681 687 702 707 715 718 723 732 747 750 758 761 762
	778 779 787 792 795 796 800 814 826 827 828 834 844 850 867
	880 894 902 921 923 924 935 956 958 959 960 967 969 972 974
	981 987 997

	G: 86
	13 34 37 70 80 82 86 90 98 107 115 120 131 152 153
	168 208 215 233 238 241 243 245 247 270 272 278 280 291 297
	306 311 337 354 369 375 380 422 442 446 451 462 487 489 498
	499 526 537 543 554 572 576 592 594 596 607 608 617 618 619
	631 632 652 699 716 727 731 768 783 793 802 808 810 849 853
	865 872 874 882 889 898 901 904 915 963 986