Advent of Code 2023 - Day 22

Section

sample = """
1,0,1~1,2,1
0,0,2~2,0,2
0,2,3~2,2,3
0,0,4~0,2,4
2,0,5~2,2,5
0,1,6~2,1,6
1,1,8~1,1,9
"""

"1,0,1~1,2,1\n0,0,2~2,0,2\n0,2,3~2,2,3\n0,0,4~0,2,4\n2,0,5~2,2,5\n0,1,6~2,1,6\n1,1,8~1,1,9\n"

Input

input = """
9,4,52~9,7,52
2,9,27~4,9,27
7,5,299~7,7,299
1,7,88~3,7,88
7,3,68~9,3,68
2,4,140~2,8,140
5,6,29~5,6,31
3,6,17~3,8,17
6,2,16~8,2,16
6,2,13~6,3,13
2,9,161~4,9,161
2,9,160~4,9,160
4,1,4~6,1,4
0,4,210~1,4,210
9,7,161~9,9,161
5,7,165~5,9,165
8,0,142~8,0,142
6,5,271~6,7,271
6,2,31~7,2,31
6,7,170~6,7,172
0,0,145~2,0,145
1,2,78~3,2,78
2,8,186~2,8,187
2,1,224~5,1,224
3,0,283~3,0,285
1,6,246~4,6,246
2,1,3~3,1,3
7,2,79~9,2,79
4,7,25~4,7,28
1,7,25~1,8,25
4,3,231~6,3,231
0,5,242~3,5,242
4,2,134~5,2,134
4,0,72~4,0,74
4,4,148~4,7,148
5,5,310~5,8,310
4,1,74~6,1,74
2,3,193~2,6,193
1,6,128~1,9,128
6,4,310~6,6,310
3,0,26~3,1,26
4,0,135~5,0,135
5,1,130~5,3,130
1,3,209~1,5,209
0,4,181~0,4,184
7,0,171~8,0,171
5,5,204~5,5,207
7,3,65~7,6,65
0,7,226~4,7,226
0,8,262~2,8,262
4,5,99~5,5,99
4,6,134~4,8,134
5,0,69~6,0,69
3,9,11~4,9,11
0,1,95~0,3,95
0,0,222~0,2,222
1,3,44~1,6,44
4,5,117~4,6,117
7,4,242~7,4,244
4,9,118~6,9,118
5,4,245~5,5,245
3,3,48~6,3,48
6,3,237~6,5,237
3,5,42~5,5,42
7,3,21~7,5,21
4,2,284~4,4,284
1,6,72~3,6,72
4,7,269~4,7,271
0,7,163~2,7,163
2,4,228~2,7,228
8,3,71~8,5,71
0,3,231~3,3,231
1,6,229~1,9,229
0,5,216~0,7,216
7,9,4~9,9,4
2,3,191~4,3,191
9,3,262~9,4,262
2,7,267~5,7,267
4,5,307~4,7,307
0,1,295~2,1,295
4,0,203~6,0,203
2,4,109~4,4,109
2,5,245~2,8,245
7,7,300~7,7,302
0,1,112~0,3,112
7,4,197~7,6,197
1,8,3~4,8,3
3,2,280~4,2,280
4,3,276~4,5,276
7,3,151~7,3,152
2,2,313~2,5,313
8,0,25~8,2,25
8,4,267~8,6,267
3,7,210~4,7,210
5,4,321~5,5,321
3,3,105~6,3,105
8,8,269~8,8,272
5,8,145~8,8,145
0,7,173~0,7,175
4,4,101~4,7,101
5,8,204~7,8,204
7,6,194~7,8,194
8,6,130~8,8,130
3,0,23~5,0,23
4,7,219~6,7,219
2,0,140~2,1,140
1,8,263~1,8,264
0,1,307~0,1,309
4,9,269~6,9,269
7,5,300~7,6,300
1,6,320~3,6,320
6,7,37~6,8,37
6,7,226~6,7,229
4,5,261~4,8,261
4,1,59~4,3,59
1,8,301~4,8,301
6,4,215~9,4,215
6,8,278~6,8,279
8,7,168~8,9,168
8,4,52~8,7,52
3,7,234~3,9,234
0,8,145~0,8,147
7,0,280~9,0,280
5,6,152~5,7,152
5,4,125~5,7,125
5,4,19~7,4,19
8,2,114~8,4,114
6,6,277~8,6,277
2,7,220~2,7,223
0,0,6~0,0,7
6,9,227~8,9,227
5,2,210~8,2,210
6,0,50~8,0,50
5,6,186~5,8,186
4,5,161~4,7,161
5,2,245~6,2,245
0,3,37~0,5,37
4,1,251~5,1,251
7,1,281~9,1,281
2,4,208~4,4,208
2,5,40~5,5,40
2,8,300~5,8,300
0,5,290~3,5,290
4,6,17~4,6,19
5,3,313~5,5,313
8,7,144~8,7,146
2,1,280~2,3,280
6,4,69~9,4,69
0,8,72~2,8,72
7,0,33~9,0,33
2,9,30~2,9,32
4,7,151~4,9,151
8,5,253~8,8,253
4,7,181~7,7,181
4,5,118~6,5,118
3,1,321~5,1,321
3,6,264~6,6,264
6,7,223~6,8,223
4,6,139~6,6,139
6,6,225~6,6,227
0,0,40~2,0,40
3,4,112~5,4,112
2,8,259~3,8,259
2,7,231~4,7,231
8,7,67~9,7,67
6,0,84~9,0,84
3,9,25~6,9,25
4,7,117~4,9,117
5,2,167~5,4,167
9,0,160~9,3,160
9,3,182~9,5,182
9,6,126~9,8,126
5,2,296~5,5,296
5,7,289~8,7,289
3,4,7~5,4,7
8,4,270~8,7,270
4,0,259~4,3,259
2,7,39~5,7,39
7,1,6~7,4,6
6,6,7~9,6,7
1,6,1~2,6,1
4,4,33~4,4,35
6,8,191~7,8,191
5,4,148~5,5,148
5,6,248~5,9,248
5,4,252~8,4,252
5,6,247~5,7,247
7,2,157~7,4,157
3,9,143~5,9,143
3,7,309~6,7,309
5,3,34~5,5,34
9,4,278~9,4,278
2,7,105~2,8,105
0,9,2~4,9,2
5,0,240~5,1,240
3,7,158~5,7,158
1,6,292~2,6,292
6,9,26~6,9,28
0,8,258~3,8,258
3,1,169~6,1,169
8,6,112~8,6,114
6,8,2~8,8,2
5,5,120~7,5,120
0,0,255~2,0,255
2,6,32~4,6,32
9,0,258~9,3,258
7,0,165~9,0,165
0,7,57~0,9,57
4,8,282~7,8,282
1,1,50~1,3,50
5,6,197~5,6,199
1,8,55~1,9,55
4,9,300~6,9,300
0,8,275~0,9,275
9,1,34~9,3,34
2,3,95~2,5,95
4,3,4~4,5,4
6,1,274~8,1,274
2,1,41~2,3,41
9,8,288~9,9,288
1,9,84~3,9,84
3,6,58~3,8,58
5,2,289~5,5,289
6,0,209~8,0,209
9,5,133~9,7,133
8,0,222~9,0,222
2,3,110~2,5,110
3,3,16~6,3,16
2,6,166~2,8,166
5,0,292~5,3,292
5,0,89~7,0,89
5,8,74~5,8,76
5,3,88~5,4,88
9,1,22~9,3,22
9,1,5~9,3,5
5,3,128~7,3,128
3,4,227~3,6,227
4,1,325~6,1,325
1,8,215~3,8,215
4,7,83~4,7,84
8,8,273~8,8,275
1,0,144~1,2,144
3,7,304~3,8,304
7,0,139~9,0,139
9,6,29~9,8,29
4,5,262~6,5,262
4,4,106~4,6,106
7,6,233~8,6,233
3,0,144~4,0,144
5,5,16~8,5,16
4,1,312~4,1,315
6,4,13~9,4,13
5,4,29~8,4,29
7,7,93~7,9,93
0,1,320~3,1,320
0,2,274~1,2,274
4,5,91~4,5,94
5,7,134~5,7,136
5,4,152~7,4,152
1,0,138~4,0,138
2,2,182~2,5,182
5,1,296~7,1,296
3,6,295~6,6,295
3,7,132~5,7,132
9,0,135~9,3,135
2,0,158~2,2,158
8,7,21~8,7,22
0,3,39~0,4,39
7,0,14~9,0,14
4,3,228~4,3,228
7,3,39~7,6,39
5,7,113~5,7,115
0,4,265~1,4,265
9,5,169~9,8,169
0,1,191~2,1,191
0,0,50~0,2,50
0,2,34~0,3,34
9,2,157~9,5,157
0,7,2~2,7,2
0,2,145~0,4,145
3,4,181~3,6,181
7,3,257~9,3,257
0,6,140~0,8,140
3,9,153~4,9,153
1,5,247~1,8,247
9,6,21~9,6,23
6,7,255~8,7,255
1,7,304~1,8,304
0,1,146~0,1,149
6,3,9~7,3,9
3,7,187~3,8,187
1,7,315~5,7,315
0,5,169~0,5,171
6,2,55~6,5,55
5,3,157~5,5,157
7,6,148~7,7,148
3,7,65~5,7,65
1,8,57~3,8,57
1,1,134~3,1,134
1,5,269~1,6,269
4,8,275~4,9,275
4,0,10~6,0,10
6,1,138~6,3,138
2,2,138~2,5,138
4,8,14~6,8,14
5,4,304~7,4,304
6,5,294~6,7,294
7,1,137~9,1,137
8,2,275~8,2,277
1,8,130~3,8,130
0,1,35~1,1,35
8,0,273~8,3,273
7,8,97~9,8,97
3,3,294~3,6,294
3,8,65~4,8,65
5,4,210~6,4,210
7,2,169~7,2,172
5,5,190~6,5,190
0,7,134~0,9,134
3,8,218~3,8,219
1,4,112~1,6,112
4,4,38~6,4,38
6,5,36~6,7,36
3,0,240~4,0,240
5,2,58~8,2,58
5,7,194~5,9,194
4,5,284~4,8,284
8,7,125~8,9,125
8,3,55~8,5,55
5,6,141~5,9,141
5,1,266~7,1,266
8,7,20~8,8,20
8,5,182~8,5,183
1,0,239~1,0,241
3,2,217~3,4,217
6,0,150~6,2,150
2,5,43~2,5,44
9,2,138~9,2,142
2,3,171~4,3,171
1,0,72~3,0,72
7,6,86~7,8,86
8,8,292~9,8,292
1,8,19~4,8,19
2,2,38~5,2,38
2,6,321~2,6,321
5,3,49~5,3,50
9,6,301~9,8,301
4,6,289~4,8,289
4,0,39~4,4,39
1,0,311~3,0,311
0,0,1~0,0,3
2,8,26~4,8,26
5,2,203~8,2,203
6,4,186~6,6,186
3,2,316~5,2,316
6,8,254~6,8,256
6,0,221~6,0,222
8,3,307~8,5,307
0,1,242~0,4,242
0,3,311~0,5,311
3,1,195~5,1,195
3,0,74~3,0,76
3,0,51~3,0,53
1,1,313~1,3,313
3,2,25~5,2,25
5,8,155~8,8,155
5,6,313~5,8,313
2,2,22~4,2,22
6,9,122~8,9,122
9,6,201~9,6,204
7,0,283~9,0,283
1,0,48~3,0,48
8,3,74~8,5,74
4,4,217~4,4,217
8,2,12~8,5,12
6,3,198~6,4,198
7,2,200~7,4,200
8,7,307~8,9,307
6,0,52~8,0,52
9,2,279~9,3,279
7,6,145~9,6,145
6,6,299~6,9,299
7,4,4~9,4,4
0,5,83~0,6,83
3,6,141~3,8,141
1,2,151~1,4,151
1,3,273~1,6,273
3,2,311~3,4,311
0,9,179~1,9,179
3,8,278~3,9,278
5,0,159~5,2,159
8,4,186~8,6,186
5,8,201~6,8,201
5,0,274~5,1,274
2,0,304~5,0,304
7,6,230~7,9,230
9,5,264~9,6,264
7,7,178~7,9,178
3,3,25~6,3,25
9,2,276~9,5,276
4,1,248~6,1,248
2,1,207~2,2,207
9,1,259~9,4,259
3,4,244~3,5,244
5,8,22~5,9,22
3,4,138~3,8,138
7,4,309~8,4,309
2,4,199~2,7,199
3,1,222~3,3,222
5,4,155~8,4,155
3,7,101~3,9,101
0,8,246~2,8,246
9,3,11~9,5,11
9,6,33~9,9,33
0,9,63~0,9,65
5,2,293~7,2,293
9,1,49~9,3,49
0,5,7~4,5,7
5,0,230~5,2,230
1,4,40~1,7,40
2,4,306~2,6,306
7,1,66~8,1,66
6,0,48~8,0,48
6,3,283~8,3,283
6,1,147~6,4,147
6,9,119~8,9,119
2,6,297~2,8,297
1,9,271~4,9,271
2,5,161~2,7,161
5,3,319~5,7,319
2,2,10~4,2,10
8,7,128~8,9,128
9,1,187~9,4,187
9,5,270~9,7,270
6,0,308~7,0,308
8,9,40~9,9,40
9,4,303~9,6,303
3,4,29~3,6,29
0,1,92~0,3,92
4,7,155~5,7,155
5,1,265~5,3,265
3,1,192~3,1,193
8,2,278~8,4,278
0,4,132~0,7,132
4,1,57~7,1,57
8,4,45~8,5,45
4,8,22~4,8,24
6,7,278~7,7,278
1,3,323~1,5,323
4,2,159~4,2,161
4,2,205~7,2,205
4,6,208~4,8,208
5,5,152~7,5,152
0,3,250~0,4,250
8,8,171~8,8,173
5,1,49~8,1,49
1,0,236~1,1,236
0,7,231~0,9,231
3,8,199~6,8,199
6,6,142~8,6,142
7,7,19~7,7,22
2,1,235~5,1,235
9,5,49~9,5,51
5,3,132~5,4,132
6,2,61~6,4,61
6,3,255~6,6,255
6,7,89~8,7,89
2,2,282~5,2,282
7,1,239~7,3,239
2,7,184~2,9,184
0,1,131~2,1,131
0,9,110~3,9,110
9,5,45~9,5,47
6,8,90~8,8,90
1,3,140~1,5,140
3,6,62~3,8,62
4,4,283~5,4,283
7,4,253~7,4,253
3,6,317~3,9,317
6,4,171~6,6,171
4,4,89~4,6,89
2,4,289~2,7,289
7,7,10~9,7,10
3,6,171~4,6,171
3,6,85~3,8,85
5,6,27~5,8,27
7,6,18~9,6,18
1,5,48~1,6,48
5,7,29~7,7,29
3,4,170~3,7,170
0,8,53~3,8,53
9,1,278~9,1,280
0,2,161~3,2,161
4,2,199~4,5,199
2,4,256~4,4,256
0,0,256~3,0,256
8,6,85~8,6,87
6,7,82~6,8,82
5,4,300~5,4,303
3,2,277~4,2,277
0,7,124~2,7,124
9,8,36~9,8,37
6,1,208~9,1,208
4,5,27~6,5,27
3,5,38~3,8,38
2,2,246~2,5,246
4,2,241~6,2,241
4,1,60~4,1,62
1,2,189~1,4,189
3,4,120~3,6,120
2,0,231~2,0,234
2,2,166~2,5,166
3,1,311~3,1,311
0,4,158~0,4,161
1,7,166~1,9,166
5,3,149~7,3,149
3,3,31~3,5,31
8,1,15~8,4,15
2,1,46~3,1,46
5,4,266~5,7,266
4,3,293~4,6,293
4,3,172~7,3,172
3,6,239~5,6,239
4,0,254~4,2,254
3,7,123~3,9,123
2,6,16~4,6,16
3,1,10~5,1,10
7,3,158~7,5,158
8,1,159~8,3,159
7,3,285~7,3,287
1,5,268~1,6,268
5,7,182~7,7,182
1,3,207~4,3,207
8,6,278~8,6,279
1,3,119~3,3,119
7,1,37~9,1,37
4,4,24~4,5,24
1,2,46~3,2,46
1,3,306~4,3,306
1,2,320~4,2,320
7,3,80~9,3,80
2,2,309~2,3,309
2,0,261~4,0,261
9,1,216~9,3,216
7,4,121~7,7,121
9,6,155~9,9,155
2,2,168~4,2,168
3,4,312~4,4,312
3,6,82~6,6,82
6,7,268~6,9,268
3,2,207~3,2,210
3,0,309~3,3,309
4,0,309~4,2,309
6,3,144~6,5,144
5,3,208~5,5,208
1,9,56~2,9,56
0,4,325~1,4,325
9,6,168~9,8,168
8,6,290~8,8,290
3,0,281~5,0,281
7,1,50~7,5,50
7,3,240~7,4,240
6,1,164~6,3,164
1,0,313~4,0,313
2,7,116~4,7,116
1,8,169~3,8,169
9,2,24~9,4,24
5,9,162~7,9,162
9,3,83~9,3,85
3,8,63~3,8,64
6,9,30~9,9,30
2,3,6~4,3,6
5,5,127~5,7,127
4,8,118~5,8,118
5,7,283~5,9,283
1,5,227~1,7,227
7,8,87~8,8,87
2,7,210~2,7,212
1,2,224~3,2,224
2,4,209~2,4,210
9,5,147~9,7,147
2,0,301~5,0,301
7,9,228~9,9,228
5,8,302~8,8,302
7,4,255~7,4,257
3,1,236~3,3,236
3,4,80~4,4,80
4,0,7~4,3,7
6,6,88~7,6,88
2,3,269~2,6,269
0,2,96~0,2,97
6,1,166~6,3,166
3,9,243~6,9,243
4,7,264~7,7,264
8,4,65~8,5,65
2,5,296~4,5,296
1,7,109~1,9,109
8,2,200~8,4,200
3,3,233~3,3,234
3,3,90~5,3,90
0,6,102~3,6,102
4,8,251~6,8,251
1,8,157~3,8,157
1,2,170~1,5,170
1,8,185~3,8,185
3,4,10~5,4,10
5,1,190~7,1,190
1,0,307~3,0,307
1,4,126~1,4,127
2,0,151~4,0,151
6,5,18~8,5,18
9,6,267~9,8,267
1,2,80~2,2,80
5,2,242~5,3,242
5,2,19~5,3,19
7,4,161~7,4,163
3,1,174~3,3,174
2,4,81~2,6,81
3,1,40~5,1,40
0,3,106~0,5,106
4,4,291~4,6,291
4,2,266~6,2,266
6,5,10~9,5,10
0,3,268~0,5,268
8,0,65~8,0,65
4,3,202~4,4,202
0,3,208~0,3,209
4,1,238~4,2,238
1,3,228~3,3,228
5,6,222~7,6,222
6,3,276~6,5,276
8,7,268~8,8,268
7,2,213~9,2,213
9,3,304~9,4,304
6,9,189~9,9,189
3,1,12~3,1,12
4,3,205~4,4,205
7,9,131~9,9,131
1,4,183~2,4,183
6,6,164~6,9,164
7,5,17~9,5,17
6,2,304~8,2,304
2,3,69~2,6,69
5,1,27~5,3,27
2,0,77~2,2,77
4,8,257~6,8,257
1,4,119~1,4,121
6,8,287~9,8,287
1,0,230~4,0,230
4,5,138~4,8,138
0,3,232~0,3,234
0,9,272~1,9,272
2,2,194~2,4,194
5,5,70~5,7,70
7,2,159~7,2,161
4,1,199~5,1,199
7,3,136~7,5,136
4,8,258~4,8,260
3,9,29~5,9,29
2,2,294~2,4,294
5,3,44~7,3,44
3,2,204~3,6,204
8,6,64~8,8,64
8,5,156~9,5,156
8,3,127~8,5,127
2,5,167~2,5,169
1,8,311~3,8,311
7,0,215~9,0,215
4,4,220~7,4,220
3,5,75~5,5,75
2,7,110~4,7,110
6,7,92~6,9,92
1,9,244~3,9,244
1,3,139~3,3,139
4,9,84~6,9,84
0,1,243~0,3,243
0,4,49~0,6,49
5,4,39~5,4,42
5,6,175~5,8,175
1,5,111~2,5,111
3,8,11~5,8,11
3,8,51~4,8,51
5,0,197~5,1,197
0,6,6~2,6,6
2,9,152~4,9,152
3,6,236~3,8,236
2,0,298~2,1,298
9,2,266~9,2,267
8,2,212~8,4,212
2,4,158~2,5,158
5,3,46~6,3,46
4,2,112~4,2,115
7,2,52~8,2,52
2,7,41~2,8,41
3,0,264~4,0,264
0,6,122~3,6,122
9,3,185~9,4,185
4,3,20~4,3,22
9,4,261~9,6,261
9,5,109~9,5,109
9,5,178~9,8,178
6,7,96~9,7,96
1,4,233~1,5,233
0,5,11~0,8,11
7,3,133~7,5,133
3,2,234~5,2,234
4,4,79~4,5,79
2,0,247~4,0,247
5,4,175~8,4,175
8,0,138~9,0,138
1,7,22~1,9,22
4,6,81~4,7,81
4,5,104~4,5,105
0,6,256~0,9,256
5,4,114~6,4,114
3,6,75~6,6,75
1,0,76~1,1,76
1,0,2~2,0,2
7,4,124~9,4,124
3,6,167~6,6,167
2,1,311~2,3,311
5,1,202~7,1,202
0,3,155~0,5,155
0,5,166~0,7,166
0,4,260~0,6,260
2,2,75~4,2,75
5,5,308~6,5,308
4,2,135~7,2,135
0,0,246~2,0,246
5,1,16~8,1,16
7,3,251~7,6,251
9,7,163~9,7,165
3,0,12~5,0,12
5,0,132~5,2,132
2,2,273~4,2,273
3,4,229~3,6,229
9,4,71~9,6,71
3,5,97~5,5,97
4,7,214~8,7,214
7,4,23~7,5,23
4,1,154~5,1,154
0,8,55~0,9,55
6,6,127~8,6,127
8,0,262~8,1,262
6,5,11~6,6,11
5,0,307~8,0,307
0,1,251~0,2,251
0,2,164~1,2,164
8,4,202~8,6,202
0,4,116~2,4,116
9,0,32~9,1,32
0,4,177~0,8,177
6,8,167~8,8,167
5,1,243~8,1,243
4,7,156~5,7,156
3,2,120~5,2,120
2,0,300~2,1,300
6,0,92~7,0,92
2,1,128~2,3,128
4,4,63~8,4,63
3,8,195~6,8,195
3,2,36~3,4,36
9,3,244~9,5,244
2,1,20~4,1,20
6,6,168~7,6,168
7,4,221~7,6,221
5,1,298~5,1,299
2,4,85~5,4,85
6,3,35~6,4,35
3,5,230~5,5,230
8,8,152~9,8,152
8,7,18~8,8,18
1,2,262~1,4,262
3,3,104~6,3,104
0,4,255~2,4,255
5,8,94~7,8,94
1,1,73~4,1,73
7,3,58~8,3,58
1,5,212~1,9,212
3,1,318~7,1,318
5,1,156~8,1,156
5,7,8~5,8,8
7,7,30~7,7,32
5,3,297~5,6,297
7,7,188~9,7,188
3,1,293~5,1,293
5,0,86~9,0,86
1,5,193~1,8,193
1,1,303~3,1,303
2,2,125~4,2,125
6,2,207~6,3,207
5,6,218~8,6,218
5,0,227~5,3,227
8,2,217~8,4,217
7,4,5~7,5,5
3,5,139~3,7,139
3,8,222~5,8,222
9,0,266~9,1,266
8,2,153~9,2,153
8,4,129~8,4,129
8,5,8~8,8,8
5,2,82~7,2,82
0,0,135~0,3,135
2,1,206~4,1,206
5,3,101~5,5,101
0,6,248~0,8,248
1,3,157~1,6,157
9,6,194~9,6,196
2,7,217~2,9,217
4,5,22~4,7,22
9,1,125~9,4,125
4,2,311~4,2,313
5,5,76~5,5,76
4,5,33~6,5,33
0,4,14~2,4,14
2,4,309~3,4,309
3,8,291~5,8,291
4,8,5~7,8,5
4,6,24~6,6,24
5,4,279~7,4,279
2,7,292~4,7,292
7,3,252~7,3,255
7,6,186~7,9,186
8,7,292~8,7,293
4,5,131~4,8,131
4,7,190~7,7,190
8,8,67~8,8,68
4,9,296~7,9,296
2,0,142~4,0,142
3,6,41~5,6,41
2,0,165~5,0,165
5,9,291~7,9,291
3,6,40~3,8,40
8,4,1~8,7,1
9,4,75~9,4,76
4,9,155~4,9,158
3,2,193~3,4,193
2,0,314~3,0,314
7,0,53~7,0,55
2,4,136~5,4,136
5,3,226~5,3,226
6,4,173~9,4,173
8,8,34~8,9,34
8,9,169~8,9,171
7,4,306~8,4,306
3,0,187~3,3,187
0,6,228~0,9,228
0,6,16~0,8,16
9,0,39~9,3,39
1,5,78~3,5,78
1,0,33~2,0,33
8,9,309~9,9,309
2,3,88~4,3,88
3,2,258~3,5,258
3,5,100~3,8,100
2,1,141~2,1,143
3,3,225~5,3,225
5,2,168~7,2,168
1,0,233~1,0,235
1,6,207~4,6,207
0,4,154~3,4,154
8,8,291~9,8,291
6,3,234~8,3,234
3,6,78~3,9,78
0,0,4~1,0,4
6,4,72~7,4,72
4,0,199~6,0,199
3,0,278~3,4,278
9,2,29~9,5,29
2,6,296~3,6,296
0,4,28~4,4,28
4,7,293~6,7,293
1,8,145~3,8,145
6,9,1~6,9,4
8,5,63~8,7,63
6,0,11~7,0,11
6,6,215~6,8,215
4,1,225~4,1,227
0,4,245~0,4,248
6,1,56~6,3,56
4,2,50~4,2,52
0,7,259~3,7,259
9,0,81~9,3,81
3,7,48~3,9,48
3,8,290~6,8,290
5,3,161~5,7,161
5,0,150~5,1,150
9,2,73~9,4,73
3,7,196~3,8,196
9,5,130~9,7,130
6,6,185~8,6,185
8,5,14~8,7,14
0,9,60~2,9,60
2,5,271~4,5,271
2,8,144~2,9,144
9,8,2~9,8,3
5,4,150~5,6,150
9,6,265~9,9,265
4,5,213~4,8,213
4,6,154~6,6,154
2,6,309~2,8,309
1,3,195~1,6,195
5,1,147~5,4,147
0,9,7~1,9,7
2,1,251~2,4,251
9,2,14~9,4,14
3,9,111~5,9,111
0,3,207~0,6,207
2,6,183~2,7,183
8,4,112~8,5,112
2,0,228~4,0,228
7,5,12~7,7,12
0,1,2~0,1,4
0,5,158~0,7,158
5,2,188~5,4,188
7,6,15~8,6,15
2,7,294~2,8,294
5,6,16~5,8,16
0,6,242~2,6,242
1,0,244~4,0,244
2,6,67~2,8,67
5,7,222~7,7,222
5,8,3~8,8,3
0,1,37~0,1,37
4,0,55~6,0,55
6,0,166~9,0,166
5,4,17~8,4,17
6,4,9~6,6,9
4,3,129~4,3,131
5,8,260~6,8,260
8,2,82~8,3,82
3,2,156~6,2,156
6,0,214~8,0,214
1,5,4~1,7,4
3,9,126~3,9,127
2,6,64~4,6,64
1,4,166~1,5,166
0,1,310~0,2,310
6,5,30~6,8,30
2,5,107~5,5,107
5,5,109~5,7,109
2,4,91~2,6,91
1,7,119~4,7,119
7,8,300~9,8,300
7,8,176~9,8,176
8,9,5~9,9,5
5,3,134~5,6,134
1,0,34~1,0,35
5,9,284~8,9,284
2,7,31~4,7,31
9,3,19~9,5,19
2,1,254~2,1,255
0,2,271~0,3,271
4,7,3~6,7,3
8,2,126~9,2,126
7,4,28~9,4,28
2,8,102~4,8,102
7,6,286~7,9,286
7,1,132~7,3,132
8,5,228~8,8,228
2,4,196~2,5,196
6,0,215~6,1,215
6,0,151~6,0,153
0,7,217~0,9,217
5,7,73~5,8,73
3,2,49~3,3,49
3,7,288~3,9,288
0,7,105~0,8,105
4,0,153~4,0,157
0,9,11~2,9,11
4,2,121~6,2,121
1,5,160~1,5,163
7,0,24~7,2,24
7,9,1~8,9,1
3,7,42~3,7,45
3,0,255~3,2,255
6,2,179~9,2,179
1,4,312~2,4,312
4,2,77~7,2,77
5,6,15~5,9,15
3,1,127~3,4,127
6,1,153~6,3,153
5,6,113~7,6,113
7,0,46~7,3,46
4,9,124~4,9,126
2,3,233~2,5,233
5,4,244~5,7,244
4,3,86~4,5,86
0,3,129~0,5,129
5,8,183~7,8,183
4,6,188~5,6,188
1,0,121~1,2,121
4,4,160~6,4,160
3,2,212~3,5,212
1,7,108~4,7,108
6,1,209~7,1,209
6,2,54~8,2,54
0,2,204~2,2,204
4,6,273~6,6,273
6,5,42~9,5,42
1,1,79~1,1,79
4,3,226~4,4,226
7,2,208~7,3,208
5,9,200~7,9,200
3,4,219~3,5,219
0,2,249~3,2,249
0,4,50~0,6,50
1,1,13~4,1,13
5,8,243~7,8,243
5,8,189~7,8,189
4,7,193~4,7,195
7,5,289~8,5,289
1,1,264~1,2,264
1,5,165~3,5,165
0,4,126~0,7,126
7,9,160~9,9,160
3,3,296~3,3,299
3,7,246~5,7,246
4,0,211~8,0,211
2,6,208~2,7,208
2,1,160~2,2,160
7,2,27~7,2,29
4,3,149~4,5,149
4,8,264~6,8,264
5,6,122~7,6,122
1,4,158~1,6,158
8,0,169~8,1,169
6,4,197~6,6,197
4,2,233~4,3,233
0,9,8~3,9,8
8,1,301~8,4,301
5,4,234~5,4,236
1,0,276~1,2,276
2,2,247~2,6,247
2,3,3~4,3,3
5,1,152~6,1,152
6,9,289~8,9,289
4,6,183~7,6,183
1,4,322~1,7,322
5,5,251~5,7,251
2,6,154~2,9,154
2,7,202~2,9,202
3,0,206~6,0,206
6,0,25~6,0,27
5,0,149~5,2,149
1,6,38~1,8,38
7,5,255~9,5,255
7,6,252~7,9,252
7,8,254~9,8,254
0,6,272~2,6,272
2,6,112~2,8,112
2,3,190~4,3,190
4,1,126~4,4,126
1,9,125~2,9,125
7,0,58~7,0,60
6,1,203~8,1,203
6,4,305~6,6,305
5,0,243~5,0,245
5,3,262~6,3,262
6,6,77~6,8,77
3,8,59~4,8,59
1,3,223~3,3,223
6,1,178~6,4,178
3,4,210~3,6,210
4,2,272~4,4,272
6,3,199~8,3,199
6,8,86~6,9,86
0,3,185~0,6,185
0,1,145~3,1,145
6,3,36~8,3,36
1,3,205~1,6,205
4,5,175~7,5,175
1,2,185~3,2,185
0,7,142~0,9,142
0,0,278~2,0,278
4,9,127~6,9,127
0,3,148~2,3,148
1,3,301~4,3,301
1,6,237~4,6,237
5,6,272~6,6,272
5,5,1~5,5,2
3,3,213~3,3,214
4,1,49~4,3,49
7,1,157~8,1,157
3,1,279~4,1,279
9,4,183~9,6,183
9,3,150~9,5,150
7,3,48~9,3,48
5,7,110~6,7,110
5,0,20~7,0,20
3,8,41~5,8,41
6,5,155~8,5,155
2,0,133~2,2,133
6,3,27~8,3,27
0,4,216~0,4,218
4,5,115~4,8,115
2,4,203~4,4,203
8,8,231~8,8,233
7,2,126~7,4,126
0,4,142~1,4,142
9,1,277~9,2,277
7,9,308~9,9,308
5,0,18~8,0,18
2,0,186~2,2,186
7,2,150~8,2,150
5,9,17~7,9,17
0,4,291~2,4,291
2,5,8~3,5,8
0,6,47~1,6,47
2,4,79~2,6,79
7,6,246~7,9,246
0,4,29~1,4,29
0,3,91~3,3,91
0,7,203~2,7,203
5,7,173~5,9,173
8,2,77~8,4,77
7,0,27~9,0,27
0,1,305~2,1,305
6,8,79~6,9,79
4,6,77~4,8,77
2,7,322~5,7,322
6,1,269~6,3,269
7,6,180~7,9,180
4,2,30~4,4,30
0,2,48~0,4,48
4,1,41~4,3,41
1,8,58~1,8,60
5,8,172~7,8,172
2,3,253~2,5,253
6,8,150~8,8,150
4,8,28~4,8,29
2,6,142~2,8,142
1,3,15~1,6,15
8,4,3~8,7,3
1,1,37~1,1,39
8,5,177~8,7,177
1,1,253~1,3,253
8,3,274~9,3,274
6,3,209~7,3,209
0,1,238~2,1,238
0,9,207~0,9,209
6,1,206~8,1,206
3,5,44~6,5,44
9,3,265~9,5,265
5,6,241~5,9,241
7,0,164~7,2,164
5,6,189~5,6,191
0,0,113~0,2,113
6,3,107~6,4,107
9,2,186~9,3,186
6,7,266~8,7,266
0,7,136~0,7,137
2,3,277~5,3,277
4,1,16~4,2,16
7,7,123~9,7,123
7,0,66~8,0,66
2,7,141~2,9,141
6,4,110~6,4,112
5,5,72~5,7,72
4,2,65~4,4,65
1,8,155~2,8,155
6,1,158~6,1,158
6,1,161~6,2,161
4,2,19~4,5,19
0,4,123~2,4,123
2,5,219~2,7,219
0,6,250~0,6,254
0,5,205~0,8,205
8,1,60~8,2,60
4,8,271~7,8,271
0,4,104~0,7,104
1,4,11~5,4,11
4,0,232~4,2,232
9,2,261~9,2,263
3,0,252~3,3,252
0,0,52~0,2,52
6,6,275~6,8,275
3,7,218~6,7,218
1,0,32~1,4,32
8,1,236~8,3,236
9,4,247~9,5,247
9,3,88~9,3,88
9,7,294~9,9,294
6,3,254~6,5,254
0,2,219~3,2,219
6,4,141~6,4,143
2,2,175~2,4,175
6,5,311~6,5,313
1,1,234~1,3,234
3,4,275~6,4,275
5,0,278~5,3,278
0,0,190~1,0,190
6,6,84~8,6,84
2,0,161~2,0,163
5,5,104~8,5,104
1,5,74~1,5,76
0,1,240~0,3,240
1,0,188~1,2,188
8,7,66~9,7,66
9,6,128~9,8,128
8,3,57~8,4,57
1,3,203~1,5,203
6,0,219~8,0,219
9,3,32~9,6,32
0,5,293~0,6,293
9,0,158~9,2,158
2,2,274~4,2,274
1,5,73~1,7,73
3,1,43~3,4,43
2,1,245~5,1,245
1,5,28~1,7,28
7,2,250~9,2,250
6,5,174~8,5,174
0,1,16~1,1,16
6,5,107~9,5,107
1,6,159~1,9,159
6,7,184~9,7,184
2,9,81~5,9,81
4,1,308~4,3,308
1,5,129~1,7,129
8,3,238~9,3,238
0,3,309~1,3,309
3,0,45~3,0,47
3,2,253~4,2,253
1,1,203~3,1,203
5,3,233~5,5,233
7,0,15~7,2,15
3,5,201~6,5,201
1,0,249~1,0,252
4,8,139~6,8,139
3,8,163~4,8,163
0,9,161~1,9,161
9,2,26~9,4,26
5,3,164~5,3,166
6,0,6~6,1,6
7,1,63~8,1,63
6,9,138~8,9,138
0,0,133~0,2,133
7,9,278~9,9,278
5,5,223~8,5,223
5,4,187~5,6,187
7,7,170~7,9,170
5,3,266~7,3,266
1,2,141~4,2,141
9,0,264~9,2,264
0,4,179~0,4,180
1,1,48~2,1,48
2,2,117~2,5,117
9,8,158~9,9,158
4,2,9~5,2,9
6,7,193~6,9,193
3,0,71~5,0,71
2,2,187~2,2,187
1,2,169~2,2,169
4,6,133~4,8,133
3,3,120~3,3,122
5,9,39~8,9,39
6,7,187~8,7,187
6,0,68~8,0,68
0,8,12~0,8,15
7,5,248~7,7,248
7,1,131~7,3,131
2,2,151~2,3,151
3,6,118~5,6,118
5,6,111~8,6,111
1,4,232~1,6,232
3,7,248~3,7,248
1,3,176~2,3,176
4,4,216~4,5,216
5,0,63~8,0,63
4,9,191~6,9,191
2,1,72~2,3,72
3,4,270~4,4,270
0,5,81~1,5,81
6,4,292~6,6,292
0,5,13~0,7,13
5,9,294~6,9,294
4,7,128~6,7,128
7,0,29~9,0,29
4,4,138~6,4,138
1,4,37~3,4,37
1,1,45~1,3,45
8,5,225~8,7,225
2,4,167~4,4,167
2,4,88~2,5,88
6,5,204~7,5,204
2,4,113~2,6,113
7,8,197~9,8,197
5,4,3~5,4,4
7,7,132~7,9,132
3,1,163~3,3,163
8,4,50~9,4,50
6,0,276~9,0,276
7,4,219~7,6,219
4,4,145~6,4,145
5,2,140~5,5,140
3,6,14~3,8,14
0,7,206~0,9,206
4,4,129~4,4,130
5,6,290~7,6,290
1,3,10~4,3,10
7,9,31~8,9,31
7,0,279~7,1,279
4,6,221~6,6,221
4,4,115~6,4,115
1,0,238~3,0,238
1,6,167~2,6,167
1,7,286~4,7,286
6,1,241~8,1,241
3,7,160~3,8,160
2,4,310~4,4,310
1,2,198~1,5,198
2,6,4~2,6,4
3,4,196~6,4,196
5,7,129~7,7,129
5,1,272~8,1,272
1,1,190~1,3,190
3,7,105~3,9,105
2,8,69~2,8,71
9,0,41~9,2,41
5,7,180~6,7,180
5,4,102~5,5,102
2,3,29~2,5,29
0,6,176~0,9,176
4,5,112~6,5,112
4,2,257~7,2,257
5,4,224~7,4,224
0,5,9~0,7,9
6,2,149~9,2,149
1,2,310~1,4,310
0,8,277~0,9,277
4,2,66~4,2,66
6,0,22~8,0,22
0,4,47~2,4,47
6,0,217~8,0,217
3,8,275~3,9,275
5,4,105~7,4,105
3,3,318~4,3,318
4,2,248~7,2,248
2,9,122~4,9,122
1,5,191~4,5,191
3,3,254~5,3,254
8,6,305~8,8,305
6,1,320~6,1,322
8,3,20~8,5,20
2,3,170~2,4,170
0,4,259~2,4,259
4,1,77~6,1,77
5,2,136~7,2,136
6,9,38~8,9,38
8,4,298~8,4,299
5,1,253~5,2,253
6,1,179~7,1,179
9,5,26~9,7,26
4,6,215~4,6,217
5,2,284~5,3,284
5,3,260~7,3,260
6,6,70~6,7,70
1,0,37~1,0,39
3,4,281~4,4,281
1,4,249~3,4,249
7,4,287~7,6,287
0,2,33~4,2,33
7,7,225~7,9,225
2,6,299~3,6,299
4,9,277~7,9,277
6,8,147~8,8,147
4,2,116~4,2,118
1,5,305~4,5,305
2,6,121~2,9,121
9,6,72~9,8,72
8,1,280~8,3,280
5,6,192~5,6,195
1,3,304~1,5,304
2,5,178~5,5,178
2,0,172~2,3,172
4,7,317~5,7,317
3,9,31~5,9,31
5,6,124~6,6,124
0,0,55~2,0,55
0,9,156~3,9,156
2,2,39~2,3,39
3,8,272~6,8,272
2,0,227~2,3,227
7,5,180~9,5,180
8,1,244~8,1,244
6,4,36~7,4,36
9,7,1~9,8,1
6,9,36~8,9,36
1,0,148~2,0,148
6,6,266~8,6,266
7,3,134~9,3,134
1,5,215~1,7,215
1,6,35~4,6,35
0,7,168~0,7,171
5,1,171~6,1,171
7,2,122~7,5,122
5,7,177~5,9,177
6,0,2~6,1,2
3,4,26~5,4,26
6,7,186~6,9,186
2,0,15~4,0,15
2,1,156~2,4,156
1,9,157~2,9,157
6,3,10~8,3,10
0,3,173~0,5,173
7,5,206~9,5,206
1,1,294~1,4,294
2,4,180~2,6,180
4,4,163~5,4,163
4,1,317~4,3,317
1,5,94~2,5,94
1,4,245~1,6,245
1,1,250~1,3,250
6,6,312~6,8,312
8,2,27~9,2,27
7,6,231~7,7,231
7,7,16~8,7,16
3,8,217~3,9,217
6,6,4~6,7,4
7,1,236~7,4,236
5,9,176~7,9,176
5,2,286~5,4,286
6,6,169~6,7,169
9,5,191~9,7,191
4,5,189~5,5,189
0,1,132~1,1,132
4,6,67~6,6,67
1,2,118~1,5,118
9,2,241~9,3,241
5,0,201~5,2,201
4,5,137~5,5,137
3,2,41~3,5,41
2,2,37~5,2,37
3,5,19~3,6,19
9,1,242~9,2,242
3,4,269~5,4,269
1,9,4~3,9,4
1,4,240~1,6,240
7,4,298~7,8,298
0,4,156~0,6,156
6,6,297~6,7,297
5,9,196~6,9,196
4,9,135~7,9,135
8,9,229~8,9,229
6,4,240~6,4,241
7,1,26~9,1,26
0,4,213~0,6,213
9,6,198~9,7,198
6,4,295~8,4,295
8,4,47~8,6,47
9,0,2~9,2,2
4,4,231~4,5,231
4,2,110~4,4,110
7,4,280~7,6,280
9,3,148~9,5,148
7,5,111~9,5,111
3,7,6~3,9,6
1,3,212~2,3,212
1,0,151~1,1,151
6,2,41~6,5,41
3,1,189~5,1,189
1,7,120~1,8,120
3,4,14~3,4,16
2,7,128~2,9,128
3,9,20~6,9,20
5,1,12~5,4,12
8,1,261~9,1,261
9,8,199~9,8,199
1,6,266~4,6,266
3,6,80~3,7,80
6,9,197~9,9,197
2,2,122~4,2,122
3,7,67~6,7,67
8,2,13~9,2,13
5,0,238~5,1,238
4,5,78~4,6,78
8,4,60~8,6,60
1,5,292~3,5,292
1,5,41~1,7,41
1,1,201~1,3,201
3,1,226~3,5,226
2,0,17~2,3,17
6,7,251~8,7,251
4,3,32~7,3,32
6,8,97~6,8,100
0,3,109~0,3,111
2,4,84~5,4,84
7,4,66~7,6,66
8,5,143~8,8,143
1,0,42~4,0,42
"""

