結果

問題 No.262 面白くないビットすごろく
ユーザー 👑 rin204rin204
提出日時 2022-11-03 16:30:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 504 ms / 2,000 ms
コード長 27,338 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 87,120 KB
実行使用メモリ 76,032 KB
最終ジャッジ日時 2023-09-25 01:09:59
合計ジャッジ時間 2,180 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
71,420 KB
testcase_01 AC 504 ms
76,032 KB
testcase_02 AC 235 ms
75,892 KB
testcase_03 AC 499 ms
76,028 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_right

def popcount(n):
    n = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
    n = (n & 0x0f0f0f0f0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f0f0f0f0f)
    n = (n & 0x00ff00ff00ff00ff) + ((n >> 8) & 0x00ff00ff00ff00ff)
    n = (n & 0x0000ffff0000ffff) + ((n >> 16) & 0x0000ffff0000ffff)
    n = (n & 0x00000000ffffffff) + ((n >> 32) & 0x00000000ffffffff)
    return n

A = [1, 1000000012, 2000000010, 3000000003, 4000000010, 5000000018, 6000000012, 7000000003, 8000000003, 9000000012, 10000000003, 11000000010, 12000000010, 13000000018, 14000000012, 15000000010, 16000000004, 17000000003, 18000000018, 19000000004, 20000000012, 21000000012, 22000000003, 23000000011, 24000000010, 25000000020, 26000000003, 27000000011, 28000000010, 29000000012, 30000000003, 31000000007, 32000000008, 33000000020, 34000000004, 35000000003, 36000000003, 37000000020, 38000000018, 39000000018, 40000000010, 41000000010, 42000000010, 43000000004, 44000000004, 45000000012, 46000000010, 47000000010, 48000000003, 49000000003, 50000000003, 51000000008, 52000000012, 53000000010, 54000000010, 55000000011, 56000000010, 57000000012, 58000000018, 59000000003, 60000000004, 61000000012, 62000000008, 63000000004, 64000000001, 65000000012, 66000000003, 67000000003, 68000000018, 69000000012, 70000000012, 71000000011, 72000000012, 73000000003, 74000000003, 75000000010, 76000000001, 77000000020, 78000000003, 79000000003, 80000000010, 81000000007, 82000000010, 83000000020, 84000000010, 85000000012, 86000000018, 87000000003, 88000000008, 89000000012, 90000000010, 91000000003, 92000000010, 93000000009, 94000000003, 95000000003, 96000000004, 97000000010, 98000000012, 99000000010, 100000000004, 101000000003, 102000000008, 103000000020, 104000000010, 105000000003, 106000000010, 107000000003, 108000000010, 109000000012, 110000000010, 111000000010, 112000000003, 113000000020, 114000000018, 115000000010, 116000000003, 117000000013, 118000000004, 119000000007, 120000000008, 121000000010, 122000000010, 123000000003, 124000000008, 125000000012, 126000000008, 127000000010, 128000000013, 129000000022, 130000000010, 131000000010, 132000000004, 133000000008, 134000000004, 135000000010, 136000000007, 137000000020, 138000000018, 139000000010, 140000000010, 141000000016, 142000000010, 143000000003, 144000000010, 145000000012, 146000000004, 147000000004, 148000000004, 149000000012, 150000000003, 151000000003, 152000000013, 153000000003, 154000000003, 155000000011, 156000000012, 157000000009, 158000000012, 159000000011, 160000000003, 161000000010, 162000000008, 163000000020, 164000000003, 165000000012, 166000000001, 167000000012, 168000000003, 169000000012, 170000000010, 171000000003, 172000000001, 173000000003, 174000000012, 175000000010, 176000000001, 177000000012, 178000000010, 179000000020, 180000000010, 181000000003, 182000000012, 183000000003, 184000000003, 185000000020, 186000000012, 187000000011, 188000000004, 189000000012, 190000000004, 191000000004, 192000000008, 193000000022, 194000000010, 195000000008, 196000000010, 197000000013, 198000000003, 199000000010, 200000000008, 201000000010, 202000000012, 203000000006, 204000000007, 205000000001, 206000000001, 207000000003, 208000000010, 209000000003, 210000000004, 211000000011, 212000000003, 213000000010, 214000000004, 215000000020, 216000000003, 217000000010, 218000000018, 219000000001, 220000000010, 221000000012, 222000000003, 223000000008, 224000000004, 225000000012, 226000000003, 227000000010, 228000000001, 229000000003, 230000000003, 231000000010, 232000000012, 233000000007, 234000000007, 235000000001, 236000000008, 237000000010, 238000000008, 239000000010, 240000000001, 241000000012, 242000000010, 243000000001, 244000000010, 245000000012, 246000000004, 247000000010, 248000000017, 249000000007, 250000000010, 251000000011, 252000000001, 253000000021, 254000000003, 255000000008, 256000000008, 257000000022, 258000000008, 259000000004, 260000000010, 261000000013, 262000000010, 263000000010, 264000000008, 265000000006, 266000000008, 267000000003, 268000000008, 269000000010, 270000000003, 271000000007, 272000000008, 273000000010, 274000000021, 275000000010, 276000000003, 277000000020, 278000000010, 279000000010, 280000000010, 281000000012, 282000000012, 283000000010, 284000000010, 285000000010, 286000000004, 287000000011, 288000000010, 289000000010, 290000000010, 291000000003, 292000000018, 293000000018, 294000000018, 295000000012, 296000000008, 297000000012, 298000000010, 299000000006, 300000000004, 301000000020, 302000000012, 303000000011, 304000000008, 305000000010, 306000000004, 307000000003, 308000000004, 309000000013, 310000000010, 311000000011, 312000000010, 313000000003, 314000000012, 315000000004, 316000000010, 317000000010, 318000000010, 319000000010, 320000000004, 321000000003, 322000000010, 323000000003, 324000000020, 325000000020, 326000000001, 327000000018, 328000000004, 329000000012, 330000000010, 331000000011, 332000000008, 333000000003, 334000000018, 335000000008, 336000000004, 337000000020, 338000000018, 339000000007, 340000000010, 341000000003, 342000000004, 343000000012, 344000000013, 345000000010, 346000000012, 347000000004, 348000000010, 349000000012, 350000000010, 351000000020, 352000000013, 353000000018, 354000000010, 355000000003, 356000000010, 357000000013, 358000000001, 359000000011, 360000000003, 361000000010, 362000000012, 363000000010, 364000000010, 365000000010, 366000000004, 367000000006, 368000000004, 369000000003, 370000000021, 371000000003, 372000000008, 373000000012, 374000000010, 375000000008, 376000000008, 377000000008, 378000000018, 379000000010, 380000000008, 381000000009, 382000000008, 383000000010, 384000000001, 385000000003, 386000000008, 387000000008, 388000000003, 389000000020, 390000000008, 391000000010, 392000000010, 393000000018, 394000000007, 395000000007, 396000000004, 397000000020, 398000000010, 399000000010, 400000000001, 401000000007, 402000000010, 403000000008, 404000000010, 405000000003, 406000000001, 407000000003, 408000000001, 409000000020, 410000000013, 411000000003, 412000000008, 413000000010, 414000000012, 415000000007, 416000000003, 417000000003, 418000000004, 419000000010, 420000000018, 421000000003, 422000000010, 423000000003, 424000000004, 425000000007, 426000000010, 427000000001, 428000000008, 429000000012, 430000000001, 431000000010, 432000000004, 433000000003, 434000000010, 435000000011, 436000000003, 437000000007, 438000000008, 439000000010, 440000000003, 441000000007, 442000000010, 443000000004, 444000000004, 445000000012, 446000000007, 447000000010, 448000000008, 449000000010, 450000000010, 451000000010, 452000000004, 453000000013, 454000000010, 455000000010, 456000000013, 457000000003, 458000000012, 459000000003, 460000000004, 461000000006, 462000000010, 463000000007, 464000000010, 465000000012, 466000000008, 467000000008, 468000000008, 469000000012, 470000000008, 471000000012, 472000000007, 473000000020, 474000000010, 475000000003, 476000000020, 477000000012, 478000000003, 479000000008, 480000000013, 481000000020, 482000000010, 483000000010, 484000000003, 485000000012, 486000000008, 487000000003, 488000000003, 489000000007, 490000000010, 491000000003, 492000000008, 493000000012, 494000000010, 495000000011, 496000000001, 497000000003, 498000000008, 499000000008, 500000000010, 501000000012, 502000000010, 503000000003, 504000000013, 505000000003, 506000000013, 507000000010, 508000000004, 509000000010, 510000000008, 511000000020, 512000000007, 513000000020, 514000000008, 515000000020, 516000000001, 517000000007, 518000000018, 519000000020, 520000000003, 521000000010, 522000000007, 523000000006, 524000000003, 525000000010, 526000000010, 527000000007, 528000000001, 529000000007, 530000000021, 531000000004, 532000000017, 533000000010, 534000000004, 535000000010, 536000000007, 537000000020, 538000000010, 539000000017, 540000000004, 541000000007, 542000000008, 543000000007, 544000000008, 545000000010, 546000000010, 547000000008, 548000000008, 549000000020, 550000000010, 551000000012, 552000000012, 553000000012, 554000000003, 555000000010, 556000000003, 557000000010, 558000000010, 559000000003, 560000000003, 561000000010, 562000000018, 563000000010, 564000000018, 565000000003, 566000000010, 567000000011, 568000000003, 569000000003, 570000000010, 571000000003, 572000000008, 573000000010, 574000000010, 575000000003, 576000000003, 577000000020, 578000000010, 579000000020, 580000000010, 581000000010, 582000000004, 583000000010, 584000000007, 585000000020, 586000000003, 587000000004, 588000000001, 589000000018, 590000000018, 591000000010, 592000000001, 593000000010, 594000000010, 595000000010, 596000000010, 597000000001, 598000000001, 599000000020, 600000000008, 601000000012, 602000000003, 603000000003, 604000000010, 605000000012, 606000000010, 607000000010, 608000000007, 609000000003, 610000000010, 611000000011, 612000000018, 613000000012, 614000000004, 615000000003, 616000000008, 617000000010, 618000000007, 619000000010, 620000000010, 621000000003, 622000000010, 623000000010, 624000000010, 625000000010, 626000000012, 627000000020, 628000000008, 629000000010, 630000000018, 631000000012, 632000000010, 633000000020, 634000000010, 635000000004, 636000000010, 637000000012, 638000000003, 639000000004, 640000000008, 641000000022, 642000000004, 643000000020, 644000000003, 645000000007, 646000000004, 647000000011, 648000000017, 649000000003, 650000000003, 651000000001, 652000000008, 653000000003, 654000000003, 655000000003, 656000000008, 657000000012, 658000000018, 659000000007, 660000000010, 661000000022, 662000000010, 663000000003, 664000000008, 665000000012, 666000000012, 667000000010, 668000000007, 669000000010, 670000000028, 671000000007, 672000000008, 673000000003, 674000000021, 675000000010, 676000000001, 677000000012, 678000000001, 679000000012, 680000000003, 681000000012, 682000000012, 683000000001, 684000000008, 685000000020, 686000000008, 687000000004, 688000000008, 689000000020, 690000000010, 691000000004, 692000000010, 693000000003, 694000000018, 695000000010, 696000000010, 697000000012, 698000000018, 699000000020, 700000000003, 701000000009, 702000000001, 703000000010, 704000000008, 705000000003, 706000000003, 707000000001, 708000000010, 709000000020, 710000000004, 711000000010, 712000000003, 713000000003, 714000000007, 715000000003, 716000000008, 717000000020, 718000000010, 719000000008, 720000000004, 721000000014, 722000000010, 723000000010, 724000000010, 725000000020, 726000000003, 727000000010, 728000000010, 729000000020, 730000000003, 731000000001, 732000000008, 733000000010, 734000000001, 735000000004, 736000000008, 737000000012, 738000000004, 739000000004, 740000000008, 741000000010, 742000000004, 743000000010, 744000000001, 745000000008, 746000000010, 747000000008, 748000000010, 749000000010, 750000000017, 751000000006, 752000000001, 753000000020, 754000000008, 755000000020, 756000000003, 757000000012, 758000000010, 759000000007, 760000000007, 761000000003, 762000000012, 763000000010, 764000000001, 765000000010, 766000000010, 767000000010, 768000000013, 769000000022, 770000000004, 771000000004, 772000000001, 773000000008, 774000000008, 775000000010, 776000000004, 777000000012, 778000000003, 779000000011, 780000000007, 781000000012, 782000000010, 783000000008, 784000000003, 785000000022, 786000000003, 787000000007, 788000000008, 789000000010, 790000000001, 791000000010, 792000000008, 793000000020, 794000000003, 795000000003, 796000000003, 797000000009, 798000000003, 799000000010, 800000000013, 801000000022, 802000000008, 803000000008, 804000000003, 805000000020, 806000000007, 807000000007, 808000000010, 809000000020, 810000000012, 811000000008, 812000000008, 813000000020, 814000000004, 815000000003, 816000000012, 817000000001, 818000000021, 819000000004, 820000000020, 821000000007, 822000000004, 823000000007, 824000000008, 825000000020, 826000000010, 827000000003, 828000000010, 829000000012, 830000000008, 831000000007, 832000000004, 833000000003, 834000000012, 835000000003, 836000000018, 837000000010, 838000000003, 839000000003, 840000000007, 841000000003, 842000000012, 843000000003, 844000000010, 845000000012, 846000000004, 847000000010, 848000000008, 849000000020, 850000000008, 851000000004, 852000000003, 853000000010, 854000000008, 855000000003, 856000000007, 857000000003, 858000000010, 859000000003, 860000000008, 861000000009, 862000000010, 863000000008, 864000000008, 865000000003, 866000000004, 867000000020, 868000000003, 869000000012, 870000000010, 871000000003, 872000000012, 873000000012, 874000000013, 875000000003, 876000000008, 877000000018, 878000000003, 879000000004, 880000000004, 881000000022, 882000000008, 883000000008, 884000000010, 885000000010, 886000000018, 887000000003, 888000000008, 889000000008, 890000000010, 891000000019, 892000000001, 893000000021, 894000000010, 895000000003, 896000000001, 897000000022, 898000000010, 899000000010, 900000000010, 901000000012, 902000000003, 903000000001, 904000000008, 905000000020, 906000000007, 907000000006, 908000000003, 909000000009, 910000000010, 911000000004, 912000000008, 913000000010, 914000000004, 915000000008, 916000000018, 917000000020, 918000000004, 919000000020, 920000000008, 921000000007, 922000000001, 923000000006, 924000000003, 925000000007, 926000000008, 927000000020, 928000000010, 929000000020, 930000000010, 931000000020, 932000000008, 933000000020, 934000000007, 935000000020, 936000000020, 937000000003, 938000000010, 939000000003, 940000000008, 941000000012, 942000000008, 943000000020, 944000000013, 945000000020, 946000000021, 947000000008, 948000000003, 949000000007, 950000000004, 951000000010, 952000000017, 953000000014, 954000000018, 955000000019, 956000000004, 957000000009, 958000000007, 959000000007, 960000000008, 961000000012, 962000000007, 963000000004, 964000000010, 965000000013, 966000000003, 967000000011, 968000000004, 969000000012, 970000000010, 971000000011, 972000000008, 973000000010, 974000000004, 975000000010, 976000000004, 977000000008, 978000000008, 979000000008, 980000000010, 981000000018, 982000000004, 983000000019, 984000000007, 985000000012, 986000000010, 987000000006, 988000000003, 989000000012, 990000000010, 991000000008, 992000000012, 993000000012, 994000000004, 995000000008, 996000000008, 997000000010, 998000000008, 999000000011, 1000000000003]
B = [1, 68893379, 133259591, 197306960, 258074468, 321058221, 382283055, 442079943, 500336881, 560227456, 622527994, 682263310, 741445786, 798255889, 857654838, 914069998, 970961803, 1024948204, 1087295678, 1148272938, 1208239027, 1266032467, 1324334749, 1382824742, 1439392570, 1494819498, 1549934741, 1609100783, 1665400173, 1721448008, 1775209790, 1831848235, 1885921502, 1939492010, 1991112178, 2050766614, 2112089871, 2172073888, 2230540789, 2288414772, 2347070139, 2403605820, 2459496598, 2513177555, 2572867295, 2629831324, 2686613447, 2740669518, 2796708683, 2851139772, 2904639475, 2956417011, 3011953153, 3070471970, 3126979592, 3182557544, 3236564856, 3292540797, 3345675612, 3399342161, 3450440323, 3506572034, 3560670104, 3614368952, 3666026060, 3718408310, 3770426294, 3821300803, 3871117137, 3924201552, 3986979946, 4046654586, 4106081960, 4162299846, 4222649856, 4279677383, 4336351952, 4390617398, 4448907149, 4506623060, 4562967535, 4618135436, 4673002392, 4728449967, 4781815192, 4834711164, 4886411694, 4945825903, 5002429447, 5059264500, 5113278404, 5169320974, 5223781411, 5277319553, 5329104825, 5382955823, 5438195024, 5491726909, 5544231781, 5595619698, 5648497295, 5699054575, 5749487500, 5798115491, 5857595712, 5914749517, 5971396760, 6025839571, 6081377194, 6135983289, 6189595487, 6241916689, 6294820896, 6350315936, 6403795947, 6456745143, 6507366547, 6560831994, 6611950056, 6662905993, 6711648450, 6766476490, 6820913441, 6874428795, 6926316662, 6978562171, 7030960758, 7081651500, 7131721775, 7180825296, 7233861602, 7284235157, 7335308949, 7383946129, 7434580247, 7483421882, 7531839826, 7578661200, 7635236241, 7697055297, 7757077932, 7815715894, 7873058681, 7932249087, 7988577994, 8044653415, 8098012333, 8158200422, 8215272556, 8271911022, 8326242088, 8381944927, 8436540546, 8489905558, 8542261777, 8596915673, 8655602906, 8712015325, 8767882313, 8821503977, 8877552279, 8931277229, 8984991041, 9036279047, 9091851779, 9146297230, 9199821997, 9251584778, 9303831279, 9356171278, 9406948647, 9456804991, 9507772972, 9566975567, 9623267240, 9679543313, 9733434435, 9789975117, 9844038500, 9897678920, 9949281447, 10003792381, 10058377960, 10112100641, 10164470482, 10216181230, 10268809154, 10319505606, 10369813965, 10418075498, 10474741638, 10528615269, 10582315243, 10633600196, 10686641977, 10738286605, 10789015399, 10838422600, 10889263629, 10941706579, 10992345971, 11042480940, 11091014413, 11141401193, 11189446688, 11238047136, 11284442708, 11342692541, 11400043716, 11456704383, 11511253813, 11566358838, 11621500042, 11675030116, 11727558944, 11779819896, 11835695130, 11888992017, 11942064853, 11992859175, 12046543940, 12097772160, 12148568205, 12197611505, 12251694863, 12306324279, 12359755044, 12412095484, 12463983381, 12516495567, 12567201826, 12617413973, 12665991339, 12719059556, 12770192510, 12821170415, 12869928561, 12920299146, 12969355125, 13017676801, 13064569631, 13116119347, 13171350401, 13224844768, 13277398041, 13328753819, 13381693538, 13432205283, 13482893638, 13531516435, 13584772394, 13636026472, 13686943500, 13735979681, 13785865978, 13835161648, 13883608315, 13931009795, 13979504601, 14032227055, 14082889109, 14133219767, 14181207648, 14232225569, 14280860013, 14329327186, 14375873685, 14425570429, 14474683511, 14522917961, 14570088152, 14617220833, 14664680717, 14710598876, 14756230527, 14803053091, 14866225579, 14925927517, 14986265249, 15043328397, 15102901646, 15160331795, 15216929503, 15271514456, 15328480420, 15386984215, 15443553442, 15498993161, 15553194664, 15609054522, 15662358066, 15715418486, 15766356253, 15826159190, 15883308182, 15939920147, 15994362686, 16049976945, 16104592423, 16158092431, 16210438554, 16263461084, 16318888957, 16372352529, 16425238888, 16476018007, 16529247955, 16580373360, 16631338620, 16680086231, 16737769616, 16795335104, 16851890142, 16906483785, 16961690624, 17016966940, 17070458270, 17123074150, 17174950077, 17230890570, 17284061996, 17337647739, 17388756481, 17442181830, 17493429253, 17544397267, 17593488535, 17646855915, 17701690242, 17755314900, 17807754287, 17859287687, 17912067603, 17962675317, 18013029620, 18061051667, 18114910348, 18166062377, 18216970316, 18265841953, 18316057310, 18365210709, 18413392955, 18460653078, 18512811702, 18571535301, 18627907994, 18683776001, 18737478153, 18793523773, 18847023235, 18900817010, 18952032974, 19007700102, 19062077239, 19115623623, 19167414472, 19219600213, 19271947279, 19322726451, 19372604726, 19422941152, 19478787182, 19532070445, 19585117795, 19636226456, 19689807271, 19741077501, 19791923965, 19840983418, 19892786562, 19944564038, 19995393521, 20045107047, 20094326963, 20144210085, 20192521559, 20240354779, 20286812865, 20343211783, 20397099061, 20450824469, 20502075677, 20555132614, 20606722070, 20657498201, 20706775955, 20757770915, 20810168846, 20860876478, 20910906300, 20959582579, 21009901081, 21057882587, 21106382415, 21152733653, 21205582997, 21256911392, 21307838382, 21356948180, 21406663385, 21456158031, 21504528504, 21551986324, 21599340914, 21649528392, 21697684749, 21745651073, 21791570282, 21840108257, 21886513345, 21932668415, 21977247105, 22032765700, 22090499681, 22146811735, 22202085605, 22256916738, 22312357720, 22365738137, 22418619531, 22469874592, 22525931819, 22579576162, 22633319952, 22684554459, 22737643133, 22789267578, 22840061963, 22889275723, 22941965870, 22997229960, 23050749231, 23103246849, 23154628689, 23207487337, 23258082556, 23308580465, 23357203057, 23410563852, 23461818718, 23512704452, 23561764436, 23611689892, 23660887009, 23709303731, 23756675358, 23806512279, 23862038008, 23915494214, 23968452300, 24019036913, 24072586010, 24123691686, 24174646838, 24223376757, 24275846139, 24327485032, 24378233442, 24427599239, 24477185052, 24526980271, 24575197079, 24622891068, 24670092483, 24723131042, 24773537932, 24824662600, 24873302579, 24923908688, 24972770853, 25021173629, 25068015340, 25116725355, 25166323441, 25214648447, 25262135769, 25308734245, 25356544942, 25402475776, 25448230516, 25492236915, 25548761491, 25602750833, 25656319523, 25707862221, 25760574712, 25812372246, 25863040051, 25912772321, 25963227390, 26015729128, 26066427640, 26116641736, 26165009849, 26215373392, 26263928405, 26312425247, 26358914392, 26411098174, 26462710771, 26513488077, 26562705714, 26612343806, 26662058296, 26710362411, 26757832996, 26804969942, 26855218742, 26903312512, 26951487944, 26997835974, 27046135568, 27092611591, 27138793405, 27183456062, 27233513116, 27285348708, 27336299916, 27386057975, 27435168073, 27485170427, 27533405061, 27581301057, 27627179926, 27678132439, 27726725638, 27775211168, 27821734145, 27869617955, 27916421232, 27962431775, 28007444758, 28054640597, 28104460510, 28152624567, 28200381644, 28246654269, 28294624737, 28340513178, 28386841642, 28431184673, 28478973586, 28525619603, 28571742908, 28616509167, 28661560942, 28706768564, 28750833408, 28794209890, 28842294795, 28905186179, 28964871069, 29024268121, 29080912125, 29141037405, 29198148725, 29254728214, 29309186074, 29367170406, 29424967689, 29481456857, 29536704007, 29591438990, 29646855940, 29700314882, 29753185651, 29804503416, 29864014334, 29920990330, 29977786884, 30031835556, 30087884718, 30142325907, 30195839987, 30247608847, 30301434929, 30356667064, 30410188912, 30462769173, 30514081134, 30567033733, 30617511319, 30668291595, 30716904513, 30775993046, 30833122275, 30889859071, 30944323366, 30999721831, 31054502386, 31108158627, 31160560928, 31213149133, 31268843077, 31322196448, 31375230687, 31425584168, 31479496111, 31530637849, 31581567653, 31630418873, 31684919690, 31739467818, 31792852286, 31845019592, 31897049165, 31949521357, 32000147932, 32050381058, 32099238035, 32152316731, 32202990880, 32254045637, 32302741063, 32353195621, 32402185241, 32450499646, 32497409774, 32551101145, 32609591857, 32666158607, 32721584519, 32775796735, 32831655359, 32884942408, 32938001296, 32989010364, 33045508593, 33099580207, 33153152633, 33204770257, 33257402540, 33309179907, 33359986547, 33409698617, 33461157567, 33516562801, 33570065316, 33622988313, 33673705811, 33727022843, 33778135478, 33829101918, 33877853900, 33930368788, 33981976675, 34032741869, 34081959056, 34131660215, 34181408364, 34229685130, 34277288021, 34325312559, 34381288713, 34434419167, 34488092437, 34539188452, 34592595750, 34643902701, 34694844421, 34743950376, 34795369738, 34847393331, 34898265923, 34948082630, 34997030702, 35047179871, 35095312743, 35143286697, 35189153260, 35242936517, 35294100315, 35344979105, 35393901555, 35444069626, 35493236339, 35541392994, 35588698098, 35636825064, 35686709681, 35734899440, 35782707383, 35828886343, 35876851414, 35922974203, 35969239653, 36013628678, 36070900958, 36128511987, 36185090982, 36239720085, 36294815630, 36350051418, 36403585146, 36456091000, 36508230343, 36564070737, 36617336915, 36670475371, 36721602683, 36775159520, 36826427008, 36877280470, 36926349562, 36980123985, 37034730897, 37088344838, 37140664989, 37192453164, 37245019146, 37295767291, 37346034592, 37394326368, 37447800007, 37498916595, 37549873315, 37598613251, 37648963795, 37698029779, 37746340905, 37793332372, 37844577296, 37899889336, 37953304897, 38006036408, 38057158348, 38110192274, 38160563603, 38211645123, 38260282435, 38313330273, 38364700291, 38415596635, 38464725898, 38514409378, 38563944577, 38612299315, 38659763286, 38707880970, 38760794776, 38811389298, 38861784878, 38909973383, 38960970876, 39009664604, 39058034694, 39104721938, 39154152250, 39203347804, 39251538904, 39298907368, 39345928455, 39393421262, 39439409416, 39485035016, 39530249158, 39586299701, 39640027984, 39693744652, 39745030431, 39798105992, 39849725029, 39900513757, 39949714551, 40000796801, 40053136798, 40103913396, 40153769454, 40202608515, 40252853905, 40300971699, 40349088867, 40395447353, 40448582465, 40499859499, 40550752322, 40599806638, 40649707029, 40698886606, 40747372532, 40794754856, 40842456201, 40892436453, 40940670216, 40988559536, 41034433015, 41082838570, 41129184850, 41175397824, 41219833290, 41271204736, 41322851146, 41373578055, 41422987701, 41472546648, 41522358757, 41570544176, 41618273689, 41664941793, 41715334144, 41763381832, 41811982121, 41858376596, 41906483985, 41953101213, 41999249406, 42044000184, 42091800496, 42141440213, 42189765544, 42237274776, 42283860365, 42331675768, 42377593888, 42423349647, 42467417030, 42515787485, 42562239893, 42608330177, 42652991930, 42698463164, 42743263085, 42787257264, 42830516276, 42879866836, 42938555865, 42995017858, 43050869401, 43104414949, 43160478747, 43214385710, 43268118096, 43319392668, 43374910945, 43429341914, 43482868518, 43534639023, 43586906812, 43639232091, 43689996304, 43739907828, 43789986623, 43845900150, 43899115238, 43952535353, 44003656521, 44057131437, 44108386154, 44159304409, 44208343923, 44259953435, 44311826333, 44362754634, 44412525321, 44461580936, 44511644575, 44559849001, 44607756843, 44653623140, 44710470636, 44764386221, 44818091501, 44869438266, 44922394390, 44974059527, 45024753921, 45074271625, 45124990629, 45177458723, 45228036686, 45278272231, 45326777467, 45377170940, 45425333727, 45473894882, 45520319337, 45572819759, 45624315341, 45675128938, 45724311857, 45773867693, 45823605113, 45871928648, 45919424834, 45966662798, 46016885033, 46065023007, 46112965771, 46159179567, 46207557209, 46254039379, 46300157829, 46344835665, 46397425336, 46452040635, 46505543966, 46557889914, 46609727016, 46662228315, 46712962404, 46763178604, 46811682021, 46864914811, 46916041921, 46967006457, 47015754564, 47066127891, 47115179597, 47163492546, 47210370402, 47260302074, 47312670017, 47363425343, 47413396560, 47462138029, 47512428498, 47560459107, 47608831244, 47655183406, 47705644461, 47754383950, 47802864066, 47849652415, 47897073524, 47944129862, 47990289696, 48035576892, 48082547945, 48135332378, 48185936754, 48236295662, 48284319307, 48335417278, 48384068012, 48432493864, 48479087062, 48528688942, 48577843341, 48626023725, 48673287136, 48720335006, 48767850905, 48813810542, 48859439447, 48904206513, 48954574344, 49002882587, 49051418731, 49097859263, 49145834216, 49192551562, 49238655926, 49283463255, 49329769173, 49377130277, 49423206696, 49468552755, 49513048939, 49558665052, 49602556140, 49646288703, 49688710985, 49744658348, 49798718214, 49852308207, 49903914517, 49956535721, 50008311554, 50059144371, 50108854941, 50159094561, 50211622213, 50262399231, 50312650254, 50360866599, 50411529345, 50460146516, 50508628923, 50555097791, 50607095355, 50658684536, 50709462627, 50758743358, 50808399506, 50858169911, 50906415298, 50954054324, 51000913558, 51051231023, 51099213331, 51147716752, 51194070184, 51242282605, 51288814448, 51335012612, 51379727681, 51429382479, 51481475435, 51532317307, 51582151976]

n = int(input())
p = bisect_right(A, n) - 1
x = A[p]
ans = B[p]
while x < n:
    x += popcount(x)
    ans += 1

if x == n:
    print(ans)
else:
    print(-1)
0