
def day8a(input):
  i, acc = 0, 0
  commands = input.split('\n')
  steps = set()
  while True:
    if i in steps: return acc
    line = commands[i]
    command, mv = line[:3], int(line[4:])
    steps.add(i)
    if command == 'jmp':
      i += mv
      continue
    elif command == 'acc':
      acc += mv
    i += 1

def day8b(input):
  commands = input.split('\n')

  def backTracking(idx, seen, acc, flipped):
    if idx >= len(commands):
      return acc
    if idx in seen:
      return float('-inf')
    line, newCommand = commands[idx], ''
    command, mv = line[:3], int(line[4:])
    seen.add(idx)
    if command == 'jmp':
      res = backTracking(idx + mv, seen, acc, flipped)
      newCommand = 'nop'
    elif command == 'acc':
      acc += mv
      res = backTracking(idx + 1, seen, acc, flipped)
    else:
      res = backTracking(idx + 1, seen, acc, flipped)
      newCommand = 'jmp'
    if res == float('-inf') and not flipped:
      seen.discard(idx)
      if newCommand:
        commands[idx] = newCommand + line[3:]
        return backTracking(idx, seen, acc, True)
    return res

  return backTracking(0, set(), 0, False)


input = """acc +3
jmp +599
nop +311
jmp +605
acc -3
acc +50
acc -6
jmp +461
jmp -4
acc -7
jmp +1
acc +19
acc -18
jmp +485
nop +182
jmp +174
acc +41
acc +10
nop +570
jmp +428
acc +18
acc +33
jmp +197
jmp +202
acc +43
acc -19
acc -12
jmp +453
acc +8
jmp +55
acc +5
nop +482
acc -11
jmp +475
acc -5
acc +38
acc -16
nop +111
jmp +230
acc +41
acc -4
jmp +16
nop +147
jmp -15
nop -28
jmp +96
acc +34
acc +27
jmp -25
jmp +8
acc +8
nop +28
jmp +515
jmp +247
jmp +474
nop +392
jmp +57
nop +271
acc +20
jmp +514
acc +22
jmp +337
acc +47
acc +43
acc +42
nop +263
jmp +144
acc +26
acc +49
acc +22
jmp +170
nop +502
acc +26
acc -3
jmp +96
acc -9
nop +213
acc +1
jmp +111
nop +189
jmp +533
acc -18
acc -15
jmp +209
nop +464
jmp +463
acc +16
acc +39
acc +36
jmp +499
acc +42
jmp +1
jmp +444
acc +33
acc -5
nop +513
acc +17
jmp +377
jmp +410
acc -5
jmp +312
jmp +235
acc -4
acc +32
acc +40
jmp +477
jmp +388
jmp +112
acc +45
acc +36
jmp -68
nop +296
jmp +496
acc -19
acc +1
acc -8
jmp +1
jmp +479
jmp +195
acc -13
acc +50
acc +30
jmp +167
jmp +217
acc +17
acc +8
jmp +22
acc +46
acc -5
jmp +53
jmp +152
acc +29
acc +1
acc +24
jmp +278
acc +20
jmp +95
acc +15
jmp +1
acc +36
jmp +286
acc +44
acc +33
jmp +117
acc +12
acc +16
jmp +1
jmp +284
acc -15
nop +478
acc -17
jmp +13
nop +274
nop +217
nop +91
jmp -113
nop -58
acc +11
acc +28
nop +301
jmp +132
acc -7
acc +18
jmp +173
acc +39
nop +435
jmp +388
acc +15
acc +50
jmp +152
acc -8
acc -10
acc +15
acc +39
jmp +166
acc +14
jmp +310
nop +371
acc +26
jmp +161
acc +37
jmp -147
acc -12
acc +37
nop -78
jmp +11
acc +5
nop -130
jmp +182
acc +23
acc +17
jmp -14
acc +42
acc +16
acc +40
jmp -39
nop +325
acc +15
jmp +70
acc +39
acc +13
nop +211
jmp +210
acc -18
nop +384
acc +28
jmp -98
acc +21
acc +12
jmp +217
acc +22
acc +4
acc +12
jmp +421
acc +26
nop +298
acc +1
acc +43
jmp -15
acc +39
nop +217
nop +31
acc +17
jmp -189
jmp -68
acc -14
jmp +287
nop +62
acc +20
acc +50
jmp -5
acc +26
acc -14
acc +24
acc -2
jmp -181
acc +12
nop -89
acc +13
jmp -50
acc +39
jmp +233
nop -214
acc +47
jmp +216
acc +21
acc +30
nop +347
acc +34
jmp -240
nop -196
jmp +345
acc +48
acc +43
acc +4
nop +266
jmp +72
acc +7
acc +43
jmp +1
acc +44
acc +1
acc +21
jmp +358
acc +20
acc +28
acc +48
jmp +266
acc +14
acc +30
jmp +167
nop +18
acc +17
nop +125
acc +14
jmp -111
nop +332
acc -12
nop -177
jmp +355
acc -8
jmp -125
acc +6
jmp -185
nop +270
acc +32
acc +19
acc -9
jmp +339
jmp -13
nop +23
jmp -109
acc -4
acc +23
acc +39
nop +305
jmp +130
nop -57
acc +46
jmp +301
jmp +1
jmp +150
acc -6
nop -184
acc +18
jmp -123
acc +11
acc +40
jmp -304
acc +16
acc +26
nop -307
jmp +3
jmp -194
jmp -224
acc +8
acc +22
acc +1
acc -1
jmp +73
jmp +41
acc +40
jmp +80
acc +0
acc +39
acc +6
acc +45
jmp -186
acc +32
acc -5
jmp -99
acc +47
acc +17
acc +1
acc +0
jmp +265
jmp +264
nop +114
acc +13
jmp -108
nop -278
acc +29
acc -14
jmp -297
acc +20
acc +37
nop +175
acc -4
jmp +9
acc -11
nop +136
acc +2
jmp -37
acc +48
acc +9
acc -7
jmp +36
acc -15
jmp -118
acc -9
jmp -68
acc +26
nop -1
acc +9
jmp -15
acc +21
acc +13
acc -2
acc -17
jmp -365
acc +5
acc +8
jmp +255
acc +16
nop -312
acc -14
jmp -19
acc +32
acc +37
acc +9
jmp +1
jmp -302
jmp +1
acc +5
acc +45
acc +42
jmp +61
acc +20
acc +36
jmp +156
acc -9
jmp +117
acc -1
nop -389
jmp +242
acc +9
acc -18
jmp -5
jmp -77
acc +17
acc +30
jmp +172
acc -1
acc +11
acc -6
jmp -334
jmp +215
acc +3
acc +24
jmp +13
jmp +1
jmp -369
acc +49
acc -6
acc -14
acc -6
jmp -234
acc +13
acc +9
acc +11
nop +78
jmp +115
nop -332
nop +177
jmp +109
jmp +157
nop -372
acc +25
jmp +166
nop +171
jmp -253
acc +27
acc -11
acc -4
acc +34
jmp +98
jmp -240
acc +41
nop -381
acc -4
nop -270
jmp -328
acc +31
acc +11
acc -2
nop -163
jmp +148
jmp +1
nop -91
jmp -197
jmp +132
acc +31
nop +109
acc +43
jmp -319
acc -19
acc +49
acc +38
acc +48
jmp +86
acc -1
acc -11
acc +2
jmp -355
acc -3
acc +11
acc +39
jmp -110
acc +10
nop -465
nop -121
jmp -110
acc +0
jmp -5
nop -278
nop -199
nop +118
acc +6
jmp -47
jmp +129
acc +26
jmp -391
acc -15
acc +8
nop -86
jmp +115
nop -94
acc -7
acc +14
jmp -183
acc -16
acc +15
acc +23
jmp -178
jmp +1
jmp -365
jmp +1
jmp -320
acc +42
nop -289
acc +21
acc -17
jmp -440
acc +0
acc +5
acc +35
acc +20
jmp +29
acc -1
acc +20
acc +44
jmp +50
jmp -61
acc -2
acc +41
acc -5
jmp -410
acc +13
nop -315
acc -2
jmp -46
acc +20
acc +9
acc +38
nop -279
jmp -113
acc +48
jmp +86
jmp -151
jmp +1
acc -18
nop -291
jmp -101
jmp +49
nop -378
jmp -445
acc +36
acc +41
nop -286
acc -19
jmp -142
nop -393
acc +0
acc -3
jmp +10
acc +17
jmp -327
jmp -219
acc -5
nop -123
acc +49
acc +36
jmp -145
jmp -496
jmp +48
acc +10
jmp +11
jmp -97
acc -8
acc +22
jmp +53
jmp -316
acc +32
acc -15
acc +27
acc +33
jmp -266
jmp -10
acc +48
acc -10
acc +7
acc +5
jmp +28
acc -15
acc -19
acc -8
nop -150
jmp -388
acc +14
acc +45
acc -11
jmp -451
acc +42
acc -8
jmp -104
nop -228
acc +0
jmp -327
acc +19
acc -7
jmp +1
jmp -291
acc -8
jmp -495
jmp -61
jmp -392
acc +1
jmp -227
acc -10
jmp -286
jmp -397
jmp -539
jmp -215
acc +15
acc +36
acc -12
acc +5
jmp -147
acc +28
acc -15
acc +19
jmp +16
jmp -493
acc +7
acc +40
acc +23
nop -122
jmp -567
acc -4
acc +23
jmp -218
jmp -13
acc -18
acc -10
acc -13
nop -541
jmp -105
acc +14
acc +40
acc +0
jmp -614
acc +3
acc +14
jmp -357
jmp -510
jmp -416
acc +12
nop -245
acc +26
acc +15
jmp +1"""
print(day8a(input))
print(day8b(input))
