22.js

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

function findFalls (seen, bricks, falls = new Set(), i = -1) {
  while (true) {
    let fall = false

    for (let j = 0; j < bricks.length; j++) {
      if (i == j) continue

      const brick = bricks[j]
      let ok = true

      for (let [x, y, z] of brick) {
        if (z == 1) { ok = false; break }

        if (
          seen.has(`${x},${y},${z-1}`) &&
          !brick.find(([a,b,c]) => a == x && b == y && c == z - 1)
        ) { ok = false; break }
      }

      if (ok) {
        fall = true
        falls.add(j)

        let newBrick = []

        for (let [x, y, z] of brick) {
          seen.delete(`${x},${y},${z}`)
          seen.add(`${x},${y},${z-1}`)
          newBrick.push([x, y, z-1])
        }

        brick.splice(0, brick.length, ...newBrick)
      }
    }

    if (!fall) break
  }
}

(async function main () {
  for (let [name, rawData] of [['example1', example1], ['input', input]]) {
    const bricks = rawData
      .split('\n')
      .map(line => line.split('~').map(part => part.split(',').map(Number)))
      .map(brick => {
        const [[sx, sy, sz], [ex, ey, ez]] = brick

        if (sx == ex && sy == ey) {
          return Array(ez-sz+1).fill().map((_, i) => [sx, sy, sz+i])
        } else if (sx == ex && sz == ez) {
          return Array(ey-sy+1).fill().map((_, i) => [sx, sy+i, sz])
        } else if (sz == ez && sy == ey) {
          return Array(ex-sx+1).fill().map((_, i) => [sx+i, sy, sz])
        }
      })
    const seens = new Set()

    for (let brick of bricks) {
      for (let cube of brick) {
        seens.add(cube.toString())
      }
    }

    findFalls(seens, bricks)

    for (let part2 of [false, true]) {
      const seen = new Set(seens)
      let ans = 0

      console.log('---------')
      console.log('|       |')
      console.log('| START |')
      console.log('|       |')
      console.log('---------')
      console.time(`start ${name} ${part2 ? 'part 2' : 'part 1'}`)

      const old_seen = new Set(seen)
      const old_bricks = structuredClone(bricks)

      for (let i = 0; i < bricks.length; i++) {
        const bricks2 = structuredClone(old_bricks)
        const seen2 = new Set(old_seen)
        const falls = new Set()

        for (let cube of bricks[i]) {
          seen2.delete(cube.toString())
        }

        findFalls(seen2, bricks2, falls, i)

        if (part2) ans += falls.size
        else ans += falls.size == 0

        for (let cube of bricks[i]) {
          seen2.add(cube.toString())
        }
      }

      console.log(ans);
      console.timeEnd(`start ${name} ${part2 ? 'part 2' : 'part 1'}`)
    }
  }
})()