"9,4,52~9,7,52\n2,9,27~4,9,27\n7,5,299~7,7,299\n1,7,88~3,7,88\n7,3,68~9,3,68\n2,4,140~2,8,140\n5,6,29~5,6,31\n3,6,17~3,8,17\n6,2,16~8,2,16\n6,2,13~6,3,13\n2,9,161~4,9,161\n2,9,160~4,9,160\n4,1,4~6,1,4\n0,4,210~1,4,210\n9,7,161~9,9,161\n5,7,165~5,9,165\n8,0,142~8,0,142\n6,5,271~6,7,271\n6,2,31~7,2,31\n6,7,170~6,7,172\n0,0,145~2,0,145\n1,2,78~3,2,78\n2,8,186~2,8,187\n2,1,224~5,1,224\n3,0,283~3,0,285\n1,6,246~4,6,246\n2,1,3~3,1,3\n7,2,79~9,2,79\n4,7,25~4,7,28\n1,7,25~1,8,25\n4,3,231~6,3,231\n0,5,242~3,5,242\n4,2,134~5,2,134\n4,0,72~4,0,74\n4,4,148~4,7,148\n5,5,310~5,8,310\n4,1,74~6,1,74\n2,3,193~2,6,193\n1,6,128~1,9,128\n6,4,310~6,6,310\n3,0,26~3,1,26\n4,0,135~5,0,135\n5,1,130~5,3,130\n1,3,209~1,5,209\n0,4,181~0,4,184\n7,0,171~8,0,171\n5,5,204~5,5,207\n7,3,65~7,6,65\n0,7,226~4,7,226\n0,8,262~2,8,262\n4,5,99~5,5,99\n4,6,134~4,8,134\n5,0,69~6,0,69\n3,9,11~4,9,11\n0,1,95~0,3,95\n0,0,222~0,2,222\n1,3,44~1,6,44\n4,5,117~4,6,117\n7,4,242~7,4,244\n4,9,118~6,9,118\n5,4,245~5,5,245\n3,3,48~6,3,48\n6,3,237~6,5,237\n3,5,42~5,5,42\n7,3,21~7,5,21\n4,2,284~4,4,284\n1,6,72~3,6,72\n4,7,269~4,7,271\n0,7,163~2,7,163\n2,4,228~2,7,228\n8,3,71~8,5,71\n0,3,231~3,3,231\n1,6,229~1,9,229\n0,5,216~0,7,216\n7,9,4~9,9,4\n2,3,191~4,3,191\n9,3,262~9,4,262\n2,7,267~5,7,267\n4,5,307~4,7,307\n0,1,295~2,1,295\n4,0,203~6,0,203\n2,4,109~4,4,109\n2,5,245~2,8,245\n7,7,300~7,7,302\n0,1,112~0,3,112\n7,4,197~7,6,197\n1,8,3~4,8,3\n3,2,280~4,2,280\n4,3,276~4,5,276\n7,3,151~7,3,152\n2,2,313~2,5,313\n8,0,25~8,2,25\n8,4,267~8,6,267\n3,7,210~4,7,210\n5,4,321~5,5,321\n3,3,105~6,3,105\n8,8,269~8,8,272\n5,8,145~8,8,145\n0,7,173~0,7,175\n4,4,101~4,7,101\n5,8,204~7,8,204\n7,6,194~7,8,194\n8,6,130~8,8,130\n3,0,23~5,0,23\n4,7,219~6,7,219\n2,0,140~2,1,140\n1,8,263~1,8,264\n0,1,307~0,1,309\n4,9,269~6,9,269\n7,5,300~7,6,300\n1,6,320~3,6,320\n6,7,37~6,8,37\n6,7,226~6,7,229\n4,5,261~4,8,261\n4,1,59~4,3,59\n1,8,301~4,8,301\n6,4,215~9,4,215\n6,8,278~6,8,279\n8,7,168~8,9,168\n8,4,52~8,7,52\n3,7,234~3,9,234\n0,8,145~0,8,147\n7,0,280~9,0,280\n5,6,152~5,7,152\n5,4,125~5,7,125\n5,4,19~7,4,19\n8,2,114~8,4,114\n6,6,277~8,6,277\n2,7,220~2,7,223\n0,0,6~0,0,7\n6,9,227~8,9,227\n5,2,210~8,2,210\n6,0,50~8,0,50\n5,6,186~5,8,186\n4,5,161~4,7,161\n5,2,245~6,2,245\n0,3,37~0,5,37\n4,1,251~5,1,251\n7,1,281~9,1,281\n2,4,208~4,4,208\n2,5,40~5,5,40\n2,8,300~5,8,300\n0,5,290~3,5,290\n4,6,17~4,6,19\n5,3,313~5,5,313\n8,7,144~8,7,146\n2,1,280~2,3,280\n6,4,69~9,4,69\n0,8,72~2,8,72\n7,0,33~9,0,33\n2,9,30~2,9,32\n4,7,151~4,9,151\n8,5,253~8,8,253\n4,7,181~7,7,181\n4,5,118~6,5,118\n3,1,321~5,1,321\n3,6,264~6,6,264\n6,7,223~6,8,223\n4,6,139~6,6,139\n6,6,225~6,6,227\n0,0,40~2,0,40\n3,4,112~5,4,112\n2,8,259~3,8,259\n2,7,231~4,7,231\n8,7,67~9,7,67\n6,0,84~9,0,84\n3,9,25~6,9,25\n4,7,117~4,9,117\n5,2,167~5,4,167\n9,0,160~9,3,160\n9,3,182~9,5,182\n9,6,126~9,8,126\n5,2,296~5,5,296\n5,7,289~8,7,289\n3,4,7~5,4,7\n8,4,270~8,7,270\n4,0,259~4,3,259\n2,7,39~5,7,39\n7,1,6~7,4,6\n6,6,7~9,6,7\n1,6,1~2,6,1\n4,4,33~4,4,35\n6,8,191~7,8,191\n5,4,148~5,5,148\n5,6,248~5,9,248\n5,4,252~8,4,252\n5,6,247~5,7,247\n7,2,157~7,4,157\n3,9,143~5,9,143\n3,7,309~6,7,309\n5,3,34~5,5,34\n9,4,278~9,4,278\n2,7,105~2,8,105\n0,9,2~4,9,2\n5,0,240~5,1,240\n3,7,158~5,7,158\n1,6,292~2,6,292\n6,9,26~6,9,28\n0,8,258~3,8,258\n3,1,169~6,1,169\n8,6,112~8,6,114\n6,8,2~8,8,2\n5,5,120~7,5,120\n0,0,255~2,0,255\n2,6,32~4,6,32\n9,0,258~9,3,258\n7,0,165~9,0,165\n0,7,57~0,9,57\n4,8,282~7,8,282\n1,1,50~1,3,50\n5,6,197~5,6,199\n1,8,55~1,9,55\n4,9,300~6,9,300\n0,8,275~0,9,275\n9,1,34~9,3,34\n2,3,95~2,5,95\n4,3,4~4,5,4\n6,1,274~8,1,274\n2,1,41~2,3,41\n9,8,288~9,9,288\n1,9,84~3,9,84\n3,6,58~3,8,58\n5,2,289~5,5,289\n6,0,209~8,0,209\n9,5,133~9,7,133\n8,0,222~9,0,222\n2,3,110~2,5,110\n3,3,16~6,3,16\n2,6,166~2,8,166\n5,0,292~5,3,292\n5,0,89~7,0,89\n5,8,74~5,8,76\n5,3,88~5,4,88\n9,1,22~9,3,22\n9,1,5~9,3,5\n5,3,128~7,3,128\n3,4,227~3,6,227\n4,1,325~6,1,325\n1,8,215~3,8,215\n4,7,83~4,7,84\n8,8,273~8,8,275\n1,0,144~1,2,144\n3,7,304~3,8,304\n7,0,139~9,0,139\n9,6,29~9,8,29\n4,5,262~6,5,262\n4,4,106~4,6,106\n7,6,233~8,6,233\n3,0,144~4,0,144\n5,5,16~8,5,16\n4,1,312~4,1,315\n6,4,13~9,4,13\n5,4,29~8,4,29\n7,7,93~7,9,93\n0,1,320~3,1,320\n0,2,274~1,2,274\n4,5,91~4,5,94\n5,7,134~5,7,136\n5,4,152~7,4,152\n1,0,138~4,0,138\n2,2,182~2,5,182\n5,1,296~7,1,296\n3,6,295~6,6,295\n3,7,132~5,7,132\n9,0,135~9,3,135\n2,0,158~2,2,158\n8,7,21~8,7,22\n0,3,39~0,4,39\n7,0," <> ...

