It seems like something is going wrong with the snow-making process. Instead of forming snow, the water that’s been absorbed into the air seems to be forming hail!
Maybe there’s something you can do to break up the hailstones?
Due to strong, probably-magical winds, the hailstones are all flying through the air in perfectly linear trajectories. You make a note of each hailstone’s position and velocity (your puzzle input). For example:
19, 13, 30 @ -2, 1, -2
18, 19, 22 @ -1, -1, -2
20, 25, 34 @ -2, -2, -4
12, 31, 28 @ -1, -2, -1
20, 19, 15 @ 1, -5, -3
Each line of text corresponds to the position and velocity of a single hailstone. The positions indicate where the hailstones are right now (at time 0). The velocities are constant and indicate exactly how far each hailstone will move in one nanosecond.
Each line of text uses the format px py pz @ vx vy vz. For instance, the hailstone specified by 20, 19, 15 @ 1, -5, -3 has initial X position 20, Y position 19, Z position 15, X velocity 1, Y velocity -5, and Z velocity -3. After one nanosecond, the hailstone would be at 21, 14, 12.
Perhaps you won’t have to do anything. How likely are the hailstones to collide with each other and smash into tiny ice crystals?
To estimate this, consider only the X and Y axes; ignore the Z axis. Looking forward in time, how many of the hailstones’ paths will intersect within a test area? (The hailstones themselves don’t have to collide, just test for intersections between the paths they will trace.)
In this example, look for intersections that happen with an X and Y position each at least 7 and at most 27; in your actual data, you’ll need to check a much larger test area. Comparing all pairs of hailstones’ future paths produces the following results:
Hailstone A: 19, 13, 30 @ -2, 1, -2
Hailstone B: 18, 19, 22 @ -1, -1, -2
Hailstones' paths will cross inside the test area (at x=14.333, y=15.333).
Hailstone A: 19, 13, 30 @ -2, 1, -2
Hailstone B: 20, 25, 34 @ -2, -2, -4
Hailstones' paths will cross inside the test area (at x=11.667, y=16.667).
Hailstone A: 19, 13, 30 @ -2, 1, -2
Hailstone B: 12, 31, 28 @ -1, -2, -1
Hailstones' paths will cross outside the test area (at x=6.2, y=19.4).
Hailstone A: 19, 13, 30 @ -2, 1, -2
Hailstone B: 20, 19, 15 @ 1, -5, -3
Hailstones' paths crossed in the past for hailstone A.
Hailstone A: 18, 19, 22 @ -1, -1, -2
Hailstone B: 20, 25, 34 @ -2, -2, -4
Hailstones' paths are parallel; they never intersect.
Hailstone A: 18, 19, 22 @ -1, -1, -2
Hailstone B: 12, 31, 28 @ -1, -2, -1
Hailstones' paths will cross outside the test area (at x=-6, y=-5).
Hailstone A: 18, 19, 22 @ -1, -1, -2
Hailstone B: 20, 19, 15 @ 1, -5, -3
Hailstones' paths crossed in the past for both hailstones.
Hailstone A: 20, 25, 34 @ -2, -2, -4
Hailstone B: 12, 31, 28 @ -1, -2, -1
Hailstones' paths will cross outside the test area (at x=-2, y=3).
Hailstone A: 20, 25, 34 @ -2, -2, -4
Hailstone B: 20, 19, 15 @ 1, -5, -3
Hailstones' paths crossed in the past for hailstone B.
Hailstone A: 12, 31, 28 @ -1, -2, -1
Hailstone B: 20, 19, 15 @ 1, -5, -3
Hailstones' paths crossed in the past for both hailstones.
So, in this example, 2 hailstones’ future paths cross inside the boundaries of the test area.
However, you’ll need to search a much larger test area if you want to see if any hailstones might collide. Look for intersections that happen with an X and Y position each at least 200000000000000 and at most 400000000000000. Disregard the Z axis entirely.
Considering only the X and Y axes, check all pairs of hailstones’ future paths for intersections. How many of these intersections occur within the test area?
type Point struct {
x, y float64
}
type Hailstone struct {
px, py, pz float64
vx, vy, vz float64
}
func parseInput(filename string) []Hailstone {
file, err := os.Open(filename)
if err != nil {
return []Hailstone{}
}
defer file.Close()
var hailstones []Hailstone
scanner := bufio.NewScanner(file)
for scanner.Scan() {
line := scanner.Text()
var h Hailstone
parts := strings.Split(line, " @ ")
fmt.Sscanf(parts[0], "%f, %f, %f", &h.px, &h.py, &h.pz)
fmt.Sscanf(parts[1], "%f, %f, %f", &h.vx, &h.vy, &h.vz)
hailstones = append(hailstones, h)
}
return hailstones
}
func findIntersection(h1, h2 Hailstone) (Point, bool) {
determinant := h1.vx*h2.vy - h1.vy*h2.vx
if determinant == 0 {
return Point{}, false
}
t := ((h2.px-h1.px)*h2.vy - (h2.py-h1.py)*h2.vx) / determinant
x := h1.px + t*h1.vx
y := h1.py + t*h1.vy
if t < 0 {
return Point{}, false
}
s := (x - h2.px) / h2.vx
if s < 0 {
return Point{}, false
}
return Point{x, y}, true
}
func main() {
hailstones := parseInput("input.txt")
const min float64 = 200000000000000
const max float64 = 400000000000000
count := 0
for i := 0; i < len(hailstones); i++ {
for j := i + 1; j < len(hailstones); j++ {
if point, intersects := findIntersection(hailstones[i], hailstones[j]); intersects {
if point.x >= min && point.x <= max && point.y >= min && point.y <= max {
count++
}
}
}
}
fmt.Printf("Number of intersections within test area: %d\n", count)
}
Upon further analysis, it doesn’t seem like any hailstones will naturally collide. It’s up to you to fix that!
You find a rock on the ground nearby. While it seems extremely unlikely, if you throw it just right, you should be able to hit every hailstone in a single throw!
You can use the probably-magical winds to reach any integer position you like and to propel the rock at any integer velocity. Now including the Z axis in your calculations, if you throw the rock at time 0, where do you need to be so that the rock perfectly collides with every hailstone? Due to probably-magical inertia, the rock won’t slow down or change direction when it collides with a hailstone.
In the example above, you can achieve this by moving to position 24, 13, 10 and throwing the rock at velocity -3, 1, 2. If you do this, you will hit every hailstone as follows:
Hailstone: 19, 13, 30 @ -2, 1, -2
Collision time: 5
Collision position: 9, 18, 20
Hailstone: 18, 19, 22 @ -1, -1, -2
Collision time: 3
Collision position: 15, 16, 16
Hailstone: 20, 25, 34 @ -2, -2, -4
Collision time: 4
Collision position: 12, 17, 18
Hailstone: 12, 31, 28 @ -1, -2, -1
Collision time: 6
Collision position: 6, 19, 22
Hailstone: 20, 19, 15 @ 1, -5, -3
Collision time: 1
Collision position: 21, 14, 12
Above, each hailstone is identified by its initial position and its velocity. Then, the time and position of that hailstone’s collision with your rock are given.
After 1 nanosecond, the rock has exactly the same position as one of the hailstones, obliterating it into ice dust! Another hailstone is smashed to bits two nanoseconds after that. After a total of 6 nanoseconds, all of the hailstones have been destroyed.
So, at time 0, the rock needs to be at X position 24, Y position 13, and Z position 10. Adding these three coordinates together produces 47. (Don’t add any coordinates from the rock’s velocity.)
Determine the exact position and velocity the rock needs to have at time 0 so that it perfectly collides with every hailstone. What do you get if you add up the X, Y, and Z coordinates of that initial position?
type Hailstone struct {
px, py, pz float64
vx, vy, vz float64
}
func parseInput(filename string) []Hailstone {
file, err := os.Open(filename)
if err != nil {
return []Hailstone{}
}
defer file.Close()
var hailstones []Hailstone
scanner := bufio.NewScanner(file)
for scanner.Scan() {
line := scanner.Text()
var h Hailstone
parts := strings.Split(line, " @ ")
fmt.Sscanf(parts[0], "%f, %f, %f", &h.px, &h.py, &h.pz)
fmt.Sscanf(parts[1], "%f, %f, %f", &h.vx, &h.vy, &h.vz)
hailstones = append(hailstones, h)
}
return hailstones
}
func solve(hailstones []Hailstone) int {
var possibleRockVelX, possibleRockVelY, possibleRockVelZ []int
for i, hs1 := range hailstones {
for _, hs2 := range hailstones[i+1:] {
if hs1.vx == hs2.vx {
possibilities := getPossibleVelocities(int(hs2.px), int(hs1.px), int(hs1.vx))
if len(possibleRockVelX) == 0 {
possibleRockVelX = possibilities
} else {
possibleRockVelX = getIntersection(possibleRockVelX, possibilities)
}
}
if hs1.vy == hs2.vy {
possibilities := getPossibleVelocities(int(hs2.py), int(hs1.py), int(hs1.vy))
if len(possibleRockVelY) == 0 {
possibleRockVelY = possibilities
} else {
possibleRockVelY = getIntersection(possibleRockVelY, possibilities)
}
}
if hs1.vz == hs2.vz {
possibilities := getPossibleVelocities(int(hs2.pz), int(hs1.pz), int(hs1.vz))
if len(possibleRockVelZ) == 0 {
possibleRockVelZ = possibilities
} else {
possibleRockVelZ = getIntersection(possibleRockVelZ, possibilities)
}
}
}
}
if len(possibleRockVelX) == 1 && len(possibleRockVelY) == 1 && len(possibleRockVelZ) == 1 {
rockVelX := float64(possibleRockVelX[0])
rockVelY := float64(possibleRockVelY[0])
rockVelZ := float64(possibleRockVelZ[0])
hailstone1, hailstone2 := hailstones[0], hailstones[1]
slope1 := (hailstone1.vy - rockVelY) / (hailstone1.vx - rockVelX)
slope2 := (hailstone2.vy - rockVelY) / (hailstone2.vx - rockVelX)
intercept1 := hailstone1.py - (slope1 * hailstone1.px)
intercept2 := hailstone2.py - (slope2 * hailstone2.px)
rockPosX := (intercept2 - intercept1) / (slope1 - slope2)
rockPosY := slope1*rockPosX + intercept1
time := (rockPosX - hailstone1.px) / (hailstone1.vx - rockVelX)
rockPosZ := hailstone1.pz + (hailstone1.vz-rockVelZ)*time
return int(rockPosX + rockPosY + rockPosZ)
}
return 0
}
func getPossibleVelocities(pos1, pos2 int, vel int) []int {
match := []int{}
for possibleVel := -1000; possibleVel < 1000; possibleVel++ {
if possibleVel != vel && (pos1-pos2)%(possibleVel-vel) == 0 {
match = append(match, possibleVel)
}
}
return match
}
func getIntersection(slice1, slice2 []int) []int {
result := []int{}
valueMap := map[int]bool{}
for _, value := range slice2 {
valueMap[value] = true
}
for _, value := range slice1 {
if valueMap[value] {
result = append(result, value)
}
}
return result
}
func main() {
hailstones := parseInput("input.txt")
fmt.Println(solve(hailstones))
}
Links
Click to show the input
147847636573416, 190826994408605, 140130741291716 @ 185, 49, 219 287509258905812, 207449079739538, 280539021150559 @ -26, 31, 8 390970075767404, 535711685410735, 404166182422876 @ -147, -453, -149 306391780523937, 382508967958270, 264612201472049 @ -24, -274, 28 278063616684570, 510959526404728, 288141792965603 @ -18, -441, -6 247862847874155, 518262698181307, 103757008598594 @ 28, -489, 417 309088232168881, 518439101394981, 327968576316109 @ -120, -493, -112 289970722781988, 392465652122173, 259795401258443 @ -151, -81, 74 230223985474398, 35863480523764, 277969238912399 @ 59, 178, 13 216716914470214, 397396129688172, 68669738590683 @ 138, -100, 829 296851714870622, 285896914754978, 138395552373313 @ -57, -37, 265 273110262632430, 368505433732732, 253899514195619 @ -109, 83, 112 260174866051854, 402391804119998, 300158970414806 @ -49, -74, -105 325436822413170, 421983714598402, 247172245636049 @ -167, -257, 85 252281728989270, 476980133762212, 342477467601359 @ -75, -494, -649 338600765546460, 550770620321170, 411573056556593 @ -198, -577, -323 294085917277254, 33268063188280, 127869181817651 @ -11, 99, 174 335531167298218, 183184739609991, 368731477249318 @ -45, -91, -73 267703225160407, 445230864886582, 262482828912995 @ -186, -210, 114 339694972888821, 322707062288083, 484395005928779 @ -86, -173, -262 200387611591150, 401709185732432, 40246757417119 @ 127, -235, 493 263547967438298, 153079306194867, 257003350697599 @ 19, 5, 38 311740422496906, 380202359303744, 284280966836487 @ -240, -29, -23 326619626826715, 129432579477502, 311085273747489 @ -42, -18, -20 139847472501998, 49629966993476, 199065986486195 @ 183, 203, 120 319271548112989, 98343505044765, 123884333663745 @ -60, 131, 220 257236313576220, 244137919924884, 288564296941044 @ 17, 16, -7 239319225684810, 414577431892772, 282153566338659 @ 50, -26, -38 253448094666470, 413754896239052, 288959254056474 @ -201, 536, -253 356289721674166, 315669249634508, 237109178067363 @ -92, -184, 62 215515055132304, 325595633773036, 269696659655816 @ 109, -8, 29 215444235966838, 214893623437328, 94262935571621 @ 75, -74, 225 217285761085222, 234506001314422, 52102333028740 @ 103, 210, 571 325589917407024, 261829042562024, 347197719693097 @ -184, 182, -179 267471726048930, 536391639375988, 227804886677719 @ -28, -558, 143 266329227773105, 415207750633562, 240460453500014 @ -98, -98, 201 331883852035187, 82290050581148, 199467230944283 @ -42, 8, 90 313129632104559, 99213874360918, 308301981948791 @ -30, 22, -18 300425936932986, 242692707024584, 235477005752739 @ -79, 98, 98 145686890074182, 218401239860584, 144551755991035 @ 281, 249, 340 254128723566594, 211968796627628, 303807266512611 @ 20, 112, -38 248115956527650, 443159022182044, 124078443016167 @ 32, -324, 287 371288573973166, 197074915783274, 151713457275241 @ -81, -101, 137 213336389044518, 207831441327316, 217210181430107 @ 134, 481, 205 296418816410964, 350718419863150, 460683167996103 @ -160, 51, -664 274166084571550, 556394033227340, 312642495146803 @ -18, -536, -55 148786581031767, 143970816967726, 272281093340648 @ 206, 198, 21 253902263577281, 518911639175591, 161544912640287 @ -32, -671, 646 221520853664100, 322202853952340, 307428891339424 @ 77, -128, -37 323926326188532, 107117980535962, 281397075693395 @ -44, 25, 10 229456991678840, 330867298124852, 223159063494579 @ 94, 244, 250 288176911900746, 243535784382202, 245752060548968 @ -61, 130, 81 253107734690230, 136776483854242, 175863410203349 @ 27, 129, 165 294695660104770, 341464723212292, 316167280607387 @ -138, 50, -124 330211753118286, 240673058582572, 251503251874531 @ -142, 105, 65 272990612776169, 108422276429367, 275793957475713 @ 10, 35, 16 304595434172432, 216516999740500, 277951114863024 @ -35, -48, 13 235115538584550, 392685127299436, 293797475708867 @ 62, -132, -46 248100495616540, 464759654025447, 99205581683799 @ 9, -367, 814 320232260020527, 180258179692249, 388221645556247 @ -46, -33, -114 251568249501706, 58236537481612, 294246800533235 @ 33, 120, -6 240494522391700, 257218814180002, 368508169974979 @ 46, -81, -110 242656108657926, 440970993048730, 278180121899069 @ -5, 39, -57 158569509691306, 110237112663132, 215754905076917 @ 139, 40, 84 226432768027391, 182852076414920, 202167051315687 @ 70, 124, 142 225570305295638, 253658809190232, 317199869397231 @ 69, -35, -49 390319761168066, 182862725967796, 377834468298899 @ -127, -36, -102 147391441522287, 48980781373024, 59412806099109 @ 146, 84, 248 179386359225410, 62875453970452, 17425856566584 @ 123, 144, 341 256809411323083, 439839475360034, 324710450924036 @ -182, -46, -663 254247143420730, 162776103669152, 518412124821159 @ 32, -49, -235 299824278999990, 145362064404727, 291016801459841 @ -73, 275, -16 272280605079290, 239054040894540, 343299591989473 @ -83, 536, -259 236282437401357, 420075275436520, 293316261185032 @ 104, 348, -299 269354081380734, 332605615472260, 298769675631743 @ -45, 46, -59 295845946126990, 242050305590192, 257425517530299 @ -41, -13, 44 279635993276616, 358775350972302, 329069654221933 @ 5, -250, -40 150600702453203, 260378919310735, 95686589783565 @ 196, -21, 316 422218514602688, 185766893487117, 353001819895607 @ -147, -65, -66 246874027515354, 382678223803792, 368215618182113 @ 9, 70, -485 245245548803220, 349043206004380, 273265581646927 @ 32, -48, 20 204109099658613, 249340190397430, 175443869155772 @ 98, -54, 159 338795636786142, 101911847254116, 246486534060299 @ -61, 34, 48 234850749126480, 391276545488532, 265494792105999 @ 62, -140, 44 252691516438614, 372448092477132, 288975284152211 @ -10, 40, -48 273397503298602, 211312940026125, 269191593947423 @ -37, 269, 30 330508539679350, 134444173179992, 399777117459259 @ -67, 53, -140 466676270508142, 265232480651404, 415935578924803 @ -204, -141, -139 240982820883025, 274071089605303, 233517618248384 @ 42, 411, 183 262438381888591, 353489617152245, 398443216471378 @ 10, -181, -185 259789438964660, 391813585283267, 348314511273169 @ -15, -139, -212 437351216503785, 538032191022152, 350433449089009 @ -196, -452, -76 275870225988312, 402339972856315, 281827541785112 @ -179, 21, -31 324930970943790, 388339682594068, 245605896063299 @ -193, -149, 98 253992740155705, 351667229548807, 353042405546519 @ -20, 165, -354 350135843048703, 203321436273936, 387508524300904 @ -94, -28, -127 271382800916635, 403901213938581, 378450900194082 @ -138, -13, -593 335617615257110, 336059381292132, 261281184662239 @ -51, -230, 31 308175516178757, 244416076183211, 443352347955969 @ -54, -37, -232 287259076388658, 130702108943536, 244372024331451 @ -46, 291, 76 272752868376252, 456078921405286, 247804235341517 @ -50, -339, 95 273162381941169, 128147987787659, 188963475327047 @ 14, -29, 102 299139503137472, 280086115330004, 245439097722953 @ -84, 44, 81 293631920431630, 370286848598272, 158838057794249 @ -113, -84, 360 260237398426422, 307174991425612, 257417448502235 @ -16, 120, 69 222292831294590, 287036978559404, 321730592859155 @ 92, 94, -105 278938201662814, 247721297839620, 294118009467027 @ -27, 47, -20 247333351618254, 139297502834356, 281574694281443 @ 39, -18, 10 238894145566514, 433421545287236, 298010697992879 @ 54, -118, -177 280300743594792, 147553978222285, 396596605156666 @ 5, -33, -109 199190835480535, 197363657590534, 355128145060209 @ 112, 66, -112 322627760846750, 63367054393958, 351689628318644 @ -33, 26, -57 264819549866694, 355360441100503, 198359763634358 @ -9, -119, 187 126412802644668, 244684697549502, 245106056981813 @ 200, -65, 57 262371184456084, 204019541174390, 420125365086491 @ 21, -62, -150 248352662165892, 423479279782570, 262410907589405 @ -22, -41, 111 366059477020491, 267049298648833, 401196587905201 @ -94, -141, -124 241154789915868, 411162343217962, 286274382477797 @ 38, -25, -61 231468455101898, 391427905444742, 324494665640907 @ 133, 385, -506 250331743410348, 211331317928176, 365332103568329 @ 36, -98, -77 331361563852260, 120697977349072, 262048969223189 @ -91, 156, 36 267191543373964, 291936753464290, 361494135567495 @ 10, -129, -100 253753592218080, 136615735747432, 396086234106544 @ 29, 60, -139 239416086526980, 409491280232032, 274677642967319 @ 50, 114, 12 296823086171385, 373705788753532, 307566281852369 @ -106, -120, -72 185911922936856, 318822091157329, 208731761238099 @ 113, -183, 98 253715733875148, 398289359474671, 275478061549580 @ -19, -53, 11 259267649003535, 203069322928532, 310233126996014 @ 26, -80, -21 262407482781262, 145119149011500, 362633119995779 @ 24, -37, -72 234703844953548, 128085787940626, 151057888192157 @ 53, 38, 164 286980955904080, 233844948302832, 213279902868869 @ -23, -20, 108 252339054895373, 183749771785998, 446184513524439 @ 28, 62, -242 260986291155732, 331163912947006, 312139773960887 @ -12, 7, -88 305239442402868, 203401764714478, 223300763971667 @ -46, 9, 90 293886503422211, 195361034982892, 531814198221545 @ -50, 120, -444 248431311390070, 435555833073372, 271535632534559 @ -27, -124, 39 301777096021112, 271308692547716, 269316674922043 @ -59, -32, 26 175453401496330, 208583624254720, 280427776078189 @ 147, 36, 8 244208133437000, 83023818569094, 362146618338425 @ 37, 494, -180 290778595507460, 162190156605495, 120201295317480 @ -23, 53, 229 308953121043126, 153657177222292, 268534582297343 @ -29, -20, 24 318682961068038, 185053683692416, 297098028239075 @ -35, -71, -6 332808188611182, 333245099279180, 305753352238755 @ -79, -184, -25 330573105000008, 190078438380960, 176941220983899 @ -84, 34, 158 297886641834058, 219862716113408, 192713349026129 @ -71, 134, 183 325337907466710, 414985552978276, 431934729405383 @ -173, -236, -388 357568408022260, 101022893807572, 89003057929519 @ -74, 12, 208 330116904234409, 228732668213246, 352409718441614 @ -74, -46, -87 236239020399547, 404672546198715, 342478234268388 @ 64, -77, -313 290768450596981, 343949192661507, 213810334830543 @ -92, -35, 182 237157879423918, 253411561421388, 277894917992387 @ 51, -37, 12 169397696131857, 27365575408159, 386388289844846 @ 124, 117, -105 307699040762670, 339545259993517, 307438138164284 @ -81, -127, -45 265919574687108, 438589146641034, 267877402928499 @ -124, -199, 58 283585738322310, 283034263623892, 317827080985499 @ -61, 84, -90 228055408019286, 218806877367724, 207693251771003 @ 65, 16, 120 375930559083652, 337846108011258, 438966488805369 @ -180, -151, -257 302656020338158, 279015798830700, 273435894533575 @ -65, -32, 19 369528839709486, 244231138416100, 311847866010227 @ -145, -36, -38 264086692272146, 310441094668233, 123720669799679 @ -21, 67, 438 186654449370991, 244093970259366, 386922652521707 @ 126, -34, -150 323152606960430, 50410115748652, 157242471605059 @ -33, 36, 130 255389060400420, 63020232233548, 327149369338145 @ 32, 24, -33 245933094666120, 407298013860472, 265960840637489 @ -46, 482, 139 316167769018642, 161640541637474, 312203306065525 @ -47, 11, -29 242908408378066, 448613070071919, 318735210774653 @ -5, -119, -720 153566779391472, 252819056610511, 115138646153367 @ 149, -111, 206 428037259058265, 357259686818023, 459651423564167 @ -168, -239, -194 400151219033974, 130696192672292, 414832188374243 @ -117, -20, -126 233499409784795, 463424369742617, 269355397093464 @ 78, -361, 41 210410474598830, 11115607559132, 443652231375219 @ 79, 133, -167 300407468144494, 112852915930448, 490609323158019 @ -65, 287, -382 329479320100580, 311048893826682, 340400545686419 @ -180, 25, -150 269848048936150, 333237978420692, 303779165917379 @ -50, 59, -78 266347743209517, 169857306425398, 308309223576299 @ 16, -18, -22 384509697761853, 273887110448308, 380773875944693 @ -216, -16, -176 223064805098350, 139937392368972, 346033864680259 @ 66, 8, -64 293199190333530, 375148421523652, 203880241746899 @ -78, -154, 182 327037557159765, 334343196256885, 557383490756282 @ -188, -13, -745 255908578447450, 334810794903643, 143970514124788 @ 27, -201, 179 197850793360182, 379411810310236, 196536069237803 @ 113, -228, 140 332416920056850, 93554866523608, 281800512008867 @ -48, 19, 10 371002389432664, 368405869911512, 325897150986291 @ -216, -170, -86 264221490933406, 144061147648436, 399660347978923 @ -41, 788, -434 316613090780574, 216046847247380, 203782524627043 @ -115, 161, 166 300833451825192, 376882908844792, 371209528658147 @ -144, -90, -286 346607746935555, 167696071874507, 311539950690944 @ -64, -53, -21 262892637145905, 346923169579627, 272146582100429 @ -28, 17, 24 281909479751880, 294609251298532, 250171709772869 @ -22, -84, 57 260281289791398, 428292153960136, 271737852888995 @ -171, 11, 42 274906758852930, 276717585265792, 318245904145199 @ -38, 91, -89 252246261128110, 410977350792012, 284507465456579 @ -35, -17, -51 523880257870382, 483625067625436, 527139983237139 @ -329, -387, -317 382009975265108, 387942234291617, 294764481103099 @ -227, -215, -22 245870528118920, 275511369942209, 289894863314733 @ 37, -53, -8 241757900357209, 349277192802512, 317727876619591 @ 34, 380, -266 265574267267051, 349669587055360, 278436813391657 @ -174, 612, -20 287671907390664, 240166463416222, 265736164310489 @ -40, 45, 33 262294731540923, 288492804012613, 274443808840405 @ -54, 423, 16 341025141594909, 344725222007974, 269795467926029 @ -194, -78, 28 336111807780066, 482343699277480, 399597277678799 @ -210, -411, -317 262708301379702, 437632218143700, 264500061720803 @ -40, -263, 54 224676612010162, 381362147807220, 194829885125912 @ 75, -208, 165 265207446370596, 355870309106519, 334036437623067 @ -31, -31, -166 242213832540830, 424489585026284, 282156980635155 @ 22, 34, -65 253677939647052, 71774790363784, 150339320389553 @ 30, 118, 169 208914542209863, 221327515035132, 296977527741265 @ 98, 40, -20 225978346919055, 189503363271362, 257464127408849 @ 62, -62, 36 280003292270532, 273194929507258, 192484316683139 @ -32, 13, 178 241370561741850, 301244008927992, 251395845067739 @ 44, -59, 60 206442308099133, 181336118734342, 408107100470830 @ 86, -30, -139 301996760867700, 310387280483609, 263624066602274 @ -43, -139, 33 314923237240095, 375732987666217, 320822894207489 @ -136, -147, -96 270183603971816, 408157484728546, 266483029933701 @ -200, 87, 79 282522274827330, 419154844645462, 348187416533909 @ -183, -123, -381 391400308625885, 234143077254917, 282386325814828 @ -188, -5, 5 248241992982702, 236933600584012, 226618253934467 @ 35, -40, 85 304738809943074, 366974648702914, 315071440963577 @ -271, 111, -183 317256833455004, 499659423991375, 358438535133325 @ -87, -423, -128 344861079140814, 235832084307832, 235088467063073 @ -161, 90, 95 331627889067230, 102166635226816, 325445669966691 @ -53, 33, -38 277544470541487, 362661905217658, 143456056384913 @ -74, -38, 436 65079839987340, 240651101966827, 121860062366489 @ 233, -123, 180 342577770669831, 147347133816201, 324945146472724 @ -64, -19, -37 308212772927520, 458805983346352, 228065319967187 @ -108, -350, 122 253740247767806, 365333909289500, 61614133850996 @ 31, -248, 261 365962690526502, 315362924823830, 328439534180403 @ -157, -121, -70 294054326857992, 213010706005999, 298211548819148 @ -27, -19, -15 219779660610798, 303410561760076, 159708886802459 @ 151, 472, 613 136893701943065, 362953254474672, 267946767752574 @ 166, -244, 25 244893787502580, 407393629575422, 282902725291239 @ 17, -34, -34 196262891759589, 238852516009657, 260190114409079 @ 110, -35, 38 264224513866830, 412756554745282, 271040907422789 @ -193, 135, 47 244145257499630, 246902624705932, 345477124356419 @ 40, -15, -96 103567172543300, 152988647354764, 106415799964097 @ 342, 312, 381 237049328535246, 455778758722276, 322043719650635 @ 51, -349, -53 376673352124310, 310593535637292, 290158218469475 @ -258, -20, -18 210424804092078, 82373243542024, 232291981915631 @ 111, 471, 109 159978395250240, 183507914962372, 269072947206269 @ 209, 208, 28 246232684189905, 399046050250807, 297901770630794 @ -8, 185, -185 180324128508096, 214385631530956, 235672173157841 @ 154, 88, 87 223806194848000, 357082785792496, 396087216756685 @ 102, 6, -403 259194752897380, 317821847729034, 308986971649649 @ 22, -173, -27 298307615889558, 417432296286096, 486434201004327 @ -109, -238, -548 232114645917249, 313609780467904, 388217993645735 @ 66, 12, -266 321337200009270, 158785966963012, 515755954842479 @ -35, -54, -225 275457332204289, 406220664040342, 270397382020487 @ -72, -170, 30 340476566721830, 326374157455682, 352274774785194 @ -137, -110, -125 181463753476870, 164473967077487, 205295738227709 @ 103, -73, 84 304519692270462, 77725310087932, 377824754146483 @ -16, 15, -83 214857068349012, 301596870886552, 271813369796849 @ 104, 10, 23 211348250163967, 225273734951441, 183300694463183 @ 156, 553, 366 133496002595225, 62291365374777, 207919756885189 @ 166, 89, 92 244181443656309, 420772574702589, 253837864817948 @ 20, -101, 141 300830018159322, 174296199703666, 295138452116897 @ -31, 9, -9 243422051270555, 407940865415295, 278103301151887 @ 22, 17, -10 220581154422402, 79722471889372, 350697513903731 @ 68, 60, -66 245082925719986, 342609293800214, 405264281678849 @ 33, -43, -327 247850340684918, 392398438796662, 236899162162649 @ 11, -45, 183 128001069451687, 297989555796431, 228061359845532 @ 210, -119, 85 244939407723390, 435060214502276, 280562950369875 @ -13, -34, -58 316913138714072, 221638788197917, 323437895995343 @ -159, 285, -114 267864842067030, 150400085066932, 284878281461219 @ 16, -15, 6 405614866313304, 316937218597504, 168919312438151 @ -114, -218, 120 240637839003613, 301874876344243, 75619226493044 @ 46, -177, 243 407681341269689, 435406711222921, 270906852900440 @ -116, -333, 21 307601428077410, 211682999308042, 303439787556799 @ -59, 33, -28 279432068976558, 477067779004460, 412656544245283 @ -145, -427, -653 246495611865920, 420199745093797, 271803259585999 @ -39, 189, 46 269998249376270, 246235532001960, 216537526427763 @ -33, 214, 170 178714014879450, 89848098383351, 85784226487264 @ 107, 7, 203 440404629353925, 170996047237408, 389241750785651 @ -148, -76, -94 248390985168508, 267368954441181, 248093018301785 @ 25, 139, 84 267233147798320, 330970653168712, 374847112142679 @ -44, 78, -316 264482666673849, 352379568285502, 233070865048691 @ -40, 30, 162 264574331700600, 20145140157697, 145526953126739 @ 13, 247, 194 271659396428382, 255644324099356, 222206528627219 @ -30, 141, 143 290977311736348, 444676948938541, 116801545222381 @ -11, -339, 196 313010435881710, 336553683288152, 229358174734664 @ -145, -28, 135 285956222292694, 358335906227884, 240283939863275 @ -101, -24, 126 280817842468188, 264536968119232, 407779118284637 @ -15, -60, -184 236403778487910, 437660647013767, 257095921487864 @ 71, -177, 139 327270091265392, 131483675042490, 224134910443536 @ -39, -34, 67 335061195902542, 271153712345492, 325540021063251 @ -149, 35, -88 238890628317892, 322141235855438, 308185914440670 @ 49, -34, -61 271131779035310, 403216663522684, 78684258172451 @ -33, -207, 516 209029303479318, 47601404592196, 331677735726731 @ 104, 411, -89 132664359388121, 55133082545048, 12921636899287 @ 216, 284, 430 280898664654246, 287224037559008, 275711771568728 @ -25, -52, 15 157283904893390, 15810567219360, 4416323806402 @ 207, 508, 541 307016268839259, 294335836955284, 309836829696560 @ -90, -16, -55 302401719922456, 292179038047870, 313766874165040 @ -131, 126, -95 252780858207378, 418150220598583, 243149525767079 @ -29, -97, 198 200157628876110, 242237200406572, 240147145090739 @ 109, -14, 71 316594269693554, 460445258008648, 264277016412725 @ -119, -354, 39 252527948512697, 453026571775097, 299111778012581 @ -72, -265, -216 219039780135044, 186558656984248, 267983068227965 @ 78, 54, 27 246555699674550, 463619179105429, 250029115292186 @ -73, -367, 441 250480755196005, 415462332029510, 285723060284125 @ -28, -26, -64 208221797969585, 86948144064012, 99756800446489 @ 106, 344, 344