1 /* 2 * Copyright 2021 Higher Frequency Trading http://www.higherfrequencytrading.com 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 /* 17 * Forked from zero-allocation-hashing-0.14 (https://github.com/OpenHFT/Zero-Allocation-Hashing). 18 * Modified by the gRPC Authors 19 */ 20 21 package io.grpc.xds; 22 23 import static org.junit.Assert.assertEquals; 24 25 import java.nio.ByteBuffer; 26 import java.nio.ByteOrder; 27 import java.nio.charset.StandardCharsets; 28 import java.util.ArrayList; 29 import java.util.Arrays; 30 import java.util.Collection; 31 import org.junit.Test; 32 import org.junit.experimental.runners.Enclosed; 33 import org.junit.runner.RunWith; 34 import org.junit.runners.JUnit4; 35 import org.junit.runners.Parameterized; 36 37 /** 38 * Unit tests for {@link XxHash64}. Adapted from 39 * <a href="https://github.com/OpenHFT/Zero-Allocation-Hashing/blob/master/src/test/java/net/openhft/hashing/LongHashFunctionTest.java"> 40 * OpenHFT/Zero-Allocation-Hashing</a>. 41 */ 42 @RunWith(Enclosed.class) 43 public class XxHash64Test { 44 45 @RunWith(Parameterized.class) 46 public static class HashingTest { 47 48 /** Data for test. */ 49 @Parameterized.Parameters data()50 public static Collection<Object[]> data() { 51 ArrayList<Object[]> data = new ArrayList<>(); 52 for (int len = 0; len < 1025; len++) { 53 data.add(new Object[]{len}); 54 } 55 return data; 56 } 57 58 @Parameterized.Parameter 59 public int len; 60 61 @Test withoutSeeds()62 public void withoutSeeds() { 63 test(XxHash64.INSTANCE, HASHES_OF_LOOPING_BYTES_WITHOUT_SEED); 64 } 65 66 @Test withOneSeed()67 public void withOneSeed() { 68 test(new XxHash64(42L), HASHES_OF_LOOPING_BYTES_WITH_SEED_42); 69 } 70 test(XxHash64 f, long[] hashesOfLoopingBytes)71 private void test(XxHash64 f, long[] hashesOfLoopingBytes) { 72 byte[] data = new byte[len]; 73 for (int j = 0; j < data.length; j++) { 74 data[j] = (byte) j; 75 } 76 test(f, data, hashesOfLoopingBytes[len]); 77 } 78 test(XxHash64 f, byte[] data, long eh)79 private static void test(XxHash64 f, byte[] data, long eh) { 80 int len = data.length; 81 testVoid(f, eh, len); 82 testBytes(f, eh, data); 83 testAsciiString(f, eh, len, data); 84 ByteBuffer bb = ByteBuffer.wrap(data).order(ByteOrder.nativeOrder()); 85 testByte(f, eh, len, bb); 86 testShort(f, eh, len, bb); 87 testChar(f, eh, len, bb); 88 testInt(f, eh, len, bb); 89 testLong(f, eh, len, bb); 90 testNegativePrimitives(f, len); 91 } 92 testVoid(XxHash64 f, long eh, int len)93 private static void testVoid(XxHash64 f, long eh, int len) { 94 if (len == 0) { 95 assertEquals("void", eh, f.hashVoid()); 96 } 97 } 98 testByte(XxHash64 f, long eh, int len, ByteBuffer bb)99 private static void testByte(XxHash64 f, long eh, int len, ByteBuffer bb) { 100 if (len == 1) { 101 assertEquals("byte hash", eh, f.hashByte(bb.get(0))); 102 } 103 } 104 testShort(XxHash64 f, long eh, int len, ByteBuffer bb)105 private static void testShort(XxHash64 f, long eh, int len, ByteBuffer bb) { 106 if (len == 2) { 107 assertEquals("short hash", eh, f.hashShort(bb.getShort(0))); 108 } 109 } 110 testChar(XxHash64 f, long eh, int len, ByteBuffer bb)111 private static void testChar(XxHash64 f, long eh, int len, ByteBuffer bb) { 112 if (len == 2) { 113 assertEquals("char hash", eh, f.hashChar(bb.getChar(0))); 114 } 115 } 116 testInt(XxHash64 f, long eh, int len, ByteBuffer bb)117 private static void testInt(XxHash64 f, long eh, int len, ByteBuffer bb) { 118 if (len == 4) { 119 assertEquals("int hash", eh, f.hashInt(bb.getInt(0))); 120 } 121 } 122 testLong(XxHash64 f, long eh, int len, ByteBuffer bb)123 private static void testLong(XxHash64 f, long eh, int len, ByteBuffer bb) { 124 if (len == 8) { 125 assertEquals("long hash", eh, f.hashLong(bb.getLong(0))); 126 } 127 } 128 testNegativePrimitives(XxHash64 f, int len)129 private static void testNegativePrimitives(XxHash64 f, int len) { 130 if (len == 0) { 131 byte[] bytes = new byte[8]; 132 Arrays.fill(bytes, (byte) -1); 133 long oneByteExpected = f.hashBytes(bytes, 0, 1); 134 long twoByteExpected = f.hashBytes(bytes, 0, 2); 135 long fourByteExpected = f.hashBytes(bytes, 0, 4); 136 long eightByteExpected = f.hashBytes(bytes); 137 assertEquals("byte hash", oneByteExpected, f.hashByte((byte) -1)); 138 assertEquals("short hash", twoByteExpected, f.hashShort((short) -1)); 139 assertEquals("char hash", twoByteExpected, f.hashChar(Character.MAX_VALUE)); 140 assertEquals("int hash", fourByteExpected, f.hashInt(-1)); 141 assertEquals("long hash", eightByteExpected, f.hashLong(-1L)); 142 } 143 } 144 testBytes(XxHash64 f, long eh, byte[] data)145 private static void testBytes(XxHash64 f, long eh, byte[] data) { 146 assertEquals("byte array", eh, f.hashBytes(data)); 147 } 148 testAsciiString(XxHash64 f, long eh, int len, byte[] data)149 private static void testAsciiString(XxHash64 f, long eh, int len, byte[] data) { 150 if (len <= 128) { 151 assertEquals("string hash", eh, f.hashAsciiString( 152 new String(data, StandardCharsets.US_ASCII))); 153 } 154 } 155 } 156 157 @RunWith(JUnit4.class) 158 public static class CollisionTest { 159 160 @SuppressWarnings("ConstantOverflow") 161 @Test collisionTest()162 public void collisionTest() { 163 XxHash64 f = XxHash64.INSTANCE; 164 ByteBuffer sequence = ByteBuffer.allocate(128); 165 sequence.order(ByteOrder.LITTLE_ENDIAN); 166 sequence.putLong(0, 1); 167 sequence.putLong(16, 42); 168 sequence.putLong(32, 2); 169 long h1 = f.hashBytes(sequence.array()); 170 171 sequence.putLong(0, 1 + 0xBA79078168D4BAFL); 172 sequence.putLong(32, 2 + 0x9C90005B80000000L); 173 long h2 = f.hashBytes(sequence.array()); 174 assertEquals(h1, h2); 175 176 sequence.putLong(0, 1 + 0xBA79078168D4BAFL * 2); 177 sequence.putLong(32, 2 + 0x9C90005B80000000L * 2); 178 179 long h3 = f.hashBytes(sequence.array()); 180 assertEquals(h2, h3); 181 } 182 } 183 184 /* 185 * Test data is output of the following program with xxHash implementation 186 * from https://github.com/Cyan4973/xxHash 187 * 188 * #include "xxhash.c" 189 * #include <stdlib.h> 190 * #include <stdio.h> 191 * int main() 192 * { 193 * char* src = (char*) malloc(1024); 194 * const int N = 1024; 195 * for (int i = 0; i < N; i++) { 196 * src[i] = (char) i; 197 * } 198 * 199 * printf("without seed\n"); 200 * for (int i = 0; i <= N; i++) { 201 * printf("%lldL,\n", (long long) XXH64(src, i, 0)); 202 * } 203 * 204 * printf("with seed 42\n"); 205 * for (int i = 0; i <= N; i++) { 206 * printf("%lldL,\n", (long long) XXH64(src, i, 42)); 207 * } 208 * } 209 */ 210 211 private static final long[] HASHES_OF_LOOPING_BYTES_WITHOUT_SEED = { 212 -1205034819632174695L, 213 -1642502924627794072L, 214 5216751715308240086L, 215 -1889335612763511331L, 216 -13835840860730338L, 217 -2521325055659080948L, 218 4867868962443297827L, 219 1498682999415010002L, 220 -8626056615231480947L, 221 7482827008138251355L, 222 -617731006306969209L, 223 7289733825183505098L, 224 4776896707697368229L, 225 1428059224718910376L, 226 6690813482653982021L, 227 -6248474067697161171L, 228 4951407828574235127L, 229 6198050452789369270L, 230 5776283192552877204L, 231 -626480755095427154L, 232 -6637184445929957204L, 233 8370873622748562952L, 234 -1705978583731280501L, 235 -7898818752540221055L, 236 -2516210193198301541L, 237 8356900479849653862L, 238 -4413748141896466000L, 239 -6040072975510680789L, 240 1451490609699316991L, 241 -7948005844616396060L, 242 8567048088357095527L, 243 -4375578310507393311L, 244 -3749919242623962444L, 245 888155921178136237L, 246 -228195649085979072L, 247 -521095004075279741L, 248 -2458702038214709156L, 249 -2792334161285995319L, 250 7509323632532862410L, 251 46046374822258777L, 252 -731200582691896855L, 253 933917387460394992L, 254 5623144551929396680L, 255 6456984547425914359L, 256 -6398540474588876142L, 257 1224372500617079775L, 258 -931727396974525131L, 259 979677643219401656L, 260 -8078270932489049756L, 261 -92767506898879473L, 262 2379112167176776082L, 263 2065719310945572007L, 264 -4972682801816081667L, 265 -7346559332994187462L, 266 4674729779638751546L, 267 5844780159702313017L, 268 925606237565008152L, 269 8164325403643669774L, 270 5124005065773312983L, 271 -4646462236086916483L, 272 4733593776494364101L, 273 -6408850806317360L, 274 7405089268865026700L, 275 -2131704682637193649L, 276 -592659849139514384L, 277 -4386868621773355429L, 278 -2216833672566288862L, 279 4022619316305276641L, 280 -60464713570988944L, 281 2416749694506796597L, 282 3576590985110933976L, 283 3368688771415645536L, 284 -357157638897078259L, 285 3484358739758473117L, 286 2078888409435083535L, 287 8053093288416703076L, 288 -4934736471585554038L, 289 -7784370683223414061L, 290 -4109284735634941390L, 291 5982490102027564625L, 292 -4991107002810882893L, 293 8664747912276562373L, 294 8536879438728327651L, 295 2358675440174594061L, 296 5352236919104495867L, 297 6340852522718110192L, 298 5075606340464035668L, 299 -6313168920073458239L, 300 -6428599582591385786L, 301 -7278654800402467208L, 302 -6630626099856243581L, 303 -7548742438664634646L, 304 5514383762309532642L, 305 -5996126265702944431L, 306 4011116741319319261L, 307 -7289240093981845088L, 308 4975257207486779926L, 309 -3945500877932691916L, 310 1973955144068521079L, 311 3884425912161913184L, 312 7692681977284421015L, 313 -1616730378439673826L, 314 4799493270916844476L, 315 -6107310582897997679L, 316 3643294092300179537L, 317 5406040598516899149L, 318 -3032420409304067208L, 319 5044227119457305622L, 320 9165032773225506149L, 321 7553488247682850248L, 322 2247298339072845043L, 323 7380491470304042584L, 324 -456791943260357427L, 325 -1906500292613319324L, 326 -4025157985304129897L, 327 6167829983725509611L, 328 -8678196943431064825L, 329 -636391087313417831L, 330 5757999497725839182L, 331 8999325347316115948L, 332 -6042339776328081249L, 333 7988836354190359013L, 334 2818448030979902104L, 335 -8484201484113382447L, 336 -1140175406473847155L, 337 3042776987426497381L, 338 3147338037480432386L, 339 5065714330193756569L, 340 8827021486636772242L, 341 838335823706922959L, 342 481844220820054909L, 343 5333474685474667077L, 344 -3722898251196013565L, 345 7909417627390150381L, 346 7116148225996109646L, 347 7520381989775811302L, 348 6045444672904719015L, 349 169039646730338133L, 350 -2144629916252757106L, 351 -3752608501798118554L, 352 8374704774878780935L, 353 -5830926781667225570L, 354 3202139393110256022L, 355 4400219135677717216L, 356 -5663710220155589201L, 357 -2589002340345751622L, 358 -8240133511464343390L, 359 -4036798392879835146L, 360 501599054729008501L, 361 -4851415719238782188L, 362 7565157933617774080L, 363 -6428091359957700043L, 364 4081845077806300175L, 365 -9016659258880122392L, 366 7811786097015457596L, 367 1357606791019752376L, 368 6522211979684949668L, 369 -3462397075047559451L, 370 3075504459164148117L, 371 3055992297861390732L, 372 -7230492327399411047L, 373 -1128103378253532506L, 374 1834607408788151585L, 375 7065978976369231860L, 376 6566122632438908362L, 377 -3440855531356735824L, 378 6271453770746181891L, 379 413365468403580071L, 380 -8342682158827061522L, 381 -3713303136987568731L, 382 -8959326895824091541L, 383 -2793862582117663595L, 384 -184756427409317729L, 385 -7052502019782453427L, 386 3666196071825438258L, 387 170204095295428634L, 388 -1880693509859077843L, 389 5179169206996749826L, 390 2866097700453114958L, 391 1859104195026275510L, 392 3782323564639128125L, 393 -6485194456269981193L, 394 6761934873296236857L, 395 5764605515941066448L, 396 597754945258033208L, 397 -4888986062036739232L, 398 -6490228233091577705L, 399 3234089784845854336L, 400 -5506883591180767430L, 401 1491493862343818933L, 402 3232293217886687768L, 403 -4079803366160739972L, 404 4884134040093556099L, 405 -7274733680156962461L, 406 5265680254123454403L, 407 1036855740788018258L, 408 423439784169709263L, 409 -3627743032115866622L, 410 -6311378083791982305L, 411 -3058076915688265687L, 412 5826550132901840796L, 413 8049712006832885455L, 414 1707844692241288946L, 415 -3293048440386932248L, 416 -2458638193238955307L, 417 943059295184967928L, 418 3899561579431348819L, 419 -1516862862245909493L, 420 4448476568037673976L, 421 8738531437146688925L, 422 -1033913449611929894L, 423 733668166271378558L, 424 438686375775205249L, 425 -4325889118346169305L, 426 -238178883117433622L, 427 -7972205050662019794L, 428 -1263398103237492853L, 429 -8333197763892905802L, 430 7796341294364809534L, 431 -1381767618016537445L, 432 2892579485651013970L, 433 -3376209887503828920L, 434 -8575120126045607817L, 435 -1609355362031172055L, 436 -386138918275547508L, 437 4598874691849543747L, 438 -2961781601824749597L, 439 -3032925351997820092L, 440 -4256249198066449735L, 441 6712291718681474012L, 442 -4281614253751277086L, 443 3727487933918100016L, 444 -2744649548868700294L, 445 8662377383917584333L, 446 -9154398439761221404L, 447 -6895275824272461794L, 448 3394857180017540444L, 449 2010825527298793302L, 450 4894417464710366872L, 451 -6879244364314087051L, 452 83677167865178033L, 453 -8258406393927169823L, 454 5042126978317943321L, 455 6485279223034053259L, 456 4442956705009100620L, 457 316801800427881731L, 458 1381431847939703076L, 459 5172932759041399062L, 460 -69656533526213521L, 461 -5302643413630076306L, 462 -3956089084400440856L, 463 372087412941022771L, 464 4711314482928419386L, 465 3255220726505012060L, 466 8917854303046844847L, 467 1116214654602499731L, 468 2282408585429094475L, 469 -9207590323584417562L, 470 8881688165595519866L, 471 1731908113181957442L, 472 3847295165012256987L, 473 4457829016858233661L, 474 4944046822375522396L, 475 3445091217248591320L, 476 -5055680960069278553L, 477 -399195423199498362L, 478 -8109174165388156886L, 479 4967185977968814820L, 480 -5911973391056763118L, 481 2239508324487797550L, 482 -954783563382788523L, 483 8523699184200726144L, 484 932575865292832326L, 485 -7491448407022023047L, 486 1809887519026638446L, 487 -8610524715250756725L, 488 6158809695983348998L, 489 4948400960714316843L, 490 -4513370424175692831L, 491 -3955280856263842959L, 492 6440233015885550592L, 493 8756942107256956958L, 494 7895095834297147376L, 495 370033091003609904L, 496 948078545203432448L, 497 -8523229038380945151L, 498 100794871657160943L, 499 -2186420796072284323L, 500 -9221115378196347951L, 501 8102537654803861332L, 502 5857339063191690550L, 503 -4554257374958739421L, 504 6607496554818971053L, 505 -778402196622557070L, 506 -3817535277727878318L, 507 3564122000469288769L, 508 -44446230828995950L, 509 1322708749649533240L, 510 6150374672341998205L, 511 -3300275952549095391L, 512 5700833512536085850L, 513 -8559358370491270937L, 514 5434443260519512697L, 515 -8031025173259990945L, 516 7117462129248544172L, 517 5425177419943569451L, 518 -7215427371174054838L, 519 -5728669976971194528L, 520 -2096361446095323077L, 521 -4247416835972286805L, 522 4912769047482466787L, 523 7755341152739082452L, 524 6797061233443658471L, 525 4089361562209715474L, 526 5830701413838808929L, 527 5514515889578551370L, 528 609334005368729318L, 529 177310574483850759L, 530 -820431153866372784L, 531 7188454041446661654L, 532 7480194911613035473L, 533 4564607884390103056L, 534 888496928954372093L, 535 -5480535802290619117L, 536 9100964700413324707L, 537 510523132632789099L, 538 8249362675875046694L, 539 5340321809639671537L, 540 -4633081050124361874L, 541 -839915092967986193L, 542 -7377542419053401928L, 543 1820485955145562839L, 544 8517645770425584256L, 545 -1877318739474090786L, 546 7674371564231889244L, 547 -3311130470964498678L, 548 -880090321525066135L, 549 -5670998531776225745L, 550 -8828737503035152589L, 551 -6029750416835830307L, 552 -6535608738168818581L, 553 -550872341393232043L, 554 2831504667559924912L, 555 -4613341433216920241L, 556 502960879991989691L, 557 576723875877375776L, 558 -2575765564594953903L, 559 -4642144349520453953L, 560 7939746291681241029L, 561 6486356905694539404L, 562 -9086235573768687853L, 563 5369903658359590823L, 564 3199947475395774092L, 565 8384948078622146995L, 566 -3365598033653273878L, 567 -2525526479099052030L, 568 2648498634302427751L, 569 3715448294999624219L, 570 -4734466095330028983L, 571 -8440427851760401644L, 572 -371198022355334589L, 573 8864079431738600817L, 574 -4205600060099565684L, 575 6617166152874298882L, 576 -6515522971156180292L, 577 7254251246745292298L, 578 -420587237082849417L, 579 1190495815435763349L, 580 -474540026828753709L, 581 -8150622114536376016L, 582 -5790621848044235275L, 583 -2780522220219318167L, 584 -2991155855957250848L, 585 1692932912262846366L, 586 8814949734565782733L, 587 -8746818869495012552L, 588 7931250816026891600L, 589 -7434629709560596700L, 590 4388261932396122996L, 591 7154847153195510802L, 592 -2810154398655124882L, 593 2601892684639182965L, 594 7781574423676509607L, 595 -6647000723020388462L, 596 -8679132292226137672L, 597 -2447013202020963672L, 598 3658855631326217196L, 599 2176620921764007759L, 600 3654402165357492705L, 601 4511989090021652156L, 602 -3254638803798424003L, 603 9050506214967102331L, 604 922579360317805810L, 605 609820949221381248L, 606 5723875594772949290L, 607 4637721466210023638L, 608 6195303339320487374L, 609 -38202587086649325L, 610 -2142927092331878341L, 611 5355751314914287101L, 612 -7170892783575760055L, 613 -7506612729078573199L, 614 8645580445823695595L, 615 3221950179890871958L, 616 1638211443525398634L, 617 7356718304253861777L, 618 -296260062751271549L, 619 -1790105985391377345L, 620 -7004118620405119098L, 621 7056012094479909462L, 622 -7673357898031223798L, 623 -8929502135696203556L, 624 7527161467311997998L, 625 6182865571027510002L, 626 -2163310275402596869L, 627 6285112477695252864L, 628 3703909999924067987L, 629 962491298117560533L, 630 138936592567072793L, 631 6094857527471100960L, 632 5914305068838335718L, 633 -8896724991235492552L, 634 -2667562314507789198L, 635 -7456492499188304500L, 636 -3422709784851063201L, 637 -1511644999824238281L, 638 -7130158069449057322L, 639 6243266426571961929L, 640 2713895636371672711L, 641 5765589573821453640L, 642 2624585483746388367L, 643 3933828437519859601L, 644 -5664404238108533781L, 645 7086393398544811684L, 646 1322058227068490376L, 647 -8232508114671021371L, 648 -5963804389649678229L, 649 -3318229976491806899L, 650 -6261789542948241754L, 651 199130260709663583L, 652 7521707465510595039L, 653 507353862067534334L, 654 -7737968456769005928L, 655 -8964687882992257099L, 656 -7735003539801528311L, 657 6989812739838460574L, 658 -6986289777499051441L, 659 1881562796144865699L, 660 -6077719780113966592L, 661 -5427071388091979746L, 662 1660707436425817310L, 663 -4338189980197421104L, 664 5330934977599207307L, 665 4461280425701571033L, 666 -7426107478263746863L, 667 4258305289832328199L, 668 -8003283151332860979L, 669 -2500604212764835216L, 670 -8883941775298564436L, 671 -5059709834257638733L, 672 -4582947579039913741L, 673 1371959565630689983L, 674 -1925163414161391371L, 675 -1180269729544278896L, 676 -6603171789097590304L, 677 8985062706306079731L, 678 -3588748723254272836L, 679 -6052032019910018725L, 680 6200960040430493088L, 681 2146343936795524980L, 682 7785948646708747443L, 683 4524411768393719400L, 684 749211414228926779L, 685 -163844243342465015L, 686 1066801203344117463L, 687 -3687825939602944988L, 688 -4873811917429870500L, 689 -3765115783578949524L, 690 3344884226049804020L, 691 -22793631121165636L, 692 -5636541624133159076L, 693 -6201449576244177151L, 694 -4533734412127714050L, 695 -2064657727206266594L, 696 -1325853623186040989L, 697 -2651306529045029511L, 698 903264360879626406L, 699 6082283797495873520L, 700 6185446819995987847L, 701 -5727850940826115079L, 702 8356646143516726527L, 703 -7705915341280821272L, 704 9137633133909463406L, 705 6613483969797411894L, 706 8598514961735984460L, 707 6805925079991408361L, 708 6009403222422527608L, 709 2216303622650116705L, 710 -3736062178532154638L, 711 -7139008962939637477L, 712 -1537711200058404375L, 713 8896755073380580322L, 714 -6063426810787442347L, 715 -3472064301690015285L, 716 -4568131486464952371L, 717 -8141256104294687045L, 718 5627435360893599536L, 719 1136003802967708029L, 720 2730027518034735037L, 721 1985287040172139729L, 722 -3643431491383365431L, 723 -9042919736106376701L, 724 8879968900590373568L, 725 8504486139877409399L, 726 5832665747670146536L, 727 4202923651402292496L, 728 1738511892080946286L, 729 4512683881549777042L, 730 9200194457599870145L, 731 -1948301178705617139L, 732 8655715314401162523L, 733 412698981651521600L, 734 -1479274044808688580L, 735 2688302549664693359L, 736 -3059920027366623178L, 737 -4275753325231806565L, 738 -8321791698013769889L, 739 -3678119714812414102L, 740 -2500922551770832553L, 741 9018541633115002061L, 742 5713301371152396803L, 743 4180584812840471799L, 744 3062416401091271879L, 745 -8125716681035757962L, 746 -2076056159878596225L, 747 8855540523533374738L, 748 2402007906402689092L, 749 2020584786288649542L, 750 1707405964421070701L, 751 -3681994462249973122L, 752 -3982567775984742012L, 753 7133200226358561844L, 754 -5270514263562558963L, 755 9060760368219219429L, 756 -6967162372382490281L, 757 -9094664463528453384L, 758 -3968518633408880046L, 759 8618660189330281694L, 760 -4668946581954397558L, 761 -8596433172676363407L, 762 -1264942061713169049L, 763 -5309493221793643795L, 764 -1099320768477039529L, 765 8925041285873295227L, 766 -6809278181760513499L, 767 -7039439984223885585L, 768 6188209901527865226L, 769 1487353394192637059L, 770 2402097349430126337L, 771 -3818359601525025681L, 772 4123217079279439249L, 773 -1424515143377220376L, 774 1742298536803356877L, 775 -2836832784751148874L, 776 -4838603242771410698L, 777 2383745618623084414L, 778 -2790832243316548423L, 779 -1176683649587660160L, 780 1862928178605117401L, 781 5208694030074527671L, 782 4339841406618876548L, 783 -7704801448691668472L, 784 500068664415229033L, 785 -2111184635274274347L, 786 -1387769336519960517L, 787 -2368660677263980293L, 788 -4980481392402938776L, 789 -6856361166068680884L, 790 1708658704968066797L, 791 -9013068514618931938L, 792 -2616479975851677179L, 793 7121103440247327570L, 794 -7094192881960646061L, 795 -4042342930006488618L, 796 5294323611741266775L, 797 5235545113690922502L, 798 -2562011392475214878L, 799 -4613304566070234734L, 800 -3784386310583029381L, 801 -4526148219816534267L, 802 -8643470129031767968L, 803 -4573761335510927866L, 804 -8255399593563317902L, 805 -1925488377092111963L, 806 -1747797357090594237L, 807 7292772921748919564L, 808 3951718848780851600L, 809 5339305877764077075L, 810 7889570407201305102L, 811 -8935437555550449315L, 812 -1858205318388884024L, 813 381779657795494278L, 814 -3769854251228686168L, 815 -7957724087073627355L, 816 4349540075286824743L, 817 -2476434494603040708L, 818 -4506107235113109706L, 819 -7120863144673563848L, 820 -8534342596639587598L, 821 2205658724629050493L, 822 604438195864305027L, 823 4530331938860561927L, 824 -2074141653226683751L, 825 -1114378227875974007L, 826 3377301950002508302L, 827 5369356700690664306L, 828 -1747063224581819445L, 829 -6320380781966280801L, 830 -2075443262555773155L, 831 1028541493355576591L, 832 -4694402890123574860L, 833 -5250660999767019003L, 834 3847087895315315136L, 835 -4448050214964317066L, 836 -4591316307978008151L, 837 4894820902772635901L, 838 3088847887353411593L, 839 -6699208183127463352L, 840 4636731998354510780L, 841 9095126525233209263L, 842 4135373626035182291L, 843 3835688804093949701L, 844 -3490782692819028324L, 845 -561453348486424761L, 846 -3329283619698366365L, 847 3251154327320814221L, 848 -8006986328190314286L, 849 5856651505286251345L, 850 -8871425101391073L, 851 7806993676637210959L, 852 7586479850833664643L, 853 -7091216108599847229L, 854 -3410137297792125447L, 855 -8251963871271100526L, 856 -8849730915506517177L, 857 8400334327557485676L, 858 1676125861848906502L, 859 -8480324002538122254L, 860 -1402216371589796114L, 861 5951911012328622382L, 862 8596811512609928773L, 863 -2266336480397111285L, 864 -8840962712683931463L, 865 4301675602445909557L, 866 1843369157327547440L, 867 2169755460218905712L, 868 -1592865257954325910L, 869 -8763867324602133653L, 870 -4283855559993550994L, 871 -7577702976577664015L, 872 -5152834259238990784L, 873 4596243922610406362L, 874 -4326545138850544854L, 875 1480440096894990716L, 876 8548031958586152418L, 877 6705615952497668303L, 878 -2915454802887967935L, 879 -6137002913510169520L, 880 2908515186908319288L, 881 5834242853393037250L, 882 -6721431559266056630L, 883 -7810820823419696676L, 884 1954209413716096740L, 885 6657013078387802473L, 886 2214178984740031680L, 887 8789512881373922013L, 888 1240231669311237626L, 889 8694612319028097761L, 890 492180561068515854L, 891 -6047127535609489112L, 892 7436686740711762797L, 893 -4520261623507558716L, 894 938282189116272147L, 895 3232025564608101134L, 896 -5425498066931840551L, 897 932123105892452494L, 898 9054941090932531526L, 899 8066693670021084601L, 900 764877609198828864L, 901 -489112437588815338L, 902 4827691353685521957L, 903 1948321254606741278L, 904 6117773063719937712L, 905 4645962658121906639L, 906 -7846887104148029590L, 907 4210795945791252618L, 908 -8879516722990993098L, 909 -2621063563373927241L, 910 2094675051444850863L, 911 -8681225697045319537L, 912 6072534474938492189L, 913 6181923696407824226L, 914 5463607676777614919L, 915 3708342890820711111L, 916 8844501223821777366L, 917 -1459359143442302680L, 918 2225439088478089068L, 919 -3866259492807347627L, 920 5715020051188773955L, 921 3922300588924895992L, 922 -9142841818158905228L, 923 2234845285375211931L, 924 2466598091809457099L, 925 -5086614780930363190L, 926 -59740786891006359L, 927 3484340182077240897L, 928 5684798394905475931L, 929 8492255409537329167L, 930 5276601975076232447L, 931 -723955912320185993L, 932 9032937149732310432L, 933 2226206333274026280L, 934 5631303328800272036L, 935 3943832708526382713L, 936 -3756282686478033644L, 937 -5407377327559185078L, 938 2025162219823732106L, 939 -8802502232162774782L, 940 9039368856081455195L, 941 663058667658971174L, 942 3624269418844967319L, 943 1835338408542062149L, 944 6821836507221295281L, 945 6273547355770435776L, 946 -3104373869480308814L, 947 1150888014781722836L, 948 7638478751521711777L, 949 -6407096352658729423L, 950 -2242514077180426481L, 951 -3181824045541296523L, 952 -4562287221569080073L, 953 -5550768647534615669L, 954 -5786611484859469238L, 955 -6147722345444149090L, 956 3737249616177808079L, 957 3401215612108618403L, 958 -713522925214097648L, 959 7938558781452631257L, 960 -2822931074351003413L, 961 -6484774850345918944L, 962 3384659068511379086L, 963 6976459554734427695L, 964 4254162229878558339L, 965 -3312164339867139602L, 966 7263045146222903358L, 967 4561625003713187235L, 968 -3350421200373539593L, 969 -6329267008823047447L, 970 -6889593333717619051L, 971 -6470291206680780949L, 972 -1925391510610223335L, 973 4955720513801530785L, 974 -6515999401129420095L, 975 -5146900596178823847L, 976 2572121582663686783L, 977 -4958678197003031937L, 978 -1295912792184970105L, 979 -8320363273488883198L, 980 -8213501149234986129L, 981 -3883775881968950160L, 982 -8925953418077243474L, 983 3199784299548492168L, 984 -6836506744583692202L, 985 -5007347279129330642L, 986 7387675960164975441L, 987 -5841389805259238070L, 988 6263589037534776610L, 989 3327727201189139791L, 990 3673450414312153409L, 991 -1563909967243907088L, 992 -3758518049401683145L, 993 6368282934319908146L, 994 -6025191831649813215L, 995 1223512633484628943L, 996 -8540335264335924099L, 997 -8569704496403127098L, 998 -5712355262561236939L, 999 -6468621715016340600L, 1000 7015005898276272746L, 1001 -1037164971883038884L, 1002 -6108649908647520338L, 1003 -6781540054819591698L, 1004 -2762739023866345855L, 1005 -270930832663123436L, 1006 -2387080926579956105L, 1007 -3984603512651136889L, 1008 2367015942733558542L, 1009 2997123688964990405L, 1010 -424413420483149165L, 1011 2906467516125124288L, 1012 7979917630945955701L, 1013 2879736983084566817L, 1014 558436267366797870L, 1015 6471658168855475843L, 1016 -3453803644372811678L, 1017 95470628886709014L, 1018 5666911245054448862L, 1019 1594133734978640945L, 1020 3790246368687946045L, 1021 8636400206261643605L, 1022 5901994795106283147L, 1023 -6774812279971490610L, 1024 -4622588246534854941L, 1025 5395884908872287278L, 1026 7381412950348018556L, 1027 5461775216423433041L, 1028 2851500852422732203L, 1029 1153428834012773824L, 1030 2567326223464897798L, 1031 6290362916558214218L, 1032 6095765709335097474L, 1033 -3526424734043456674L, 1034 -8411274175041022530L, 1035 7565408328520233290L, 1036 -1318636864706103626L, 1037 1261242784453012654L, 1038 -472643963000448611L, 1039 -7126293899612852456L, 1040 5072187962931197668L, 1041 4775251504230927816L, 1042 -1624676500499667689L, 1043 2252385971292411863L, 1044 7908437759266752884L, 1045 -8948829914565397845L, 1046 5258787823809553293L, 1047 3885696202809019506L, 1048 -4551784314460062669L, 1049 5315762970089305011L, 1050 7218180419200466576L, 1051 109471822471146966L, 1052 3901499100759315793L, 1053 -5613018173558603696L, 1054 5782419706003468119L, 1055 8285176821902721729L, 1056 -2944182278904878473L, 1057 8089487615165958290L, 1058 6934039118340963316L, 1059 8481603619533191729L, 1060 -6321491167299496492L, 1061 6441589800192421521L, 1062 6436057639713571196L, 1063 6819921695214365155L, 1064 1185928916708893611L, 1065 2597068862418243401L, 1066 -7637601550649263782L, 1067 9129303862479379164L, 1068 4047905726243458335L, 1069 6672087858539795207L, 1070 -4841432774404255351L, 1071 5501215987763227677L, 1072 -5300305896512100453L, 1073 1635946349436492617L, 1074 -5017459781050596604L, 1075 -7313558338536196566L, 1076 4625509831332846264L, 1077 -1241826701278444028L, 1078 2916178164108211239L, 1079 -6947453283344846915L, 1080 5520544791845620925L, 1081 5009241392834567026L, 1082 -630825152277572403L, 1083 6246654103747517292L, 1084 -5632205909016659384L, 1085 -5099826214945383802L, 1086 2466330894206710401L, 1087 -1463559257726812272L, 1088 4922422449110036517L, 1089 -4940410396057186660L, 1090 8835766963654337957L, 1091 -1984334093384497740L, 1092 5616151800825184227L, 1093 -8442970605804311782L, 1094 -5396399970392474268L, 1095 2711274356126287353L, 1096 -5090439840321959043L, 1097 6638617029380445409L, 1098 -6424875729377006548L, 1099 -7243574969986334324L, 1100 -904268348341193502L, 1101 -6196811069886893217L, 1102 -7742123331454617135L, 1103 1449632469607275832L, 1104 3212140938119717436L, 1105 8676942774083692265L, 1106 -6625590425417154859L, 1107 8720904664575676760L, 1108 9151723732605931383L, 1109 7642401923610349184L, 1110 -3454390566366389884L, 1111 -232373658792783206L, 1112 -8933620623437682010L, 1113 2514068248201398743L, 1114 6757007617821370359L, 1115 -2870340646674679163L, 1116 416331333845426881L, 1117 -5319172016123138702L, 1118 3294412564645954555L, 1119 2812538484970453169L, 1120 -9128349093860081905L, 1121 6784456254618976198L, 1122 -2861881330654872638L, 1123 3912429093271518508L, 1124 -2562542119887175820L, 1125 4835616088583228965L, 1126 427639171891209425L, 1127 2590582080178010045L, 1128 -6288067880951692635L, 1129 -3204510905067065501L, 1130 9008426291442999873L, 1131 -4085962609397876083L, 1132 -3786041297813905157L, 1133 -6006475053574578261L, 1134 -6174022276199807178L, 1135 7958957647277035097L, 1136 2915785807118517755L, 1137 2139592530283433011L, 1138 -8562048562533248017L, 1139 -4991735207930685025L, 1140 393144860250454082L, 1141 -5852177196425420458L, 1142 -2652303154023739579L, 1143 2079679586901234739L, 1144 -1386526064824772584L, 1145 1574420554361329695L, 1146 -855542130447493508L, 1147 8291940350733154044L, 1148 -5330200233059892402L, 1149 5140782607921164290L, 1150 -977254437067235218L, 1151 -261520846651909307L, 1152 -7369143208070837455L, 1153 -4728766390712852111L, 1154 -8572213434879266955L, 1155 -6754813768712497692L, 1156 7946121307356573089L, 1157 504268959085012646L, 1158 -5536654029698676818L, 1159 -6021520522792328781L, 1160 6968613512520500871L, 1161 4029920623217569312L, 1162 2738878342460920492L, 1163 4562432005481165726L, 1164 -1279037845195368028L, 1165 1746645308450474697L, 1166 2538150989161378915L, 1167 2012299649948738944L, 1168 -3997559675475377347L, 1169 -5939431505669672858L, 1170 2077103722387383456L, 1171 -6188261335534632204L, 1172 8772504603740967633L, 1173 -1653698997940568281L, 1174 1676948989756529271L, 1175 2377579815165102226L, 1176 -2667481192445387240L, 1177 -5498860615033631762L, 1178 -2490865541169744469L, 1179 -1233441883399707566L, 1180 5445263795307566596L, 1181 2288458809413275798L, 1182 -5908274826918996877L, 1183 2909363406069168415L, 1184 2376032171261335687L, 1185 -5215189045919902574L, 1186 -6083327007632847329L, 1187 2462785604224107327L, 1188 -6684045035730714275L, 1189 2409356208468676804L, 1190 2814747114160772803L, 1191 -4529204412661254980L, 1192 -8437511853472556883L, 1193 1819323657613892915L, 1194 6862685309651627151L, 1195 -9210337863564319258L, 1196 -3641041551811494963L, 1197 -6791020794026796740L, 1198 -5261661996953805298L, 1199 -1953516254626596632L, 1200 -5901591005960707793L, 1201 -7413695905040596911L, 1202 2952256922297384020L, 1203 -8427771021447591769L, 1204 -6920139339436245233L, 1205 2967149838604559395L, 1206 -3253499104068010353L, 1207 -8473804925120692039L, 1208 -3561285603521886085L, 1209 -4453849179065102447L, 1210 2050092642498054323L, 1211 -5626434133619314199L, 1212 7995075368278704248L, 1213 7685996432951370136L, 1214 -8037783900933102779L, 1215 4601459625295412851L, 1216 -4491938778497306775L, 1217 -9089886217821142309L, 1218 -3947191644612298897L, 1219 1364225714229764884L, 1220 2580394324892542249L, 1221 -3765315378396862242L, 1222 6023794482194323576L, 1223 -662753714084561214L, 1224 3080495347149127717L, 1225 911710215008202776L, 1226 -803705685664586056L, 1227 -6101059689379533503L, 1228 -2122356322512227634L, 1229 8012110874513406695L, 1230 -4158551223425336367L, 1231 8282080141813519654L, 1232 4172879384244246799L, 1233 708522065347490110L, 1234 -6997269001146828181L, 1235 1887955086977822594L, 1236 8014460039616323415L 1237 }; 1238 1239 private static final long[] HASHES_OF_LOOPING_BYTES_WITH_SEED_42 = { 1240 -7444071767201028348L, 1241 -8959994473701255385L, 1242 7116559933691734543L, 1243 6019482000716350659L, 1244 -6625277557348586272L, 1245 -5507563483608914162L, 1246 1540412690865189709L, 1247 4522324563441226749L, 1248 -7143238906056518746L, 1249 -7989831429045113014L, 1250 -7103973673268129917L, 1251 -2319060423616348937L, 1252 -7576144055863289344L, 1253 -8903544572546912743L, 1254 6376815151655939880L, 1255 5913754614426879871L, 1256 6466567997237536608L, 1257 -869838547529805462L, 1258 -2416009472486582019L, 1259 -3059673981515537339L, 1260 4211239092494362041L, 1261 1414635639471257331L, 1262 166863084165354636L, 1263 -3761330575439628223L, 1264 3524931906845391329L, 1265 6070229753198168844L, 1266 -3740381894759773016L, 1267 -1268276809699008557L, 1268 1518581707938531581L, 1269 7988048690914090770L, 1270 -4510281763783422346L, 1271 -8988936099728967847L, 1272 -8644129751861931918L, 1273 2046936095001747419L, 1274 339737284852751748L, 1275 -8493525091666023417L, 1276 -3962890767051635164L, 1277 -5799948707353228709L, 1278 -6503577434416464161L, 1279 7718729912902936653L, 1280 191197390694726650L, 1281 -2677870679247057207L, 1282 20411540801847004L, 1283 2738354376741059902L, 1284 -3754251900675510347L, 1285 -3208495075154651980L, 1286 5505877218642938179L, 1287 6710910171520780908L, 1288 -9060809096139575515L, 1289 6936438027860748388L, 1290 -6675099569841255629L, 1291 -5358120966884144380L, 1292 -4970515091611332076L, 1293 -1810965683604454696L, 1294 -516197887510505242L, 1295 1240864593087756274L, 1296 6033499571835033332L, 1297 7223146028771530185L, 1298 909128106589125206L, 1299 1567720774747329341L, 1300 -1867353301780159863L, 1301 4655107429511759333L, 1302 5356891185236995950L, 1303 182631115370802890L, 1304 -3582744155969569138L, 1305 595148673029792797L, 1306 495183136068540256L, 1307 5536689004903505647L, 1308 -8472683670935785889L, 1309 -4335021702965928166L, 1310 7306662983232020244L, 1311 4285260837125010956L, 1312 8288813008819191181L, 1313 -3442351913745287612L, 1314 4883297703151707194L, 1315 9135546183059994964L, 1316 123663780425483012L, 1317 509606241253238381L, 1318 5940344208569311369L, 1319 -2650142344608291176L, 1320 3232776678942440459L, 1321 -922581627593772181L, 1322 7617977317085633049L, 1323 7154902266379028518L, 1324 -5806388675416795571L, 1325 4368003766009575737L, 1326 -2922716024457242064L, 1327 4771160713173250118L, 1328 3275897444752647349L, 1329 -297220751499763878L, 1330 5095659287766176401L, 1331 1181843887132908826L, 1332 9058283605301070357L, 1333 3984713963471276643L, 1334 6050484112980480005L, 1335 1551535065359244224L, 1336 565337293533335618L, 1337 7412521035272884309L, 1338 -4735469481351389369L, 1339 6998597101178745656L, 1340 -9107075101236275961L, 1341 5879828914430779796L, 1342 6034964979406620806L, 1343 5666406915264701514L, 1344 -4666218379625258428L, 1345 2749972203764815656L, 1346 -782986256139071446L, 1347 6830581400521008570L, 1348 2588852022632995043L, 1349 -5484725487363818922L, 1350 -3319556935687817112L, 1351 6481961252981840893L, 1352 2204492445852963006L, 1353 -5301091763401031066L, 1354 -2615065677047206256L, 1355 -6769817545131782460L, 1356 -8421640685322953142L, 1357 -3669062629317949176L, 1358 -9167016978640750490L, 1359 2783671191687959562L, 1360 -7599469568522039782L, 1361 -7589134103255480011L, 1362 -5932706841188717592L, 1363 -8689756354284562694L, 1364 -3934347391198581249L, 1365 -1344748563236040701L, 1366 2172701592984478834L, 1367 -5322052340624064417L, 1368 -8493945390573620511L, 1369 3349021988137788403L, 1370 -1806262525300459538L, 1371 -8091524448239736618L, 1372 4022306289903960690L, 1373 -8346915997379834224L, 1374 -2106001381993805461L, 1375 -5784123934724688161L, 1376 6775158099649720388L, 1377 -3869682756870293568L, 1378 4356490186652082006L, 1379 8469371446702290916L, 1380 -2972961082318458602L, 1381 -7188106622222784561L, 1382 -4961006366631572412L, 1383 3199991182014172900L, 1384 2917435868590434179L, 1385 8385845305547872127L, 1386 7706824402560674655L, 1387 -1587379863634865277L, 1388 -4212156212298809650L, 1389 -1305209322000720233L, 1390 -7866728337506665880L, 1391 8195089740529247049L, 1392 -4876930125798534239L, 1393 798222697981617129L, 1394 -2441020897729372845L, 1395 -3926158482651178666L, 1396 -1254795122048514130L, 1397 5192463866522217407L, 1398 -5426289318796042964L, 1399 -3267454004443530826L, 1400 471043133625225785L, 1401 -660956397365869974L, 1402 -6149209189144999161L, 1403 -2630977660039166559L, 1404 8512219789663151219L, 1405 -3309844068134074620L, 1406 -6211275327487847132L, 1407 -2130171729366885995L, 1408 6569302074205462321L, 1409 4855778342281619706L, 1410 3867211421508653033L, 1411 -3002480002418725542L, 1412 -8297543107467502696L, 1413 8049642289208775831L, 1414 -5439825716055425635L, 1415 7251760070798756432L, 1416 -4774526021749797528L, 1417 -3892389575184442548L, 1418 5162451061244344424L, 1419 6000530226398686578L, 1420 -5713092252241819676L, 1421 8740913206879606081L, 1422 -8693282419677309723L, 1423 1576205127972543824L, 1424 5760354502610401246L, 1425 3173225529903529385L, 1426 1785166236732849743L, 1427 -1024443476832068882L, 1428 -7389053248306187459L, 1429 1171021620017782166L, 1430 1471572212217428724L, 1431 7720766400407679932L, 1432 -8844781213239282804L, 1433 -7030159830170200877L, 1434 2195066352895261150L, 1435 1343620937208608634L, 1436 9178233160016731645L, 1437 -757883447602665223L, 1438 3303032934975960867L, 1439 -3685775162104101116L, 1440 -4454903657585596656L, 1441 -5721532367620482629L, 1442 8453227136542829644L, 1443 5397498317904798888L, 1444 7820279586106842836L, 1445 -2369852356421022546L, 1446 3910437403657116169L, 1447 6072677490463894877L, 1448 -2651044781586183960L, 1449 5173762670440434510L, 1450 -2970017317595590978L, 1451 -1024698859439768763L, 1452 -3098335260967738522L, 1453 -1983156467650050768L, 1454 -8132353894276010246L, 1455 -1088647368768943835L, 1456 -3942884234250555927L, 1457 7169967005748210436L, 1458 2870913702735953746L, 1459 -2207022373847083021L, 1460 1104181306093040609L, 1461 5026420573696578749L, 1462 -5874879996794598513L, 1463 -4777071762424874671L, 1464 -7506667858329720470L, 1465 -2926679936584725232L, 1466 -5530649174168373609L, 1467 5282408526788020384L, 1468 3589529249264153135L, 1469 -6220724706210580398L, 1470 -7141769650716479812L, 1471 5142537361821482047L, 1472 -7029808662366864423L, 1473 -6593520217660744466L, 1474 1454581737122410695L, 1475 -139542971769349865L, 1476 1727752089112067235L, 1477 -775001449688420017L, 1478 -5011311035350652032L, 1479 -8671171179275033159L, 1480 -2850915129917664667L, 1481 -5258897903906998781L, 1482 -6954153088230718761L, 1483 -4070351752166223959L, 1484 -6902592976462171099L, 1485 -7850366369290661391L, 1486 -4562443925864904705L, 1487 3186922928616271015L, 1488 2208521081203400591L, 1489 -2727824999830592777L, 1490 -3817861137262331295L, 1491 2236720618756809066L, 1492 -4888946967413746075L, 1493 -446884183491477687L, 1494 -43021963625359034L, 1495 -5857689226703189898L, 1496 -2156533592262354883L, 1497 -2027655907961967077L, 1498 7151844076490292500L, 1499 -5029149124756905464L, 1500 526404452686156976L, 1501 8741076980297445408L, 1502 7962851518384256467L, 1503 -105985852299572102L, 1504 -2614605270539434398L, 1505 -8265006689379110448L, 1506 8158561071761524496L, 1507 -6923530157382047308L, 1508 5551949335037580397L, 1509 565709346370307061L, 1510 -4780869469938333359L, 1511 6931895917517004830L, 1512 565234767538051407L, 1513 -8663136372880869656L, 1514 1427340323685448983L, 1515 6492705666640232290L, 1516 1481585578088475369L, 1517 -1712711110946325531L, 1518 3281685342714380741L, 1519 6441384790483098576L, 1520 -1073539554682358394L, 1521 5704050067194788964L, 1522 -5495724689443043319L, 1523 -5425043165837577535L, 1524 8349736730194941321L, 1525 -4123620508872850061L, 1526 4687874980541143573L, 1527 -468891940172550975L, 1528 -3212254545038049829L, 1529 -6830802881920725628L, 1530 9033050533972480988L, 1531 4204031879107709260L, 1532 -677513987701096310L, 1533 -3286978557209370155L, 1534 1644111582609113135L, 1535 2040089403280131741L, 1536 3323690950628902653L, 1537 -7686964480987925756L, 1538 -4664519769497402737L, 1539 3358384147145476542L, 1540 -4699919744264452277L, 1541 -4795197464927839170L, 1542 5051607253379734527L, 1543 -8987703459734976898L, 1544 8993686795574431834L, 1545 -2688919474688811047L, 1546 375938183536293311L, 1547 1049459889197081920L, 1548 -1213022037395838295L, 1549 4932989235110984138L, 1550 -6647247877090282452L, 1551 -7698817539128166242L, 1552 -3264029336002462659L, 1553 6487828018122309795L, 1554 -2660821091484592878L, 1555 7104391069028909121L, 1556 -1765840012354703384L, 1557 85428166783788931L, 1558 -6732726318028261938L, 1559 7566202549055682933L, 1560 229664898114413280L, 1561 -1474237851782211353L, 1562 -1571058880058007603L, 1563 -7926453582850712144L, 1564 2487148368914275243L, 1565 8740031015380673473L, 1566 1908345726881363169L, 1567 -2510061320536523178L, 1568 7854780026906019630L, 1569 -6023415596650016493L, 1570 -6264841978089051107L, 1571 4024998278016087488L, 1572 -4266288992025826072L, 1573 -3222176619422665563L, 1574 -1999258726038299316L, 1575 1715270077442385636L, 1576 6764658837948099754L, 1577 -8646962299105812577L, 1578 -51484064212171546L, 1579 -1482515279051057493L, 1580 -8663965522608868414L, 1581 -256555202123523670L, 1582 1973279596140303801L, 1583 -7280796173024508575L, 1584 -5691760367231354704L, 1585 -5915786562256300861L, 1586 -3697715074906156565L, 1587 3710290115318541949L, 1588 6796151623958134374L, 1589 -935299482515386356L, 1590 -7078378973978660385L, 1591 5379481350768846927L, 1592 -9011221735308556302L, 1593 5936568631579608418L, 1594 -6060732654964511813L, 1595 -4243141607840017809L, 1596 3198488845875349355L, 1597 -7809288876010447646L, 1598 4371587872421472389L, 1599 -1304197371105522943L, 1600 7389861473143460103L, 1601 -1892352887992004024L, 1602 2214828764044713398L, 1603 6347546952883613388L, 1604 1275694314105480954L, 1605 -5262663163358903733L, 1606 1524757505892047607L, 1607 1474285098416162746L, 1608 -7976447341881911786L, 1609 4014100291977623265L, 1610 8994982266451461043L, 1611 -7737118961020539453L, 1612 -2303955536994331092L, 1613 1383016539349937136L, 1614 1771516393548245271L, 1615 -5441914919967503849L, 1616 5449813464890411403L, 1617 -3321280356474552496L, 1618 4084073849712624363L, 1619 4290039323210935932L, 1620 2449523715173349652L, 1621 7494827882138362156L, 1622 9035007221503623051L, 1623 5722056230130603177L, 1624 -5443061851556843748L, 1625 -7554957764207092109L, 1626 447883090204372074L, 1627 533916651576859197L, 1628 -3104765246501904165L, 1629 -4002281505194601516L, 1630 -8402008431255610992L, 1631 -408273018037005304L, 1632 214196458752109430L, 1633 6458513309998070914L, 1634 2665048360156607904L, 1635 96698248584467992L, 1636 -3238403026096269033L, 1637 6759639479763272920L, 1638 -4231971627796170796L, 1639 -2149574977639731179L, 1640 -1437035755788460036L, 1641 -6000005629185669767L, 1642 145244292800946348L, 1643 -3056352941404947199L, 1644 3748284277779018970L, 1645 7328354565489106580L, 1646 -2176895260373660284L, 1647 3077983936372755601L, 1648 1215485830019410079L, 1649 683050801367331140L, 1650 -3173237622987755212L, 1651 -1951990779107873701L, 1652 -4714366021269652421L, 1653 4934690664256059008L, 1654 1674823104333774474L, 1655 -3974408282362828040L, 1656 2001478896492417760L, 1657 -4115105568354384199L, 1658 -2039694725495941666L, 1659 -587763432329933431L, 1660 -391276713546911316L, 1661 -5543400904809469053L, 1662 1882564440421402418L, 1663 -4991793588968693036L, 1664 3454088185914578321L, 1665 2290855447126188424L, 1666 3027910585026909453L, 1667 2136873580213167431L, 1668 -6243562989966916730L, 1669 5887939953208193029L, 1670 -3491821629467655741L, 1671 -3138303216306660662L, 1672 8572629205737718669L, 1673 4154439973110146459L, 1674 5542921963475106759L, 1675 -2025215496720103521L, 1676 -4047933760493641640L, 1677 -169455456138383823L, 1678 -1164572689128024473L, 1679 -8551078127234162906L, 1680 -7247713218016599028L, 1681 8725299775220778242L, 1682 6263466461599623132L, 1683 7931568057263751768L, 1684 7365493014712655238L, 1685 -7343740914722477108L, 1686 8294118602089088477L, 1687 7677867223984211483L, 1688 -7052188421655969232L, 1689 -3739992520633991431L, 1690 772835781531324307L, 1691 881441588914692737L, 1692 6321450879891466401L, 1693 5682516032668315027L, 1694 8493068269270840662L, 1695 -3895212467022280567L, 1696 -3241911302335746277L, 1697 -7199586338775635848L, 1698 -4606922569968527974L, 1699 -806850906331637768L, 1700 2433670352784844513L, 1701 -5787982146811444512L, 1702 7852193425348711165L, 1703 8669396209073850051L, 1704 -6898875695148963118L, 1705 6523939610287206782L, 1706 -8084962379210153174L, 1707 8159432443823995836L, 1708 -2631068535470883494L, 1709 -338649779993793113L, 1710 6514650029997052016L, 1711 3926259678521802094L, 1712 5443275905907218528L, 1713 7312187582713433551L, 1714 -2993773587362997676L, 1715 -1068335949405953411L, 1716 4499730398606216151L, 1717 8538015793827433712L, 1718 -4057209365270423575L, 1719 -1504284818438273559L, 1720 -6460688570035010846L, 1721 1765077117408991117L, 1722 8278320303525164177L, 1723 8510128922449361533L, 1724 1305722765578569816L, 1725 7250861238779078656L, 1726 -576624504295396147L, 1727 -4363714566147521011L, 1728 -5932111494795524073L, 1729 1837387625936544674L, 1730 -4186755953373944712L, 1731 -7657073597826358867L, 1732 140408487263951108L, 1733 5578463635002659628L, 1734 3400326044813475885L, 1735 -6092804808386714986L, 1736 -2410324417287268694L, 1737 3222007930183458970L, 1738 4932471983280850419L, 1739 3554114546976144528L, 1740 -7216067928362857082L, 1741 -6115289896923351748L, 1742 -6769646077108881947L, 1743 4263895947722578066L, 1744 2939136721007694271L, 1745 1426030606447416658L, 1746 -1316192446807442076L, 1747 5366182640480055129L, 1748 6527003877470258527L, 1749 5849680119000207603L, 1750 5263993237214222328L, 1751 -6936533648789185663L, 1752 -9063642143790846605L, 1753 3795892210758087672L, 1754 4987213125282940176L, 1755 2505500970421590750L, 1756 -1014022559552365387L, 1757 -3574736245968367770L, 1758 1180676507127340259L, 1759 -2261908445207512503L, 1760 -8416682633172243509L, 1761 1114990703652673283L, 1762 7753746660364401380L, 1763 1874908722469707905L, 1764 2033421444403047677L, 1765 21412168602505589L, 1766 385957952615286205L, 1767 2053171460074727107L, 1768 1915131899400103774L, 1769 6680879515029368390L, 1770 568807208929724162L, 1771 -6211541450459087674L, 1772 -5026690733412145448L, 1773 1384781941404886235L, 1774 -98027820852587266L, 1775 1806580495924249669L, 1776 6322077317403503963L, 1777 9078162931419569939L, 1778 -2809061215428363978L, 1779 7697867577577415733L, 1780 -5270063855897737274L, 1781 5649864555290587388L, 1782 -6970990547695444247L, 1783 579684606137331754L, 1784 3871931565451195154L, 1785 2030008578322050218L, 1786 -5012357307111799829L, 1787 -2271365921756144065L, 1788 4551962665158074190L, 1789 -3385474923040271312L, 1790 -7647625164191633577L, 1791 6634635380316963029L, 1792 -5201190933687061585L, 1793 8864818738548593973L, 1794 2855828214210882907L, 1795 9154512990734024165L, 1796 -6945306719789457786L, 1797 1200243352799481087L, 1798 875998327415853787L, 1799 1275313054449881011L, 1800 -6105772045375948736L, 1801 -2926927684328291437L, 1802 9200050852144954779L, 1803 5188726645765880663L, 1804 5197037323312705176L, 1805 3434926231010121611L, 1806 -5054013669361906544L, 1807 2582959199749224670L, 1808 -6053757512723474059L, 1809 -5016308176846054473L, 1810 -2509827316698626133L, 1811 7700343644503853204L, 1812 -1997627249894596731L, 1813 3993168688325352290L, 1814 -8181743677541277704L, 1815 3719056119682565597L, 1816 -7264411659282947790L, 1817 7177028972346484464L, 1818 -5460831176884283278L, 1819 1799904662416293978L, 1820 -6549616005092764514L, 1821 5472403994001122052L, 1822 8683463751708388502L, 1823 -7873363037838316398L, 1824 689134758256487260L, 1825 -1287443614028696450L, 1826 4452712919702709507L, 1827 762909374167538893L, 1828 6594302592326281411L, 1829 1183786629674781984L, 1830 5021847859620133476L, 1831 -2490098069181538915L, 1832 5105145136026716679L, 1833 4437836948098585718L, 1834 1987270426215858862L, 1835 6170312798826946249L, 1836 634297557126003407L, 1837 -1672811625495999581L, 1838 6282971595586218191L, 1839 4549149305727581687L, 1840 -5652165370435317782L, 1841 1064501550023753890L, 1842 -5334885527127139723L, 1843 -6904378001629481237L, 1844 -1807576691784201230L, 1845 -205688432992053911L, 1846 7621619053293393289L, 1847 6258649161313982470L, 1848 -1111634238359342096L, 1849 -8044260779481691987L, 1850 400270655839010807L, 1851 -7806833581382890725L, 1852 -2970563349459508036L, 1853 -7392591524816802798L, 1854 2918924613160219805L, 1855 -6444161627929149002L, 1856 6096497501321778876L, 1857 -1477975665655830038L, 1858 1690651307597306138L, 1859 -2364076888826085362L, 1860 -6521987420014905821L, 1861 -4419193480146960582L, 1862 3538587780233092477L, 1863 8374665961716940404L, 1864 7492412312405424500L, 1865 6311662249091276767L, 1866 -1240235198282023566L, 1867 5478559631401166447L, 1868 3476714419313462133L, 1869 377427285984503784L, 1870 2570472638778991109L, 1871 -2741381313777447835L, 1872 -7123472905503039596L, 1873 2493658686946955193L, 1874 1024677789035847585L, 1875 -2916713904339582981L, 1876 -4532003852004642304L, 1877 -2202143560366234111L, 1878 5832267856442755135L, 1879 -261740607772957384L, 1880 239435959690278014L, 1881 5755548341947719409L, 1882 6138795458221887696L, 1883 -7709506987360146385L, 1884 -6657487758065140444L, 1885 -7006376793203657499L, 1886 6544409861846502033L, 1887 3171929352014159247L, 1888 1051041925048792869L, 1889 2617300158375649749L, 1890 952652799620095175L, 1891 -576661730162168147L, 1892 -1634191369221345988L, 1893 4833656816115993519L, 1894 647566759700005786L, 1895 2473810683785291822L, 1896 3005977181064745326L, 1897 -3321881966853149523L, 1898 7595337666427588699L, 1899 6004093624251057224L, 1900 -563917505657690279L, 1901 6117428527147449302L, 1902 -6287297509522976113L, 1903 -4527219334756214406L, 1904 742626429298092489L, 1905 3057351806086972041L, 1906 645967551210272605L, 1907 -4428701157828864227L, 1908 3236379103879435414L, 1909 -8477089892132066300L, 1910 -6127365537275859058L, 1911 -4052490484706946358L, 1912 -8004854976625046469L, 1913 -3679456917426613424L, 1914 -8212793762082595299L, 1915 -818288739465424130L, 1916 1358812099481667095L, 1917 7835987612195254310L, 1918 -3663247409614323059L, 1919 -2931105150130396604L, 1920 7296136776835614792L, 1921 -2014557408985889628L, 1922 7267662411237959788L, 1923 3699280615819277743L, 1924 -212010675469091396L, 1925 -6518374332458360120L, 1926 145026010541628849L, 1927 1879297324213501001L, 1928 -7146296067751816833L, 1929 -5002958800391379931L, 1930 6060682439924517608L, 1931 -432234782921170964L, 1932 -6669688947353256956L, 1933 7728943532792041267L, 1934 830911367341171721L, 1935 3396934884314289432L, 1936 -779464156662780749L, 1937 2330041851883352285L, 1938 -4783350380736276693L, 1939 -5758476056890049254L, 1940 -7551552301614791791L, 1941 1253334187723911710L, 1942 -2685018208308798978L, 1943 5379636036360946454L, 1944 6154668487114681217L, 1945 -8641287462255458898L, 1946 4676087643800649558L, 1947 -2405142641398691475L, 1948 1088685126864246881L, 1949 6431149082338374041L, 1950 -607357695335069155L, 1951 -720970692129524140L, 1952 2648766932394044468L, 1953 8408344790179354573L, 1954 -6193808387735667350L, 1955 7722524628524697419L, 1956 -6975433852560238120L, 1957 -2925851029234475295L, 1958 -4274458387165211028L, 1959 -8355836377702147319L, 1960 5278146397877332061L, 1961 8502098812383680707L, 1962 2292836642336580326L, 1963 -6127608082651070062L, 1964 2222301962240611208L, 1965 -1930887695854799378L, 1966 7640503480494894592L, 1967 1162652186586436094L, 1968 -1918002592943761683L, 1969 7648998601717261840L, 1970 -8472603250832757057L, 1971 -988877663117552456L, 1972 2368458128168026494L, 1973 -6480813811998475245L, 1974 -5896967824416018967L, 1975 -2593783161701820446L, 1976 6950098417530252598L, 1977 6362589545555771236L, 1978 7981389665448567125L, 1979 3954017080198558850L, 1980 1626078615050230622L, 1981 6650159066527969109L, 1982 697345338922935394L, 1983 -1226816215461768626L, 1984 8740408765973837440L, 1985 -4194155864629568323L, 1986 7016680023232424746L, 1987 6043281358142429469L, 1988 -4201005667174376809L, 1989 1216727117859013155L, 1990 6367202436544203935L, 1991 35414869396444636L, 1992 3715622794033998412L, 1993 488654435687670554L, 1994 -2503747297224687460L, 1995 3147101919441470388L, 1996 -8248611218693190922L, 1997 970697264481229955L, 1998 3411465763826851418L, 1999 9117405004661599969L, 2000 -5204346498331519734L, 2001 -19637460819385174L, 2002 -5039124225167977219L, 2003 2990108874601696668L, 2004 -2623857460235459202L, 2005 4256291692861397446L, 2006 6724147860870760443L, 2007 3558616688507246537L, 2008 6487680097936412800L, 2009 -6470792832935928161L, 2010 4314814550912237614L, 2011 -1292878983006062345L, 2012 6791915152630414174L, 2013 5971652079925815310L, 2014 2557529546662864312L, 2015 466175054322801580L, 2016 -585216717310746872L, 2017 -2486640422147349036L, 2018 7212029603994220134L, 2019 3958995069888972500L, 2020 4950471855791412790L, 2021 -3721948842035712763L, 2022 -6184503487488243051L, 2023 4079570444585775332L, 2024 -3952156172546996872L, 2025 4543894231118208322L, 2026 -1739995588466209963L, 2027 9155948355455935530L, 2028 5821980345462207860L, 2029 -2431287667309520417L, 2030 -3890108130519441316L, 2031 -558124689277030490L, 2032 6079823537335801717L, 2033 5409742395192364262L, 2034 -2329885777717160453L, 2035 -7332804342513677651L, 2036 1466490574975950555L, 2037 -420549419907427929L, 2038 -5249909814389692516L, 2039 -5145692168206210661L, 2040 5934113980649113921L, 2041 3241618428555359661L, 2042 -6622110266160980250L, 2043 5048250878669516223L, 2044 5747219637359976174L, 2045 2975906212588223728L, 2046 5730216838646273215L, 2047 -176713127129024690L, 2048 6734624279336671146L, 2049 5127866734316017180L, 2050 7111761230887705595L, 2051 3457811808274317235L, 2052 3362961434604932375L, 2053 -1877869936854991246L, 2054 7171428594877765665L, 2055 -8252167178400462374L, 2056 -6306888185035821047L, 2057 -6684702191247683887L, 2058 -7754928454824190529L, 2059 -1902605599135704386L, 2060 -4037319846689421239L, 2061 8493746058123583457L, 2062 -8156648963857047193L, 2063 2051510355149839497L, 2064 -1256416624177218909L, 2065 -3344927996254072010L, 2066 -1838853051925943568L, 2067 316927471680974556L, 2068 -1502257066700798003L, 2069 -5836095610125837606L, 2070 -1594125583615895424L, 2071 1442211486559637962L, 2072 -144295071206619569L, 2073 5159850900959273410L, 2074 4589139881166423678L, 2075 -7038726987463097509L, 2076 2886082400772974595L, 2077 2780759114707171916L, 2078 5694649587906297495L, 2079 1260349041268169667L, 2080 4921517488271434890L, 2081 644696475796073018L, 2082 6262811963753436289L, 2083 -6128198676595868773L, 2084 -3625352083004760261L, 2085 -8751453332943236675L, 2086 8749249479868749221L, 2087 -2450808199545048250L, 2088 -6517435817046180917L, 2089 -3433321727429234998L, 2090 -2591586258908763451L, 2091 3847750870868804507L, 2092 6603614438546398643L, 2093 -7598682191291031287L, 2094 8710261565627204971L, 2095 4753389483755344355L, 2096 -4645333069458786881L, 2097 -6742695046613492214L, 2098 643070478568866643L, 2099 -7543096104151965610L, 2100 7171495384655926161L, 2101 595063872610714431L, 2102 3292310150781130424L, 2103 4326847806055440904L, 2104 -4580020566072794152L, 2105 3142286571820373678L, 2106 5530356537440155930L, 2107 546372639737516181L, 2108 7401214477400367500L, 2109 7406531960402873109L, 2110 3287639667219172570L, 2111 4977301681213633671L, 2112 5253257820925174498L, 2113 2906216636104297878L, 2114 6142955758238347523L, 2115 -3498651268741727235L, 2116 -5875053958265588593L, 2117 3896719087169993883L, 2118 -910904726885775073L, 2119 380107493197368177L, 2120 -4993591912695447004L, 2121 2970487257212582761L, 2122 2551762717569548774L, 2123 953061649962736812L, 2124 8949739538606589463L, 2125 -2962839167079475801L, 2126 -1375673191272573835L, 2127 3761793818361866390L, 2128 -389577789190726878L, 2129 5661262051502180269L, 2130 -6558556411143987683L, 2131 -702798336372315031L, 2132 -336662820551371779L, 2133 998576401126580155L, 2134 -5945021269112582755L, 2135 6108533925730179871L, 2136 2207095297001999618L, 2137 -9042779159998880435L, 2138 -6177868444342118372L, 2139 6775965402605895077L, 2140 -3788428885163306576L, 2141 7790055010527190387L, 2142 3581587652196995358L, 2143 -6176354155561607694L, 2144 -5859381340906321207L, 2145 395898765763528395L, 2146 8132967590863909348L, 2147 -3329092504090544483L, 2148 -6785855381158040247L, 2149 1497218517051796750L, 2150 -5352392845588925911L, 2151 -6271364901230559194L, 2152 2314830370653350118L, 2153 -7617588269001325450L, 2154 1423166885758213795L, 2155 8538612578307869519L, 2156 -61918791718295474L, 2157 -8177103503192338593L, 2158 -4740086042584326695L, 2159 3677931948215558698L, 2160 6558856291580149558L, 2161 2674975452453336335L, 2162 5133796555646930522L, 2163 5139252693299337100L, 2164 7949476871295347205L, 2165 4407815324662880678L, 2166 -3758305875280581215L, 2167 6066309507576587415L, 2168 -7368508486398350973L, 2169 -3181640264332856492L, 2170 6905100869343314145L, 2171 3677177673848733417L, 2172 8862933624870506941L, 2173 -8575223195813810568L, 2174 9178470351355678144L, 2175 4677809017145408358L, 2176 -1194833416287894989L, 2177 3436364743255571183L, 2178 -5204770725795363579L, 2179 560599448536335263L, 2180 -3192077522964776200L, 2181 -751575299648803575L, 2182 6334581746534596579L, 2183 -8358187891202563300L, 2184 -1462480609823525055L, 2185 5605961062646987941L, 2186 4968399805931440889L, 2187 7968693270782626653L, 2188 -5868205923557518188L, 2189 1830234928743560617L, 2190 -8435261076693154407L, 2191 2138416970728681332L, 2192 8088740745199685138L, 2193 806532400344230520L, 2194 1800590379902909333L, 2195 -8909128842071238901L, 2196 -7357495566969170860L, 2197 3679766664126940553L, 2198 2060050474865839094L, 2199 2363972840121763414L, 2200 525695004292982714L, 2201 -1224842191746529593L, 2202 7011317848855545003L, 2203 -6337167558180299938L, 2204 -5184688833363785939L, 2205 -8426673387248359061L, 2206 -5035438815930785229L, 2207 3521810320608058994L, 2208 4803742557254962242L, 2209 6623527039545786598L, 2210 -1221475882122634738L, 2211 -3344794405518401087L, 2212 6510298498414053658L, 2213 2844753907937720338L, 2214 90502309714994895L, 2215 -750403235344282494L, 2216 -4825474181021465833L, 2217 -3405519947983849510L, 2218 3503875590944089793L, 2219 7286294700691822468L, 2220 7828126881500292486L, 2221 8437899353709338096L, 2222 136052254470293480L, 2223 1113259077339995086L, 2224 -8244887265606191121L, 2225 8089569503800461649L, 2226 -1429698194850157567L, 2227 1575595674002364989L, 2228 3576095286627428675L, 2229 -7653655285807569222L, 2230 -6053506977362539111L, 2231 -3923855345805787169L, 2232 -8001149080454232377L, 2233 -4382867706931832271L, 2234 4212860258835896297L, 2235 4207674254247034014L, 2236 5519424058779519159L, 2237 -754483042161434654L, 2238 1434113479814210082L, 2239 -6416645032698336896L, 2240 5624329676066514819L, 2241 -8229557208322175959L, 2242 3922640911653270376L, 2243 7826932478782081910L, 2244 -4862787164488635842L, 2245 1449234668827944573L, 2246 -1781657689570106327L, 2247 5442827552725289699L, 2248 3589862161007644641L, 2249 4787115581650652778L, 2250 -3512152721942525726L, 2251 -6750103117958685206L, 2252 5012970446659949261L, 2253 6797752795961689017L, 2254 5086454597639943700L, 2255 -7616068364979994076L, 2256 1492846825433110217L, 2257 2967476304433704510L, 2258 -8413824338284112078L, 2259 -1319049442043273974L, 2260 -1756090916806844109L, 2261 -9061091728950139525L, 2262 -6864767830358160810L, 2263 4879532090226251157L, 2264 5528644708740739488L 2265 }; 2266 } 2267