Part 1

defmodule Block do
  defstruct [:x, :y, :z, supported_by: [], label: ""]
end

defmodule Part1 do
  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(fn line ->
      line
      |> String.split("~")
      |> Enum.map(fn coords ->
        coords
        |> String.split(",")
        |> Enum.map(&String.to_integer/1)
      end)
      |> Enum.zip()
    end)
    |> Enum.with_index()
    |> Enum.map(fn {[{ax, bx}, {ay, by}, {az, bz}], i} ->
      %Block{
        x: ax..bx,
        y: ay..by,
        z: az..bz,
        label: List.to_string([i + ?A])
      }
    end)
  end

  def overlaps(a, b) do
    !([:x, :y]
      |> Enum.any?(fn dim ->
        Range.disjoint?(Map.get(a, dim), Map.get(b, dim))
      end))
  end

  # blocks is remaining blocks that have not been processed
  # resting is where they ended up
  def process(blocks, resting \\ [])
  def process([], resting), do: resting

  def process(blocks, resting) do
    [head | tail] = blocks
    resting = Enum.sort(resting, fn a, b -> b.z.last <= a.z.last end)

    supporters =
      resting
      |> Enum.filter(fn r -> overlaps(head, r) end)

    max_z =
      if supporters == [] do
        0
      else
        Enum.map(supporters, fn s -> s.z.last end) |> Enum.max()
      end

    supporters = Enum.filter(supporters, fn s -> s.z.last == max_z end)

    os..oe = head.z
    z = (max_z + 1)..(oe - os + max_z + 1)
    resting = [%Block{head | z: z, supported_by: supporters} | resting]

    process(tail, resting)
  end
