TEST DATA FOR `printtree'
A Zip file of this data
is available.
Input for test 1
6
5
1
1
3
-1
5
Output for test 1
5
.1
..2
..3
...4
.6
Input for test 2
10
9
4
7
7
1
3
-1
7
3
7
Output for test 2
7
.3
..6
..9
...1
....5
.4
..2
.8
.10
Input for test 3
16
12
11
11
6
10
11
15
6
12
7
10
10
11
11
-1
2
Output for test 3
15
.7
..10
...5
...11
....2
.....16
....3
....6
.....4
.....8
....13
....14
...12
....1
....9
Input for test 4
17
9
13
-1
13
3
3
6
4
13
12
3
11
6
1
9
5
11
Output for test 4
3
.5
..16
.6
..7
..13
...2
...4
....8
...9
....1
.....14
....15
.11
..12
...10
..17
Input for test 5
42
-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Output for test 5
1
.2
..3
...4
....5
.....6
......7
.......8
........9
.........10
..........11
...........12
............13
.............14
..............15
...............16
................17
.................18
..................19
...................20
....................21
.....................22
......................23
.......................24
........................25
.........................26
..........................27
...........................28
............................29
.............................30
..............................31
...............................32
................................33
.................................34
..................................35
...................................36
....................................37
.....................................38
......................................39
.......................................40
........................................41
.........................................42
Input for test 6
82
44
82
52
79
54
9
25
12
58
58
54
37
5
11
1
12
66
66
68
59
42
68
80
16
36
52
21
27
14
16
68
12
58
16
14
54
-1
60
35
19
56
37
14
49
44
11
57
17
68
29
20
36
12
12
54
49
3
42
73
55
29
35
71
11
14
58
68
11
26
79
21
53
9
4
31
25
79
49
11
78
4
41
Output for test 6
37
.12
..8
..16
...24
...30
...34
..32
..53
...72
..54
...5
....13
...11
....14
.....29
......50
......61
.....35
......39
......62
.....43
.....65
....46
....64
....68
.....19
......40
.....22
.....31
......75
.....49
......44
.......1
........15
.......45
......56
.......41
........82
.........2
......78
.......80
........23
.....67
....79
.....4
......74
......81
.....70
.....77
...36
....25
.....7
.....76
....52
.....3
......57
.......47
.....26
......69
...55
....60
.....38
.42
..21
...27
....28
...71
....63
..58
...9
....6
....73
.....59
......20
.......51
...10
...33
...66
....17
.....48
....18
Input for test 7
207
59
26
109
121
81
24
153
88
122
5
12
24
57
91
198
20
46
39
47
37
56
127
201
134
91
121
126
72
126
92
24
134
145
125
196
127
81
92
138
113
134
65
6
16
109
200
24
204
95
125
134
24
48
155
187
145
204
57
26
173
80
31
126
206
134
116
126
40
127
28
58
109
135
167
127
43
127
188
149
204
155
114
76
-1
22
52
48
155
125
40
146
176
12
48
22
55
26
186
28
12
115
45
100
125
29
51
138
203
84
18
51
86
87
121
84
28
185
142
38
64
53
191
53
81
133
69
182
40
65
97
155
101
134
84
126
107
134
72
130
27
174
88
146
138
26
174
207
85
80
22
3
168
173
160
134
188
89
126
17
204
55
153
139
143
72
205
182
47
125
114
111
126
52
133
127
115
148
59
189
101
20
204
46
106
22
145
134
59
116
174
48
66
38
130
201
167
134
17
107
61
146
66
123
134
31
174
37
Output for test 7
84
.109
..3
...151
..45
...102
..72
...28
....70
....99
....116
.....66
......192
......202
.....189
......179
...138
....39
.....18
......110
....107
.....136
.....199
....144
...165
.115
..101
...132
...180
..176
...92
....30
....38
.....119
.....193
.134
..24
...6
....43
.....76
......83
...12
....11
....93
....100
.....103
...31
....62
....205
.....166
...47
....19
....168
.....152
...52
....86
.....112
....173
.....60
.....153
......7
......162
..32
..41
..51
...106
....184
...111
....171
..65
...42
...129
..133
...125
....34
....50
....89
.....157
....104
....169
...174
....141
....146
.....91
......14
......25
.....143
......164
.....201
......23
......195
....190
....206
.....64
......120
..137
..155
...54
...81
....5
.....10
....37
.....20
......16
.......44
......181
.....207
......147
....124
...88
....8
....142
.....118
...131
..187
...55
....96
....161
..197
..204
...48
....53
.....121
......4
......26
.......2
.......59
........1
........178
........188
.........78
.........156
.......97
........130
.........139
..........163
.........194
.......145
........33
........56
.........21
........186
.........98
......114
.......82
.......170
.....123
......203
.......108
....87
.....113
......40
.......68
.......90
.......128
....94
....191
.....122
......9
...57
....13
....58
.....71
...80
....61
.....200
......46
.......17
........159
........198
.........15
.......183
....149
.....79
...160
....154
...182
....127
.....22
......85
.......148
........177
......95
.......49
......150
......185
.......117
.....36
.....69
......126
.......27
........140
.......29
........105
.......63
.......67
.......135
........73
.......158
.......172
.....75
.....77
.....175
....167
.....74
.....196
......35
Input for test 8
416
32
311
138
368
331
317
338
185
347
142
118
386
187
401
97
416
168
261
325
406
118
383
28
33
262
6
269
274
215
282
259
413
294
332
274
295
395
205
283
110
85
116
27
219
203
322
353
103
365
242
372
233
125
55
370
117
196
416
195
258
223
28
57
193
226
274
72
304
15
359
96
370
410
205
129
61
38
163
38
364
281
143
212
178
381
142
71
396
97
294
393
294
173
116
102
68
294
194
212
386
380
179
69
192
94
11
147
36
40
205
130
290
374
205
130
200
314
366
155
364
185
68
158
2
290
15
133
40
261
90
306
16
66
117
328
205
95
306
140
371
187
27
200
50
37
347
343
185
53
230
27
128
156
77
306
82
415
142
282
43
215
38
374
321
217
374
113
205
129
70
294
312
161
278
205
214
223
355
406
207
356
160
111
102
366
381
59
314
90
185
386
190
215
110
406
10
335
160
329
205
379
308
90
413
294
33
354
314
115
202
212
90
334
226
147
175
250
304
360
94
110
26
52
162
173
332
178
224
388
36
220
4
59
147
278
340
406
110
363
319
413
270
126
317
294
370
295
24
411
334
39
207
123
20
171
375
321
369
38
69
311
205
79
102
192
168
128
319
205
116
388
254
317
33
108
38
4
38
307
212
83
220
347
255
160
380
113
152
413
221
321
69
30
-1
116
223
248
110
404
283
36
233
276
33
111
278
295
161
327
390
90
116
90
16
359
129
332
157
142
79
171
110
342
193
343
210
172
337
79
264
326
90
40
175
142
301
307
37
147
109
225
54
38
43
337
205
404
301
160
354
246
187
62
54
146
272
367
152
109
298
158
342
54
82
108
55
304
155
406
110
129
242
233
286
295
40
205
343
189
205
314
297
27
385
131
380
382
136
100
195
108
189
20
154
195
264
80
285
365
140
298
333
221
295
193
343
65
260
271
387
90
328
27
176
375
262
Output for test 8
294
.33
..24
...248
....297
.....382
......387
.......410
........73
..206
..274
...28
....23
....62
.....353
......47
...35
...66
....133
.....127
..304
...68
....96
.....71
......87
....122
...218
...367
....357
.90
..130
...111
....183
....305
...115
....209
..189
...379
....201
...392
..203
...45
..212
...83
....281
.....81
...99
...211
...280
..311
...2
....124
...261
....18
....129
.....75
.....169
.....316
.....371
......140
.......139
.......400
..313
..332
...34
...226
....65
.....407
....214
.....176
......414
...317
....6
.....26
......222
....244
....273
..411
...249
.92
.97
..15
...69
....103
.....48
....260
.....408
....292
...126
....243
..89
.171
..255
...284
..321
...164
...257
...291
.205
..38
...77
....154
.....394
...79
....263
....320
....329
.....199
...162
....224
.....228
...259
....31
...276
....303
...278
....174
....235
....306
.....131
......385
.......384
.....138
......3
.....155
......119
......368
.......4
........232
........277
...343
....147
.....107
.....215
......29
......161
.......173
........93
........225
.........341
.......308
........202
.........210
..........326
...........331
............5
......193
.......64
.......324
.......405
.....234
.....339
....325
.....19
....378
....406
.....20
......254
.......272
........356
.........181
......393
.......91
.....179
......102
.......95
........137
.......184
.......264
........330
........396
.........88
.....195
......59
.......187
........13
........141
........352
.......233
........52
.........223
..........61
...........76
..........177
..........296
........302
........373
......390
.......310
......395
.......37
........145
........338
.........7
.....237
.....369
......258
.......60
..74
..110
...40
....109
.....340
......236
.....359
......70
.......170
......315
....128
.....152
......288
......358
.....267
....333
.....402
....376
...194
....98
...221
....290
.....112
.....125
......53
.......149
....403
...238
...298
....360
.....219
......44
....401
.....14
...322
....46
...370
....55
.....54
......342
.......323
.......362
......354
.......207
........180
........252
.......350
......363
.......239
.....366
......118
.......11
........106
.......21
......185
.......8
.......121
.......148
.......190
........192
.........104
.........265
....72
.....67
....246
.....351
..114
..136
...388
....229
....271
.....409
..168
...17
...266
..175
...216
...334
....213
....250
.....217
......165
..200
...116
....42
....94
.....105
.....220
......231
......282
.......30
........293
.......159
....270
.....242
......50
.......144
......372
.......51
....295
.....36
......108
.......275
.......365
........49
........399
.......391
......230
.......150
......301
.......336
.......348
.....247
.....307
......279
......337
.......328
........135
........412
.......345
.....375
......256
......415
.......157
........318
.....404
......299
......347
.......9
.......146
........355
.........178
..........84
..........227
.......283
........39
.........251
........300
....312
.....172
......327
.......309
...143
....82
.....156
......153
.....364
......80
.......397
......120
..262
...25
...416
....16
.....132
.....314
......117
.......56
.......134
......188
......208
......381
.......85
........41
.......186
....58
..269
...27
....43
.....160
......182
......198
......285
.......398
......349
.....344
....142
.....10
......196
.......57
........63
.....86
.....158
......123
.......253
......361
.....319
......240
......268
.....335
......197
....151
....383
.....22
....413
.....32
......1
.....204
.....241
.....289
..346
..377
..380
...101
...286
....374
.....113
......167
......287
.....163
......78
.....166
...386
....12
....100
.....389
....191
.245
Input for test 9
500
320
479
74
283
449
278
460
427
222
332
466
94
251
149
236
362
410
444
436
200
257
194
416
193
259
432
233
393
452
51
15
82
480
130
353
88
311
321
431
239
247
385
448
51
37
491
120
67
480
320
193
281
108
320
7
364
286
354
467
362
231
120
188
49
406
17
457
143
153
317
271
320
331
311
121
467
362
295
233
256
259
176
462
436
463
466
223
134
130
352
383
441
176
339
454
107
314
473
238
153
405
436
110
499
427
325
491
102
352
436
497
350
128
200
259
407
2
394
137
115
199
178
311
83
236
277
76
216
247
136
348
321
478
363
116
281
129
466
166
405
321
362
88
79
252
77
247
208
288
238
2
399
480
2
211
485
223
43
339
136
403
102
477
339
68
449
290
395
383
17
61
320
257
148
500
277
189
84
119
492
47
339
121
404
46
243
254
207
449
305
110
245
363
191
74
402
11
311
84
463
343
95
322
406
294
486
481
215
54
54
320
148
283
193
178
462
89
148
373
355
350
436
115
290
477
199
311
402
451
246
77
227
115
331
281
76
81
274
215
65
98
356
267
47
461
92
79
478
362
393
457
281
448
329
462
84
4
402
436
172
98
117
249
252
363
249
120
150
320
356
321
420
125
270
119
167
60
238
278
242
477
339
477
34
223
314
200
242
356
387
204
327
11
270
87
279
273
45
388
473
427
223
155
363
336
458
436
401
395
123
150
79
224
394
61
449
295
406
498
477
420
102
281
54
404
421
236
437
8
323
121
102
248
355
183
316
482
119
283
394
498
355
211
103
375
494
236
457
400
277
94
223
274
47
193
115
447
420
223
63
460
359
259
479
398
257
243
240
252
12
356
130
43
310
225
70
483
422
233
399
258
154
320
80
457
338
249
288
359
483
162
83
362
155
194
113
259
77
267
155
316
282
462
115
19
259
120
72
314
491
173
215
427
43
402
345
155
193
339
307
352
76
444
480
70
83
155
311
83
50
215
415
26
343
108
-1
145
300
295
13
320
363
378
77
394
256
108
406
467
133
379
289
496
118
484
461
307
345
270
84
468
110
457
134
128
356
223
479
24
448
178
159
84
264
154
320
436
448
191
436
375
243
155
325
442
204
79
178
334
126
404
110
394
493
12
431
53
283
27
430
Output for test 9
436
.19
..405
...101
...140
.84
..178
...122
...215
....208
.....148
......174
......212
......218
....239
.....40
....412
....431
.....39
.....496
......453
...471
...488
..199
...121
....75
....183
.....335
....331
.....73
.....234
...226
..256
...80
....384
...446
..460
...7
....55
...361
..473
...98
....241
....261
...300
....438
.102
..108
...53
....497
.....111
...435
...447
....357
..162
...391
..322
...203
..332
...10
.110
..103
...344
..191
...194
....22
....395
.....168
.....309
...479
....2
.....117
......262
.....151
.....154
......382
......475
....364
.....56
....468
.....461
......245
.......192
......456
..462
...83
....124
....392
....426
....429
...216
....128
.....113
......396
.....465
...255
...403
....161
..492
...180
.222
..9
.259
..25
..81
...237
..115
...120
....47
.....181
.....244
.....354
......58
....62
....267
.....243
......186
......367
......482
.......337
.....399
......152
......380
....407
.....116
......135
...223
....87
.....295
......78
......317
.......70
........376
........425
......439
....157
....285
....302
....352
.....90
.....109
.....421
......326
....359
.....362
......16
......60
.......277
........126
.........490
........176
.........82
..........32
.........93
........350
.........112
.........221
......77
.......146
.......231
........61
.........171
.........315
.......398
........365
.......444
........18
........423
......142
......249
.......263
.......266
.......387
........290
.........167
..........276
.........224
..........313
......393
.......28
.......250
.....389
....467
.....59
.....76
......127
......236
.......15
........31
.......125
........273
.........297
.......327
........292
.......347
......422
.......378
........443
.....449
......5
......166
.......139
......189
.......177
......316
.......336
........305
.........190
.......401
........308
...233
....27
.....499
......104
....79
.....144
.....247
......41
......129
.......137
........119
.........179
.........275
.........338
..........386
......147
.....312
.....487
....379
.....451
......229
...356
....242
.....280
.....288
......149
.......14
......388
.......299
....270
.....274
......238
.......99
.......150
........268
........311
.........37
..........45
...........298
.........74
..........3
..........195
.........123
..........310
...........374
.........198
.........227
..........232
.........428
.......278
........6
........279
.........296
......353
.......35
.....294
......205
.....459
....289
.....452
......29
....371
....466
.....11
......197
......293
.....86
.....138
...404
....184
....325
.....106
.....484
......455
....491
.....46
......185
.....107
......96
.....410
......17
.......66
.......170
..363
...134
....88
.....36
.....143
......68
.......165
....464
...193
....24
.....469
....51
.....30
.....44
....214
....355
.....220
.....334
......489
.....342
....418
...265
...304
...442
....485
.....156
..397
..406
...65
....240
.....368
...204
....291
....486
.....206
...318
...448
....43
.....158
.....373
......219
.....414
....253
....470
....478
.....133
......450
.....248
......333
.307
..420
...272
...321
....38
....132
....141
....271
.....71
...358
..457
...67
....48
...251
....13
.....440
...348
....131
...385
....42
...463
....85
....200
.....20
.....114
.....287
.477
..163
..225
...375
....345
.....416
......23
.....458
......306
....481
.....207
......188
.......63
........360
..281
...52
...136
....130
.....34
......284
.....89
......217
.....372
....160
...235
...252
....145
.....437
......328
....264
.....474
....369
...323
....330
..283
...4
....257
.....21
.....173
......411
.....366
...213
...339
....94
.....12
......370
......495
.....351
....159
.....472
....164
....182
....282
.....402
......196
......228
......258
.......381
......415
.......432
........26
.........433
....419
...498
....319
....341
..320
...1
...50
....430
.....500
......175
...54
....209
....210
....324
...72
....408
...172
....260
...211
....155
.....303
.....394
......118
.......454
........95
.........202
......314
.......97
.......286
........57
.......409
......340
......445
......493
.......494
........346
.....400
......349
.....417
.....427
......8
.......329
........254
.........187
......105
......301
......413
.....483
......377
......390
....343
.....201
.....434
...269
...383
....91
....169
...441
....92
.....246
......230
...476
.480
..33
..49
...64
..153
...69
...100
..424
Input for test 10
500
353
260
60
246
273
500
430
134
196
366
286
315
38
164
8
229
249
500
355
279
238
333
279
392
98
368
201
442
147
302
338
392
181
477
442
8
279
345
292
289
191
411
61
368
279
486
214
67
134
61
232
477
238
156
327
107
457
449
426
232
273
228
14
340
27
173
431
450
405
209
283
249
83
240
182
182
320
385
282
404
258
337
250
238
194
58
433
253
227
169
373
35
65
238
260
35
317
241
214
300
181
7
241
330
158
406
449
350
162
168
414
117
27
57
110
153
334
95
480
395
28
153
435
102
123
9
51
345
101
260
18
183
192
468
175
438
106
426
442
301
214
200
282
379
489
282
225
29
366
156
86
61
90
468
426
411
37
252
489
179
282
242
341
273
273
247
147
355
237
58
7
500
19
84
183
219
237
125
183
282
133
350
226
102
253
236
40
7
241
481
50
427
177
421
197
324
273
325
35
246
7
22
4
43
4
427
274
422
442
414
273
61
418
225
153
238
33
265
285
450
379
34
477
287
327
211
181
47
22
68
343
289
68
440
70
406
211
164
414
57
168
440
332
211
242
168
168
484
353
161
181
422
355
225
499
262
494
216
433
42
440
115
238
269
457
59
422
316
321
360
454
298
411
461
110
295
172
481
457
437
494
237
267
93
114
449
152
219
102
31
200
238
19
191
54
267
226
210
389
237
99
201
355
180
438
304
5
492
40
225
232
73
247
359
153
415
47
486
70
46
52
238
80
484
267
418
273
52
263
442
40
180
329
389
95
46
391
237
25
237
500
227
101
228
359
323
23
320
120
381
33
141
40
275
457
253
223
457
265
468
112
307
359
297
466
257
143
65
39
208
40
267
334
90
267
336
403
475
297
310
166
414
73
379
39
51
345
225
457
153
254
289
90
466
234
110
477
323
242
334
432
389
414
297
366
169
412
359
432
62
-1
241
209
389
7
120
39
225
84
124
42
168
148
415
201
457
168
253
373
226
40
164
169
273
327
358
282
191
322
279
9
494
147
18
60
104
98
263
494
282
492
143
421
324
442
457
238
246
248
181
240
4
279
247
345
426
250
477
4
404
314
164
285
238
353
30
426
158
56
353
141
111
172
389
110
426
437
170
107
431
432
315
102
450
331
36
206
468
449
102
Output for test 10
411
.42
..260
...2
...95
....118
....335
...130
..421
...194
....85
...453
.156
..54
...295
....276
..150
.273
..5
...307
....362
..61
...43
....204
...50
....191
.....41
.....294
.....438
......136
......305
...152
....287
.....224
...212
..164
...14
....63
...238
....21
....53
....84
.....174
.....419
....94
....216
.....258
......81
....263
.....329
......333
.......22
........202
........229
.........16
.....448
....292
.....39
......369
......385
.......78
......417
....322
.....439
....457
.....57
......114
.......285
........219
.........176
.........288
........473
......240
.......74
.......461
........274
.........207
.....265
......218
......359
.......314
........471
.......345
........38
.........13
........128
........387
........465
.......363
.......408
.....279
......20
......23
.......347
......37
.......157
......45
......440
.......234
........395
.........120
..........349
..........416
.......242
........162
.........109
........245
........399
.......261
......463
.....355
......19
.......173
........66
.......293
......168
.......110
........115
.........262
..........256
........275
.........354
........396
........485
.......241
........98
.........25
..........339
.........447
........103
........189
........412
.........407
.......246
........4
.........203
.........205
.........462
.........469
........200
.........142
.........291
........458
.......247
........166
.........381
..........350
...........108
...........182
............75
............76
........313
........464
.......422
........208
.........370
........252
.........158
..........105
..........478
........267
.........283
..........71
.........296
.........325
..........198
.........372
.........375
.......427
........192
.........133
..........181
...........33
............217
............351
...........101
............129
............343
.............231
...........227
............89
............342
...........251
...........460
........206
.........497
......253
.......88
.......185
.......356
.......428
......303
.....358
......436
.....389
......299
......334
.......117
........112
.........361
.......373
........91
........429
.......400
......402
......414
.......111
........482
.......210
........298
.........272
.......239
.......382
.......403
........377
......484
.......248
........459
.......324
........196
.........9
..........126
..........441
........454
.........271
.....426
......59
.......266
......138
......155
......466
.......365
.......394
......477
.......34
........222
.......52
........321
.........269
..........264
........328
.......223
........357
.......397
.......468
........134
.........8
..........15
..........36
...........496
.........49
........154
........360
.........270
........498
......486
.......46
........320
.........77
.........348
........336
.........376
.......318
.....456
....474
...432
....401
....409
....491
...472
..165
..197
...195
..211
...226
....183
.....132
.....175
......135
.....179
......160
....297
.....364
.....379
......144
......221
......384
.....404
......80
.......323
........346
........398
......470
....430
.....7
......102
.......124
........420
.......184
.......289
........40
.........187
.........309
.........331
..........495
.........353
..........1
..........249
...........17
...........72
..........475
...........378
..........480
...........119
.........371
.........431
..........67
...........48
..........490
........232
.........51
..........127
..........386
.........60
..........3
..........445
.........311
........392
.........24
.........32
.......493
.......500
........6
........18
.........131
.........444
........172
.........277
.........483
........341
.........163
......171
......188
......201
.......27
........65
.........93
..........284
.........368
..........26
..........44
........113
.......302
........30
.........476
.......425
......415
.......316
........268
.......424
...237
....169
.....90
......153
.......116
.......122
.......215
.......315
........12
........492
.........308
.........451
.......390
......374
......393
.....406
......106
.......137
......236
.......186
.....433
......87
......259
....177
.....193
....282
.....79
.....143
......367
......452
.....146
.....161
......250
.......83
........73
.........312
.........383
.......467
.....180
......304
.......306
......332
.......243
.....437
......280
......487
.....450
......68
.......230
.......233
......220
......494
.......257
........366
.........10
.........149
.........405
..........69
.......281
.......442
........28
.........121
........35
.........92
.........96
.........199
........139
........209
.........70
..........235
..........319
.........413
........330
.........104
..........446
........455
.......449
........58
.........86
..........151
.........170
..........488
........107
.........56
..........479
.........489
..........145
..........159
........286
.........11
........499
.........255
....300
.....100
....338
.....31
......290
....340
.....64
...244
..327
...55
...225
....147
.....29
......148
.......423
.....167
.....443
....214
.....47
......228
.......62
........410
.......344
......317
.......97
.....99
......301
.......140
.....141
......352
......481
.......190
.......278
....254
.....391
......337
.......82
....310
.....380
....388
....418
.....213
.....326
...435
....123
.....125
......178
..434