#include <bits/stdc++.h> using namespace std; //place these includes *before* the `#define int long long` else compile error //not using <bits/extc++.h> as it compile errors on codeforces c++20 compiler #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; //BST with extra functions https://c...content-available-to-author-only...s.com/blog/entry/11080 //order_of_key - # of elements *strictly* less than given element //find_by_order - find kth largest element, k is 0 based so find_by_order(0) returns min element template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //example initialization: indexed_set<pair<long long, int>> is; //hash table (apparently faster than unordered_map): https://c...content-available-to-author-only...s.com/blog/entry/60737 //example initialization: gp_hash_table<string, long long> ht; //For point updates: either switch to policy based BST, or use sqrt decomposition struct merge_sort_tree { const int N; vector<int> arr; vector<indexed_set<pair<int,int>>> tree; merge_sort_tree(const vector<int>& a_arr) : N(a_arr.size()), arr(a_arr), tree(2 * N) { for (int i = 0, j = 1 << __lg(2 * N - 1); i < N; i++, j = (j + 1) % N + N) tree[j].insert({arr[i], i}); for (int i = N - 1; i >= 1; i--) { for(pair<int,int> e : tree[2 * i]) tree[i].insert(e); for(pair<int,int> e : tree[2 * i + 1]) tree[i].insert(e); } } int value(int v, int x) const { return tree[v].order_of_key({x, -1}); } int to_leaf(int i) const { i += 1 << __lg(2 * N - 1); return i < 2 * N ? i : 2 * (i - N); } //update index i to new_val void update(int i, int new_val) { assert(0 <= i && i < N); for(int v = (i + (1 << __lg(2 * N - 1))) % N + N; v >= 1; v >>= 1) { tree[v].erase({arr[i], i}); tree[v].insert({new_val, i}); } arr[i] = new_val; } //How many values in range [l, r) are < x? //O(log^2(n)) int query(int l, int r, int x) const { assert(0 <= l && l <= r && r <= N); int res = 0; for (l = to_leaf(l), r = to_leaf(r); l < r; l >>= 1, r >>= 1) { if (l & 1) res += value(l++, x); if (r & 1) res += value(--r, x); } return res; } }; //MUCH RANDOM!!! seed_seq seed{ (uint32_t)chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(), (uint32_t)random_device()(), (uint32_t)(uintptr_t)make_unique<char>().get(), (uint32_t)__builtin_ia32_rdtsc() }; mt19937 rng(seed); //intended types: int, unsigned, long long //returns a random number in range [l, r) template<class T> inline T get_rand(T l, T r) { assert(l < r); return uniform_int_distribution<T>(l, r - 1)(rng); } int main() { for(int test = 1; ; test++) { cout << "test: " << test << endl; int n = get_rand(1, 1000); vector<int> arr(n); for(int i = 0; i < n; i++) { arr[i] = get_rand<int>(-10, 10); } merge_sort_tree mst(arr); for(int t = 1000; t--;) { if(get_rand(1, 3) == 1) { int i = get_rand(0, n); int new_val = get_rand<int>(-10, 10); arr[i] = new_val; mst.update(i, new_val); } else {//query int l = get_rand(0, n + 1), r = get_rand(0, n + 1); if(l > r) swap(l, r); int x = get_rand<int>(-10, 10); int cnt_naive = 0; for(int i = l; i < r; i++) { cnt_naive += arr[i] < x; } assert(cnt_naive == mst.query(l, r, x)); } } } return 0; }
Standard input is empty
test: 1 test: 2 test: 3 test: 4 test: 5 test: 6 test: 7 test: 8 test: 9 test: 10 test: 11 test: 12 test: 13 test: 14 test: 15 test: 16 test: 17 test: 18 test: 19 test: 20 test: 21 test: 22 test: 23 test: 24 test: 25 test: 26 test: 27 test: 28 test: 29 test: 30 test: 31 test: 32 test: 33 test: 34 test: 35 test: 36 test: 37 test: 38 test: 39 test: 40 test: 41 test: 42 test: 43 test: 44 test: 45 test: 46 test: 47 test: 48 test: 49 test: 50 test: 51 test: 52 test: 53 test: 54 test: 55 test: 56 test: 57 test: 58 test: 59 test: 60 test: 61 test: 62 test: 63 test: 64 test: 65 test: 66 test: 67 test: 68 test: 69 test: 70 test: 71 test: 72 test: 73 test: 74 test: 75 test: 76 test: 77 test: 78 test: 79 test: 80 test: 81 test: 82 test: 83 test: 84 test: 85 test: 86 test: 87 test: 88 test: 89 test: 90 test: 91 test: 92 test: 93 test: 94 test: 95 test: 96 test: 97 test: 98 test: 99 test: 100 test: 101 test: 102 test: 103 test: 104 test: 105 test: 106 test: 107 test: 108 test: 109 test: 110 test: 111 test: 112 test: 113 test: 114 test: 115 test: 116 test: 117 test: 118 test: 119 test: 120 test: 121 test: 122 test: 123 test: 124 test: 125 test: 126 test: 127 test: 128 test: 129 test: 130 test: 131 test: 132 test: 133 test: 134 test: 135 test: 136 test: 137 test: 138 test: 139 test: 140 test: 141 test: 142 test: 143 test: 144 test: 145 test: 146 test: 147 test: 148 test: 149 test: 150 test: 151 test: 152 test: 153 test: 154 test: 155 test: 156 test: 157 test: 158 test: 159 test: 160 test: 161 test: 162 test: 163 test: 164 test: 165 test: 166 test: 167 test: 168 test: 169 test: 170 test: 171 test: 172 test: 173 test: 174 test: 175 test: 176 test: 177 test: 178 test: 179 test: 180 test: 181 test: 182 test: 183 test: 184 test: 185 test: 186 test: 187 test: 188 test: 189 test: 190 test: 191 test: 192 test: 193 test: 194 test: 195 test: 196 test: 197 test: 198 test: 199 test: 200 test: 201 test: 202 test: 203 test: 204 test: 205 test: 206 test: 207 test: 208 test: 209 test: 210 test: 211 test: 212 test: 213 test: 214 test: 215 test: 216 test: 217 test: 218 test: 219 test: 220 test: 221 test: 222 test: 223 test: 224 test: 225 test: 226 test: 227 test: 228 test: 229 test: 230 test: 231 test: 232 test: 233 test: 234 test: 235 test: 236 test: 237 test: 238 test: 239 test: 240 test: 241 test: 242 test: 243 test: 244 test: 245 test: 246 test: 247 test: 248 test: 249 test: 250 test: 251 test: 252 test: 253 test: 254 test: 255 test: 256 test: 257 test: 258 test: 259 test: 260 test: 261 test: 262 test: 263 test: 264 test: 265 test: 266 test: 267 test: 268 test: 269 test: 270 test: 271 test: 272 test: 273 test: 274 test: 275 test: 276 test: 277 test: 278 test: 279 test: 280 test: 281 test: 282 test: 283 test: 284 test: 285 test: 286 test: 287 test: 288 test: 289 test: 290 test: 291 test: 292 test: 293 test: 294 test: 295 test: 296 test: 297 test: 298 test: 299 test: 300 test: 301 test: 302 test: 303 test: 304 test: 305 test: 306 test: 307 test: 308 test: 309 test: 310 test: 311 test: 312 test: 313 test: 314 test: 315 test: 316 test: 317 test: 318 test: 319 test: 320 test: 321 test: 322 test: 323 test: 324 test: 325 test: 326 test: 327 test: 328 test: 329 test: 330 test: 331 test: 332 test: 333 test: 334 test: 335 test: 336 test: 337 test: 338 test: 339 test: 340 test: 341 test: 342 test: 343 test: 344 test: 345 test: 346 test: 347 test: 348 test: 349 test: 350 test: 351 test: 352 test: 353 test: 354 test: 355 test: 356 test: 357 test: 358 test: 359 test: 360 test: 361 test: 362 test: 363 test: 364 test: 365 test: 366 test: 367 test: 368 test: 369 test: 370 test: 371 test: 372 test: 373 test: 374 test: 375 test: 376 test: 377 test: 378 test: 379 test: 380 test: 381 test: 382 test: 383 test: 384 test: 385 test: 386 test: 387 test: 388 test: 389 test: 390 test: 391 test: 392 test: 393 test: 394 test: 395 test: 396 test: 397 test: 398 test: 399 test: 400 test: 401 test: 402 test: 403 test: 404 test: 405 test: 406 test: 407 test: 408 test: 409 test: 410 test: 411 test: 412 test: 413 test: 414 test: 415 test: 416 test: 417 test: 418 test: 419 test: 420 test: 421 test: 422 test: 423 test: 424 test: 425 test: 426 test: 427 test: 428 test: 429 test: 430 test: 431 test: 432 test: 433 test: 434 test: 435 test: 436 test: 437 test: 438 test: 439 test: 440 test: 441 test: 442 test: 443 test: 444 test: 445 test: 446 test: 447 test: 448 test: 449 test: 450 test: 451 test: 452 test: 453 test: 454 test: 455 test: 456 test: 457 test: 458 test: 459 test: 460 test: 461 test: 462 test: 463 test: 464 test: 465 test: 466 test: 467 test: 468 test: 469 test: 470 test: 471 test: 472 test: 473 test: 474 test: 475 test: 476 test: 477 test: 478 test: 479 test: 480 test: 481 test: 482 test: 483 test: 484 test: 485 test: 486 test: 487 test: 488 test: 489 test: 490 test: 491 test: 492 test: 493 test: 494 test: 495 test: 496 test: 497 test: 498 test: 499 test: 500 test: 501 test: 502 test: 503 test: 504 test: 505 test: 506 test: 507 test: 508 test: 509 test: 510 test: 511 test: 512 test: 513 test: 514 test: 515 test: 516 test: 517 test: 518 test: 519 test: 520 test: 521 test: 522 test: 523 test: 524 test: 525 test: 526 test: 527 test: 528 test: 529 test: 530 test: 531 test: 532 test: 533 test: 534 test: 535 test: 536 test: 537 test: 538 test: 539 test: 540 test: 541 test: 542 test: 543 test: 544 test: 545 test: 546 test: 547 test: 548 test: 549 test: 550 test: 551 test: 552 test: 553 test: 554 test: 555 test: 556 test: 557 test: 558 test: 559 test: 560 test: 561 test: 562 test: 563 test: 564 test: 565 test: 566 test: 567 test: 568 test: 569 test: 570 test: 571 test: 572 test: 573 test: 574 test: 575 test: 576 test: 577 test: 578 test: 579 test: 580 test: 581 test: 582 test: 583 test: 584 test: 585 test: 586 test: 587 test: 588 test: 589 test: 590 test: 591 test: 592 test: 593 test: 594 test: 595 test: 596 test: 597 test: 598 test: 599 test: 600 test: 601 test: 602 test: 603 test: 604 test: 605 test: 606 test: 607 test: 608 test: 609 test: 610 test: 611 test: 612 test: 613 test: 614 test: 615 test: 616 test: 617 test: 618 test: 619 test: 620 test: 621 test: 622 test: 623 test: 624 test: 625 test: 626 test: 627 test: 628 test: 629 test: 630 test: 631 test: 632 test: 633 test: 634 test: 635 test: 636 test: 637 test: 638 test: 639 test: 640 test: 641 test: 642 test: 643 test: 644 test: 645 test: 646 test: 647 test: 648 test: 649 test: 650 test: 651 test: 652 test: 653 test: 654 test: 655 test: 656 test: 657 test: 658 test: 659 test: 660 test: 661 test: 662 test: 663 test: 664 test: 665 test: 666 test: 667 test: 668 test: 669 test: 670 test: 671 test: 672 test: 673 test: 674 test: 675 test: 676 test: 677 test: 678 test: 679 test: 680 test: 681 test: 682 test: 683 test: 684 test: 685 test: 686 test: 687 test: 688 test: 689 test: 690 test: 691 test: 692 test: 693 test: 694 test: 695 test: 696 test: 697 test: 698 test: 699 test: 700 test: 701 test: 702 test: 703 test: 704 test: 705 test: 706 test: 707 test: 708 test: 709 test: 710 test: 711 test: 712 test: 713 test: 714 test: 715 test: 716 test: 717 test: 718 test: 719 test: 720 test: 721 test: 722 test: 723 test: 724 test: 725 test: 726 test: 727 test: 728 test: 729 test: 730 test: 731 test: 732 test: 733 test: 734 test: 735 test: 736 test: 737 test: 738 test: 739 test: 740 test: 741 test: 742 test: 743 test: 744 test: 745 test: 746 test: 747 test: 748 test: 749 test: 750 test: 751 test: 752 test: 753 test: 754 test: 755 test: 756 test: 757 test: 758 test: 759 test: 760 test: 761 test: 762 test: 763 test: 764 test: 765 test: 766 test: 767 test: 768 test: 769 test: 770 test: 771 test: 772 test: 773 test: 774 test: 775 test: 776 test: 777 test: 778 test: 779 test: 780 test: 781 test: 782 test: 783 test: 784 test: 785 test: 786 test: 787 test: 788 test: 789 test: 790 test: 791 test: 792 test: 793 test: 794 test: 795 test: 796 test: 797 test: 798 test: 799 test: 800 test: 801 test: 802 test: 803 test: 804 test: 805 test: 806 test: 807 test: 808 test: 809 test: 810 test: 811 test: 812 test: 813 test: 814 test: 815 test: 816 test: 817 test: 818 test: 819 test: 820 test: 821 test: 822 test: 823 test: 824 test: 825 test: 826 test: 827 test: 828 test: 829 test: 830 test: 831 test: 832 test: 833 test: 834 test: 835 test: 836 test: 837 test: 838 test: 839 test: 840 test: 841 test: 842 test: 843 test: 844 test: 845 test: 846 test: 847 test: 848 test: 849 test: 850 test: 851 test: 852 test: 853 test: 854 test: 855 test: 856 test: 857 test: 858 test: 859 test: 860 test: 861 test: 862 test: 863 test: 864 test: 865 test: 866 test: 867 test: 868 test: 869 test: 870 test: 871 test: 872 test: 873 test: 874 test: 875 test: 876 test: 877 test: 878 test: 879 test: 880 test: 881 test: 882 test: 883 test: 884 test: 885 test: 886 test: 887 test: 888 test: 889 test: 890 test: 891 test: 892 test: 893 test: 894 test: 895 test: 896 test: 897 test: 898 test: 899 test: 900 test: 901 test: 902 test: 903 test: 904 test: 905 test: 906 test: 907 test: 908 test: 909 test: 910 test: 911 test: 912 test: 913 test: 914 test: 915 test: 916 test: 917 test: 918 test: 919 test: 920 test: 921 test: 922 test: 923 test: 924 test: 925 test: 926 test: 927 test: 928 test: 929 test: 930 test: 931 test: 932 test: 933 test: 934 test: 935 test: 936 test: 937 test: 938 test: 939 test: 940 test: 941 test: 942 test: 943 test: 944 test: 945 test: 946 test: 947 test: 948 test: 949 test: 950 test: 951 test: 952 test: 953 test: 954 test: 955 test: 956 test: 957 test: 958 test: 959 test: 960 test: 961 test: 962 test: 963 test: 964 test: 965 test: 966 test: 967 test: 968 test: 969 test: 970 test: 971 test: 972 test: 973 test: 974 test: 975 test: 976 test: 977 test: 978 test: 979 test: 980 test: 981 test: 982 test: 983 test: 984 test: 985 test: 986 test: 987 test: 988 test: 989 test: 990 test: 991 test: 992 test: 993 test: 994 test: 995 test: 996 test: 997 test: 998 test: 999 test: 1000 test: 1001 test: 1002 test: 1003 test: 1004 test: 1005 test: 1006 test: 1007 test: 1008 test: 1009 test: 1010 test: 1011 test: 1012 test: 1013 test: 1014 test: 1015 test: 1016 test: 1017 test: 1018 test: 1019 test: 1020 test: 1021 test: 1022 test: 1023 test: 1024 test: 1025 test: 1026 test: 1027 test: 1028 test: 1029 test: 1030 test: 1031 test: 1032 test: 1033 test: 1034 test: 1035 test: 1036 test: 1037 test: 1038 test: 1039 test: 1040 test: 1041 test: 1042 test: 1043 test: 1044 test: 1045 test: 1046 test: 1047 test: 1048 test: 1049 test: 1050 test: 1051 test: 1052 test: 1053 test: 1054 test: 1055 test: 1056 test: 1057 test: 1058 test: 1059 test: 1060 test: 1061 test: 1062 test: 1063 test: 1064 test: 1065 test: 1066 test: 1067 test: 1068 test: 1069 test: 1070 test: 1071 test: 1072 test: 1073 test: 1074 test: 1075 test: 1076 test: 1077 test: 1078 test: 1079 test: 1080 test: 1081 test: 1082 test: 1083 test: 1084 test: 1085 test: 1086 test: 1087 test: 1088 test: 1089 test: 1090 test: 1091 test: 1092 test: 1093 test: 1094 test: 1095 test: 1096 test: 1097 test: 1098 test: 1099 test: 1100 test: 1101 test: 1102 test: 1103 test: 1104 test: 1105 test: 1106 test: 1107 test: 1108 test: 1109 test: 1110 test: 1111 test: 1112 test: 1113 test: 1114 test: 1115 test: 1116 test: 1117 test: 1118 test: 1119 test: 1120 test: 1121 test: 1122 test: 1123 test: 1124 test: 1125 test: 1126 test: 1127 test: 1128 test: 1129 test: 1130 test: 1131 test: 1132 test: 1133 test: 1134 test: 1135 test: 1136 test: 1137 test: 1138 test: 1139 test: 1140 test: 1141 test: 1142 test: 1143 test: 1144 test: 1145 test: 1146 test: 1147 test: 1148 test: 1149 test: 1150 test: 1151 test: 1152 test: 1153 test: 1154 test: 1155 test: 1156 test: 1157 test: 1158 test: 1159 test: 1160 test: 1161 test: 1162 test: 1163 test: 1164 test: 1165 test: 1166 test: 1167 test: 1168 test: 1169 test: 1170 test: 1171 test: 1172 test: 1173 test: 1174 test: 1175 test: 1176 test: 1177 test: 1178 test: 1179 test: 1180 test: 1181 test: 1182 test: 1183 test: 1184 test: 1185 test: 1186 test: 1187 test: 1188 test: 1189 test: 1190 test: 1191 test: 1192 test: 1193 test: 1194 test: 1195 test: 1196 test: 1197 test: 1198 test: 1199 test: 1200 test: 1201 test: 1202 test: 1203 test: 1204 test: 1205 test: 1206 test: 1207 test: 1208 test: 1209 test: 1210 test: 1211 test: 1212 test: 1213 test: 1214 test: 1215 test: 1216 test: 1217 test: 1218 test: 1219 test: 1220 test: 1221 test: 1222 test: 1223 test: 1224 test: 1225 test: 1226 test: 1227 test: 1228 test: 1229 test: 1230 test: 1231 test: 1232 test: 1233 test: 1234 test: 1235 test: 1236 test: 1237 test: 1238 test: 1239 test: 1240 test: 1241 test: 1242 test: 1243 test: 1244 test: 1245 test: 1246 test: 1247 test: 1248 test: 1249 test: 1250 test: 1251 test: 1252 test: 1253 test: 1254 test: 1255 test: 1256 test: 1257 test: 1258 test: 1259 test: 1260 test: 1261 test: 1262 test: 1263 test: 1264 test: 1265 test: 1266 test: 1267 test: 1268 test: 1269 test: 1270 test: 1271 test: 1272 test: 1273 test: 1274 test: 1275 test: 1276 test: 1277 test: 1278 test: 1279 test: 1280 test: 1281 test: 1282 test: 1283 test: 1284 test: 1285 test: 1286 test: 1287 test: 1288 test: 1289 test: 1290 test: 1291 test: 1292 test: 1293 test: 1294 test: 1295 test: 1296 test: 1297 test: 1298 test: 1299 test: 1300 test: 1301 test: 1302 test: 1303 test: 1304 test: 1305 test: 1306 test: 1307 test: 1308 test: 1309 test: 1310 test: 1311 test: 1312 test: 1313 test: 1314 test: 1315 test: 1316 test: 1317 test: 1318 test: 1319 test: 1320 test: 1321 test: 1322 test: 1323 test: 1324 test: 1325 test: 1326 test: 1327 test: 1328 test: 1329 test: 1330 test: 1331 test: 1332 test: 1333 test: 1334 test: 1335 test: 1336 test: 1337 test: 1338 test: 1339 test: 1340 test: 1341 test: 1342 test: 1343 test: 1344 test: 1345 test: 1346 test: 1347 test: 1348 test: 1349 test: 1350 test: 1351 test: 1352 test: 1353 test: 1354 test: 1355 test: 1356 test: 1357 test: 1358 test: 1359 test: 1360 test: 1361 test: 1362 test: 1363 test: 1364 test: 1365 test: 1366 test: 1367 test: 1368 test: 1369 test: 1370 test: 1371 test: 1372 test: 1373 test: 1374 test: 1375 test: 1376 test: 1377 test: 1378 test: 1379 test: 1380 test: 1381 test: 1382 test: 1383 test: 1384 test: 1385 test: 1386 test: 1387 test: 1388 test: 1389 test: 1390 test: 1391 test: 1392 test: 1393 test: 1394 test: 1395 test: 1396 test: 1397 test: 1398 test: 1399 test: 1400 test: 1401 test: 1402 test: 1403 test: 1404 test: 1405 test: 1406 test: 1407 test: 1408 test: 1409 test: 1410 test: 1411 test: 1412 test: 1413 test: 1414 test: 1415 test: 1416 test: 1417 test: 1418 test: 1419 test: 1420 test: 1421 test: 1422 test: 1423 test: 1424 test: 1425 test: 1426 test: 1427 test: 1428 test: 1429 test: 1430 test: 1431 test: 1432 test: 1433 test: 1434 test: 1435 test: 1436 test: 1437 test: 1438 test: 1439 test: 1440 test: 1441 test: 1442 test: 1443 test: 1444 test: 1445 test: 1446 test: 1447 test: 1448 test: 1449 test: 1450 test: 1451 test: 1452 test: 1453 test: 1454 test: 1455 test: 1456 test: 1457 test: 1458 test: 1459 test: 1460 test: 1461 test: 1462 test: 1463 test: 1464 test: 1465 test: 1466 test: 1467 test: 1468 test: 1469 test: 1470 test: 1471 test: 1472 test: 1473 test: 1474 test: 1475 test: 1476 test: 1477 test: 1478 test: 1479 test: 1480 test: 1481 test: 1482 test: 1483 test: 1484 test: 1485 test: 1486 test: 1487 test: 1488 test: 1489 test: 1490 test: 1491 test: 1492 test: 1493 test: 1494 test: 1495 test: 1496 test: 1497 test: 1498 test: 1499 test: 1500 test: 1501 test: 1502 test: 1503 test: 1504 test: 1505 test: 1506 test: 1507 test: 1508 test: 1509 test: 1510 test: 1511 test: 1512 test: 1513 test: 1514 test: 1515 test: 1516 test: 1517 test: 1518 test: 1519 test: 1520 test: 1521 test: 1522 test: 1523 test: 1524 test: 1525 test: 1526 test: 1527 test: 1528 test: 1529 test: 1530 test: 1531 test: 1532 test: 1533 test: 1534 test: 1535 test: 1536 test: 1537 test: 1538 test: 1539 test: 1540 test: 1541 test: 1542 test: 1543 test: 1544 test: 1545 test: 1546 test: 1547 test: 1548 test: 1549 test: 1550 test: 1551 test: 1552 test: 1553 test: 1554 test: 1555 test: 1556 test: 1557 test: 1558 test: 1559 test: 1560 test: 1561 test: 1562 test: 1563 test: 1564 test: 1565 test: 1566 test: 1567 test: 1568 test: 1569 test: 1570 test: 1571 test: 1572 test: 1573 test: 1574 test: 1575 test: 1576 test: 1577 test: 1578 test: 1579 test: 1580 test: 1581 test: 1582 test: 1583 test: 1584 test: 1585 test: 1586 test: 1587 test: 1588 test: 1589 test: 1590 test: 1591 test: 1592 test: 1593 test: 1594 test: 1595 test: 1596 test: 1597 test: 1598 test: 1599 test: 1600 test: 1601 test: 1602 test: 1603 test: 1604 test: 1605 test: 1606 test: 1607 test: 1608 test: 1609 test: 1610 test: 1611 test: 1612 test: 1613 test: 1614 test: 1615 test: 1616 test: 1617 test: 1618 test: 1619 test: 1620 test: 1621 test: 1622 test: 1623 test: 1624 test: 1625 test: 1626 test: 1627 test: 1628 test: 1629 test: 1630 test: 1631 test: 1632 test: 1633 test: 1634 test: 1635 test: 1636 test: 1637 test: 1638 test: 1639 test: 1640 test: 1641 test: 1642 test: 1643 test: 1644 test: 1645 test: 1646 test: 1647 test: 1648 test: 1649 test: 1650 test: 1651 test: 1652 test: 1653 test: 1654 test: 1655 test: 1656 test: 1657 test: 1658 test: 1659 test: 1660 test: 1661 test: 1662 test: 1663 test: 1664 test: 1665 test: 1666 test: 1667 test: 1668 test: 1669 test: 1670 test: 1671 test: 1672 test: 1673 test: 1674 test: 1675 test: 1676 test: 1677 test: 1678 test: 1679 test: 1680 test: 1681 test: 1682 test: 1683 test: 1684 test: 1685 test: 1686 test: 1687 test: 1688 test: 1689 test: 1690 test: 1691 test: 1692 test: 1693 test: 1694 test: 1695 test: 1696 test: 1697 test: 1698 test: 1699 test: 1700 test: 1701 test: 1702 test: 1703 test: 1704 test: 1705 test: 1706 test: 1707 test: 1708 test: 1709 test: 1710 test: 1711 test: 1712 test: 1713 test: 1714 test: 1715 test: 1716 test: 1717 test: 1718 test: 1719 test: 1720 test: 1721 test: 1722 test: 1723 test: 1724 test: 1725 test: 1726 test: 1727 test: 1728 test: 1729 test: 1730 test: 1731 test: 1732 test: 1733 test: 1734 test: 1735 test: 1736 test: 1737 test: 1738 test: 1739 test: 1740 test: 1741 test: 1742 test: 1743 test: 1744 test: 1745 test: 1746 test: 1747 test: 1748 test: 1749 test: 1750 test: 1751 test: 1752 test: 1753 test: 1754 test: 1755 test: 1756 test: 1757 test: 1758 test: 1759 test: 1760 test: 1761 test: 1762 test: 1763 test: 1764 test: 1765 test: 1766 test: 1767 test: 1768 test: 1769 test: 1770 test: 1771 test: 1772 test: 1773 test: 1774 test: 1775 test: 1776 test: 1777 test: 1778 test: 1779 test: 1780 test: 1781 test: 1782 test: 1783 test: 1784 test: 1785 test: 1786 test: 1787 test: 1788 test: 1789 test: 1790 test: 1791 test: 1792 test: 1793 test: 1794 test: 1795 test: 1796 test: 1797 test: 1798 test: 1799 test: 1800 test: 1801 test: 1802 test: 1803 test: 1804 test: 1805 test: 1806 test: 1807 test: 1808 test: 1809 test: 1810 test: 1811 test: 1812 test: 1813 test: 1814 test: 1815 test: 1816 test: 1817 test: 1818 test: 1819 test: 1820 test: 1821 test: 1822 test: 1823 test: 1824 test: 1825 test: 1826 test: 1827 test: 1828 test: 1829 test: 1830 test: 1831 test: 1832 test: 1833 test: 1834 test: 1835 test: 1836 test: 1837 test: 1838 test: 1839 test: 1840 test: 1841 test: 1842 test: 1843 test: 1844 test: 1845 test: 1846 test: 1847 test: 1848 test: 1849 test: 1850 test: 1851 test: 1852 test: 1853 test: 1854 test: 1855 test: 1856 test: 1857 test: 1858 test: 1859 test: 1860 test: 1861 test: 1862 test: 1863 test: 1864 test: 1865 test: 1866 test: 1867 test: 1868 test: 1869 test: 1870 test: 1871 test: 1872 test: 1873 test: 1874 test: 1875 test: 1876 test: 1877 test: 1878 test: 1879 test: 1880 test: 1881 test: 1882 test: 1883 test: 1884 test: 1885 test: 1886 test: 1887 test: 1888 test: 1889 test: 1890 test: 1891 test: 1892 test: 1893 test: 1894 test: 1895 test: 1896 test: 1897 test: 1898 test: 1899 test: 1900 test: 1901 test: 1902 test: 1903 test: 1904 test: 1905 test: 1906 test: 1907 test: 1908 test: 1909 test: 1910 test: 1911 test: 1912 test: 1913 test: 1914 test: 1915 test: 1916 test: 1917 test: 1918 test: 1919 test: 1920 test: 1921 test: 1922 test: 1923 test: 1924 test: 1925 test: 1926 test: 1927 test: 1928 test: 1929 test: 1930 test: 1931 test: 1932 test: 1933 test: 1934 test: 1935 test: 1936 test: 1937 test: 1938 test: 1939 test: 1940 test: 1941 test: 1942 test: 1943 test: 1944 test: 1945 test: 1946 test: 1947 test: 1948 test: 1949 test: 1950 test: 1951 test: 1952 test: 1953 test: 1954 test: 1955 test: 1956 test: 1957 test: 1958 test: 1959 test: 1960 test: 1961 test: 1962 test: 1963 test: 1964 test: 1965 test: 1966 test: 1967 test: 1968 test: 1969 test: 1970 test: 1971 test: 1972 test: 1973 test: 1974 test: 1975 test: 1976 test: 1977 test: 1978 test: 1979 test: 1980 test: 1981 test: 1982 test: 1983 test: 1984 test: 1985 test: 1986 test: 1987 test: 1988 test: 1989 test: 1990 test: 1991 test: 1992 test: 1993 test: 1994 test: 1995 test: 1996 test: 1997 test: 1998 test: 1999 test: 2000 test: 2001 test: 2002 test: 2003 test: 2004 test: 2005 test: 2006 test: 2007 test: 2008 test: 2009