end

blocks = Part1.parse(input) |> Enum.sort(fn a, b -> a.z.first <= b.z.first end)

load_bearing =
  Part1.process(blocks)
  |> Enum.filter(fn b -> length(b.supported_by) == 1 end)
  |> Enum.flat_map(fn b -> b.supported_by end)
  |> Enum.map(fn b -> b.label end)
  |> Enum.into(MapSet.new())

blocks
|> Enum.map(fn b -> b.label end)
|> Enum.into(MapSet.new())
|> MapSet.difference(load_bearing)
|> MapSet.size()

517

Part 2

defmodule Part2 do
  def parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(fn line ->
      line
      |> String.split("~")
      |> Enum.map(fn coords ->
        coords
        |> String.split(",")
        |> Enum.map(&String.to_integer/1)
      end)
      |> Enum.zip()
    end)
    |> Enum.with_index()
    |> Enum.map(fn {[{ax, bx}, {ay, by}, {az, bz}], i} ->
      {i, {ax..bx, ay..by, az..bz}}
    end)
    |> Enum.into(Map.new())
  end

  def overlaps(blocks, a, b) do
    {ax, ay, _} = blocks[a]
    {bx, by, _} = blocks[b]
    !Range.disjoint?(ax, bx) && !Range.disjoint?(ay, by)
  end

  def settle(block, blocks, bottoms, tops, supporters) do
    highest =
      if map_size(tops) > 0 do
        tops |> Map.keys() |> Enum.max()
      else
        0
      end

    # Starting at the highest layer that exists and moving down,
    # we're going to look for supporters.
    {z, s} =
      highest..1//-1
      |> Stream.map(fn z ->
        {
          # height
          z,
          # everything that tops off there
          Map.get(tops, z, [])
          |> Enum.filter(fn other ->
            # that overlaps with this block
            overlaps(blocks, block, other)
          end)
        }
      end)
      # skip layers where we fall right past
      |> Stream.filter(fn {_, s} -> length(s) > 0 end)
      # grab the first one (or default to lying on the ground)
      |> Enum.at(0, {0, []})

    # This block will be just above its supporters' tops
    bottom = z + 1
    # 1..5 sitting above 0 would have a top of 5
    # 5..10 sitting above 3 would have a top of 8
    top = z + Range.size(elem(blocks[block], 2))

    # Update our maps and return
    {
      Map.update(bottoms, bottom, [block], fn existing ->
        [block | existing]
      end),
      Map.update(tops, top, [block], fn existing ->
        [block | existing]
      end),
      Map.put(supporters, block, Enum.into(s, MapSet.new()))
    }
  end

  def fallers(bottoms, supporters, z, fallen) do
    Map.get(bottoms, z, [])
    |> Enum.filter(fn block ->
      MapSet.subset?(supporters[block], fallen)
    end)
    |> Enum.into(MapSet.new())
  end
end

blocks = Part2.parse(input)

{bottoms, tops, supporters} =
  blocks
  |> Enum.sort_by(fn b ->
    ranges = elem(b, 1)
    elem(ranges, 2)
  end)
  |> Enum.map(fn {k, _} -> k end)
  |> Enum.reduce(
    {%{}, %{}, %{}},
    fn block, {bottoms, tops, supporters} ->
      Part2.settle(block, blocks, bottoms, tops, supporters)
    end
  )

# part1 = map_size(blocks) - (supporters
# |> Stream.map(fn {_k, v} ->
#   if MapSet.size(v) == 1 do
#     Enum.at(v, 0)
#   end
# end)
# |> Stream.filter(&(&1 != nil))
# |> Enum.into(MapSet.new)
# |> MapSet.size)

highest = bottoms |> Map.keys() |> Enum.max()

part2 =
  blocks
  |> Map.keys()
  |> Enum.map(fn block ->
    (2..highest
     |> Enum.reduce(
       MapSet.new([block]),
       fn z, fallen ->
         MapSet.union(fallen, Part2.fallers(bottoms, supporters, z, fallen))
       end
     )
     |> MapSet.size()) - 1
  end)
  |> Enum.sum()

part2

61276