算法题：Order of Tasks

题目描述

Thereare V tasks to do. Some task(s) can begin only after a particular task ends,which we will call precedence relation. A graph indicating precedence relationof tasks is given. In this graph, each task is denoted as vertex, and the precedencerelation as directed edge. Note there is no cycle with this graph (cycle refers to a path that starts from one vertex and returns to the same vertex). The graph below is one example of such graph

In this graph, task 1 can start after task 4 ends and task 6can when task 5 and task 7 end; there is no cycle with this graph.

Given V tasks and their precedence relations, write a programthat finds the order by which one person can does one task at a time. Usuallythere are a number of possible orders so all you need to do is present just oneof them. Since a graph with a cycle is not given in input, you don’t need toconsider error-handling in such case. In the graph with no cycle, possibleorder(s) always exist.

[Constraints]

The total number of vertices, V, in the graph is 5≤V≤1000.

Time limit: 1 sec for 10 test cases combined

[Input]

10 test cases are given. Throughout 20 lines, one test case isgiven for every two lines. In the first line of each test case, the totalnumber of graph’s vertices, V, and the total number of edges, E, are given. Inthe next line, E edges are arranged; edges are denoted as comprising twovertices. For example, the edge connecting from vertex 5 to vertex 28 is denotedas “5 28”. The vertex numbers are integers from 1 to V and two neighboringnumbers in the input are separated by a blank space.  

[Output]

Print answers for each of the 10 test cases line-by-linethroughout 10 lines. Start each line with ‘#x’, leave a blank space, and recordthe order of tasks. For the order of tasks, arrange V integers with a blankspace in-between.

[Input/output example]

Input

Output(consisting of 10 lines in total)

考察点

有向无环图的拓扑排序

Python实现

import sys
from time import time
 
def topSort():
    case_n = int(sys.stdin.readline().strip())
    for c_i in range(case_n):
        # 保存结果
        res = []
        v, e = map(int, sys.stdin.readline().strip().split())
        # 存放每个节点对应的出度节点
        graph = {}
 
        # 存放每个节点的入度数
        in_dgree_arr = {str(i+1): 0 for i in range(v)}
        sp_edg = sys.stdin.readline().strip().split()
 
        for i in range(0, len(sp_edg), 2):
            if sp_edg[i] not in graph:
                graph[sp_edg[i]] = [sp_edg[i+1]]
            else:
                graph[sp_edg[i]].append(sp_edg[i+1])
            in_dgree_arr[sp_edg[i+1]] += 1
        
        # 使用栈来保存本次入度为0的节点
        stack = [d for d in in_dgree_arr if in_dgree_arr[d]==0]
        
        # 将栈中入度为0的节点依次出栈，并将以它为入度节点的入度数减1，直到为0
        while stack:
            ind = stack.pop()
            res.append(ind)
            if ind in graph:
                 for x in graph[ind]:
                     in_dgree_arr[x] -= 1
                     if in_dgree_arr[x] == 0:
                         stack.append(x)
        print("#{} {}".format(c_i, " ".join(res)))
 
start = time()
topSort()
end = time()
print("cost: {}".format(end-start))

执行结果

测试用例：

10
3 2
2 1 1 3
4 3
1 4 2 3 4 2
5 4
2 4 3 5 2 3 1 2
20 19
9 2 10 16 10 13 16 7 11 20 20 4 13 3 11 1 10 19 2 6 18 11 10 14 13 15 5 8 13 9 9 18 16 12 20 17 9 5
100 99
21 91 27 77 30 38 48 76 13 23 21 28 87 95 60 10 89 99 67 34 60 85 37 61 16 24 97 7 60 40 19 59 70 63 38 100 37 86 46 27 50 2 49 25 91 6 60 42 20 31 19 68 30 20 30 58 97 15 67 19 49 48 74 46 67 53 59 75 11 57 21 67 60 90 59 51 89 49 15 66 30 88 88 93 49 5 21 50 38 9 37 71 62 41 59 29 11 18 44 98 66 32 19 13 62 12 91 72 46 97 78 89 68 36 45 87 62 92 73 62 85 64 3 69 67 74 74 30 60 54 93 22 45 1 14 47 7 73 7 94 72 81 67 70 49 33 71 35 73 8 21 55 66 43 39 52 36 79 5 44 46 82 49 17 21 78 96 84 78 56 51 4 3 83 7 60 53 14 10 65 53 16 15 80 37 45 3 96 32 39 40 26 3 11 97 37 66 3
181 322
152 68 142 39 20 156 46 76 145 99 163 2 52 81 65 74 65 15 23 61 167 88 65 124 23 132 40 98 2 88 104 165 63 70 46 103 129 59 166 68 39 180 155 15 54 132 161 158 173 86 129 78 60 71 100 7 36 34 174 117 1 3 163 39 13 63 145 95 60 80 64 132 109 170 87 166 131 59 139 5 100 102 56 165 5 15 104 34 134 153 113 124 44 180 7 48 92 37 8 102 24 41 110 69 138 167 18 2 43 94 128 41 116 171 14 98 25 12 25 29 134 149 20 3 104 109 136 149 146 102 175 116 35 45 27 3 25 150 65 35 96 76 22 34 60 32 108 80 138 181 162 157 2 149 169 87 63 49 179 9 100 93 138 70 44 57 115 133 128 79 45 151 56 69 19 146 167 22 97 37 144 181 31 150 96 50 116 35 130 59 179 66 83 69 107 154 57 39 38 111 165 106 30 168 142 102 46 163 152 85 54 144 54 96 43 98 64 2 58 5 128 133 132 106 51 127 19 150 105 85 65 49 169 1 179 76 26 125 130 102 93 181 162 93 69 180 70 159 16 82 181 149 27 120 108 121 116 103 110 6 174 66 78 110 30 68 73 148 36 166 109 122 19 16 165 155 54 101 162 10 3 90 21 96 32 25 113 168 89 178 126 171 2 37 46 82 143 126 61 25 34 103 72 37 13 16 51 50 150 112 84 112 33 18 67 11 132 111 30 123 62 4 42 11 80 159 116 102 59 158 40 79 77 159 38 155 9 35 92 29 40 151 17 173 51 124 10 159 138 116 48 66 1 10 21 143 24 139 22 4 167 9 15 173 97 45 5 71 139 111 153 90 136 154 155 133 56 78 176 25 56 106 38 40 31 16 153 66 153 114 42 7 63 45 89 117 96 98 41 33 179 174 151 90 21 135 107 180 58 23 124 122 55 149 42 93 87 30 5 17 147 88 58 100 176 124 93 120 113 122 15 111 24 51 56 83 35 112 43 168 60 173 56 75 46 112 25 52 109 158 177 173 109 127 43 147 31 3 63 39 21 28 136 174 22 3 142 130 8 85 31 42 9 91 115 151 10 102 155 57 118 159 78 3 126 178 18 135 41 66 78 166 124 4 179 118 32 53 56 122 169 47 153 158 145 130 179 11 129 134 93 45 179 80 84 49 179 27 114 115 54 153 21 171 23 48 64 152 54 11 123 6 134 130 60 89 135 68 60 36 146 4 45 105 23 54 133 132 179 110 67 101 113 13 13 1 136 44 141 165 101 117 23 153 175 157 146 91 120 106 107 135 129 150 171 6 87 88 161 149 138 65 58 73 43 11 73 12 136 88 97 122 36 41 58 107 163 12 27 39 91 68 31 173 58 118 107 1 100 98 129 61 135 173 135 67 149 168 23 125 29 156 26 89 152 151 78 161 8 101 147 12 118 94 128 70 97 93 130 68 105 164 134 81
398 570
234 291 335 41 112 10 329 56 103 309 102 65 96 326 289 79 214 89 104 27 112 281 106 363 218 145 227 367 1 226 179 83 158 173 315 288 192 330 48 315 145 35 353 66 363 278 7 53 173 387 219 66 19 339 366 91 313 146 100 275 347 321 140 20 315 269 392 394 91 67 124 28 76 101 34 208 173 189 163 240 151 63 30 198 384 378 13 333 151 116 93 327 8 303 329 350 251 94 351 20 167 240 88 263 185 367 99 194 102 51 167 295 88 373 299 266 316 12 192 372 236 52 377 91 285 283 343 191 314 241 197 16 338 288 369 30 235 280 280 117 304 373 75 271 195 329 209 182 256 124 232 279 47 93 153 372 262 108 347 305 149 159 70 46 215 321 361 22 355 288 310 141 86 226 123 114 151 158 398 244 130 214 40 244 285 159 145 62 198 371 219 4 182 286 254 295 391 257 137 198 130 223 188 26 365 237 270 343 89 137 48 192 240 45 206 231 11 219 238 44 369 79 61 129 246 345 59 263 245 257 162 283 390 82 367 55 126 148 376 51 306 257 7 141 357 26 325 19 275 7 204 182 54 61 330 382 276 34 8 280 307 359 101 396 103 278 361 79 120 269 316 308 91 3 49 16 153 314 121 45 252 12 246 226 311 260 387 268 266 388 207 391 398 134 276 319 245 164 169 111 397 290 335 129 322 90 169 101 192 332 326 188 87 354 379 295 151 316 204 60 175 178 96 391 199 390 41 269 215 142 139 36 218 86 331 114 78 342 306 300 91 391 67 46 106 73 88 87 297 23 341 259 233 190 81 315 356 389 327 190 198 64 202 142 175 351 225 358 247 155 16 330 85 18 40 236 344 167 360 385 378 105 328 278 398 396 203 364 68 315 341 36 324 184 241 278 22 6 61 270 85 81 362 16 87 266 287 26 69 346 334 231 365 316 15 392 360 330 175 282 340 64 318 368 14 141 240 209 210 340 232 385 42 260 303 394 240 90 381 224 276 372 37 298 377 63 41 343 107 165 335 251 24 161 103 182 342 108 105 340 262 298 160 122 395 224 309 26 161 242 181 133 329 43 270 218 306 56 155 111 394 56 387 388 16 380 16 117 238 294 271 165 122 330 216 380 113 119 303 30 162 22 287 242 318 33 234 250 239 246 229 154 378 194 329 349 168 237 254 177 115 26 265 226 239 301 81 388 261 206 9 4 254 311 225 386 387 231 320 286 264 3 227 176 118 309 38 220 104 94 9 32 163 261 11 311 86 20 256 9 67 385 48 165 120 343 246 28 261 148 193 191 341 323 381 233 340 382 125 5 274 315 227 6 57 189 183 245 284 386 269 296 171 254 298 373 388 233 139 96 352 66 168 89 339 18 335 384 387 37 331 110 102 334 195 87 285 188 375 5 160 394 383 183 249 145 218 246 298 244 249 12 21 63 2 202 354 288 252 330 136 146 16 287 212 336 171 242 267 154 232 73 38 373 13 336 38 155 31 280 393 269 188 119 377 183 131 246 40 222 381 309 321 318 7 200 386 79 301 327 217 66 208 385 38 246 102 152 120 172 153 166 99 378 112 338 151 322 216 228 215 150 69 165 125 36 74 138 346 12 326 281 243 244 239 202 341 357 266 221 262 59 186 285 11 394 267 38 212 257 118 4 42 316 140 279 201 308 139 89 376 291 218 266 125 248 17 356 249 30 144 378 232 266 25 121 298 294 254 316 286 5 232 81 384 181 330 244 151 347 208 324 52 93 311 57 215 161 390 30 23 388 144 175 321 288 271 244 21 157 224 316 275 324 183 191 144 363 251 390 222 283 151 387 218 63 179 204 173 373 205 398 298 382 125 385 130 148 123 141 384 87 120 212 162 150 369 127 223 193 317 195 337 380 108 43 398 370 31 314 398 301 353 263 11 256 45 26 101 205 270 279 351 342 195 8 61 298 131 257 307 98 244 45 256 350 185 287 46 165 303 166 141 65 307 145 148 250 172 257 2 257 151 60 216 246 305 110 111 248 236 242 304 30 34 389 275 360 359 268 111 176 223 22 57 187 229 19 223 132 221 117 353 45 198 286 254 105 360 334 124 59 150 391 377 110 169 110 259 388 58 323 347 240 127 109 99 207 316 39 276 353 365 343 386 58 292 299 149 81 263 73 302 37 225 340 9 66 282 45 139 134 293 348 197 198 370 242 199 367 208 114 325 196 113 207 398 77 96 216 398 269 31 64 261 232 149 167 127 172 348 190 247 37 350 308 139 314 89 172 168 188 23 391 230 2 91 313 14 178 116 316 40 266 47 356 98 211 256 52 92 359 212 211 68 152 116 124 361 278 112 121 341 6 157 66 106 2 123 93 169 228 197 148 146 159 156 66 89 128 276 377 381 171 179 46 130 96 70 66 25 142 95 349 140 250 367 65 195 302 219 67 127 187 290 43 8 316 230 338 116 378 205 140 390 231 168 7 41 213 293 167 360 217 94 368 234 165 59 57 303 268 237 364 83 212 16 115 151 341 40 216 36 12 242 142 355 385 88 204 369 94 175 222 174 94 235 253 11 51 234 278 15 308 199 59 135 301 54 342
529 821
176 284 299 151 331 334 77 175 427 362 141 506 25 284 527 235 441 286 447 372 146 18 364 22 288 235 198 381 470 472 462 481 335 307 470 312 512 340 324 136 425 288 46 365 318 78 297 364 311 234 58 216 490 458 41 61 335 271 56 391 221 246 392 87 146 427 36 377 432 188 39 359 278 525 107 119 107 203 326 368 388 345 166 65 221 432 408 362 70 384 12 320 190 35 503 93 47 262 318 372 64 38 46 65 68 23 492 527 469 200 44 357 183 263 36 362 325 151 4 418 364 224 248 295 419 394 482 250 202 370 349 100 17 192 519 53 445 210 517 122 276 444 383 8 124 485 459 24 71 379 244 279 307 74 268 417 210 291 178 5 227 24 407 224 470 189 405 520 218 258 307 361 418 117 300 433 225 371 378 199 63 203 261 219 214 21 420 296 207 262 253 179 135 366 257 219 46 461 237 267 116 251 59 163 515 159 68 216 491 383 529 526 463 290 333 426 96 108 414 338 267 62 314 155 54 232 428 195 225 190 528 184 1 302 207 287 523 384 222 440 284 149 356 479 380 235 185 69 470 350 144 133 215 275 129 425 529 481 7 471 169 104 172 410 164 235 198 45 88 125 182 249 287 128 507 102 348 523 340 259 159 158 516 136 46 348 338 315 86 330 170 61 369 394 369 508 297 505 326 502 35 376 383 448 325 366 341 445 88 53 410 525 182 160 510 521 96 227 455 355 397 491 380 150 214 107 67 249 27 437 145 161 412 209 446 303 369 108 504 143 215 84 398 407 403 521 411 113 376 41 256 258 239 438 190 445 202 151 201 512 213 31 40 230 370 486 354 524 240 460 501 217 109 353 27 154 312 78 211 15 344 75 110 411 214 456 457 220 42 394 422 300 233 219 511 121 363 165 469 495 182 172 145 410 513 103 243 491 422 226 323 404 403 232 428 14 321 87 36 127 150 525 349 441 212 211 201 499 136 426 312 235 193 183 162 75 205 485 281 216 505 306 214 44 255 248 370 223 166 421 512 268 456 197 86 514 150 68 512 524 16 263 159 128 147 97 91 490 48 262 118 51 267 133 192 485 198 87 319 185 252 112 341 461 284 269 454 200 449 239 330 74 138 446 223 306 326 241 54 502 289 30 187 302 354 172 157 263 168 508 174 314 21 68 328 203 437 479 195 252 459 51 439 445 64 39 52 138 332 449 469 177 58 198 236 310 469 212 266 303 508 211 161 83 520 9 157 239 285 31 86 286 331 24 143 230 508 316 425 434 126 256 297 488 28 261 48 209 331 170 311 211 83 3 390 218 242 174 101 224 468 413 37 149 147 199 190 307 52 288 156 367 164 32 450 57 27 147 504 132 388 379 516 330 511 258 192 133 529 345 509 362 139 250 35 235 276 274 424 392 237 303 516 520 49 115 432 499 68 199 227 147 428 426 526 464 295 22 27 251 317 507 166 249 96 104 328 105 437 244 245 494 333 495 79 508 519 471 405 529 4 313 248 440 454 399 294 222 91 244 27 118 134 254 100 66 409 299 182 194 236 210 31 275 452 62 289 482 262 433 518 475 470 345 156 465 127 247 504 346 152 240 115 208 423 497 496 75 390 274 96 208 285 146 487 250 274 31 482 461 523 477 126 426 180 69 425 110 285 339 352 356 323 411 462 496 180 35 73 167 143 435 64 26 95 480 492 467 425 94 335 449 1 162 352 366 517 447 57 285 374 310 206 24 7 250 317 198 187 340 268 381 452 400 293 183 305 36 182 525 292 115 462 380 516 24 360 339 284 418 261 427 440 458 48 12 123 351 429 473 180 67 77 81 129 302 524 259 507 441 275 368 122 452 524 51 124 322 494 497 390 136 437 495 478 524 408 399 259 285 425 218 378 246 240 325 329 97 116 477 169 383 50 258 103 479 284 377 303 231 463 513 53 13 225 236 515 322 168 73 13 135 78 113 11 495 401 263 398 264 520 78 236 485 158 288 319 27 223 254 349 390 467 164 162 60 2 36 65 278 504 366 204 10 67 78 409 94 205 142 278 280 81 500 118 56 323 121 176 279 139 393 293 148 311 189 370 38 255 355 300 136 270 395 263 195 325 456 242 181 518 151 305 275 319 245 333 411 439 194 213 142 3 62 88 500 280 361 491 61 324 126 16 209 190 385 85 196 520 346 494 192 14 127 226 38 360 287 378 159 418 427 348 357 218 169 108 114 54 498 242 475 222 254 53 167 227 233 12 161 50 359 375 312 336 374 377 61 220 10 305 101 19 408 13 94 382 147 380 121 211 456 226 460 213 341 396 42 341 249 176 236 267 329 118 346 485 287 267 268 317 239 233 3 470 151 399 304 135 363 166 236 439 413 88 503 48 91 53 505 365 3 217 489 529 351 238 237 446 141 472 285 172 395 519 10 408 155 327 406 428 484 430 83 372 322 513 379 487 177 429 290 92 350 187 83 283 403 412 134 423 367 2 13 13 509 52 173 55 338 437 241 459 269 437 186 353 307 287 473 283 387 140 241 411 514 420 525 142 216 377 282 459 14 412 8 482 323 49 36 293 427 85 491 76 406 423 474 496 326 471 253 109 271 375 310 248 361 222 497 269 112 123 442 159 239 376 137 336 395 206 12 277 326 295 45 438 235 186 499 313 170 38 235 469 82 507 117 90 15 386 492 317 33 418 254 527 115 15 381 240 411 525 61 295 274 145 377 190 196 412 179 64 130 503 475 172 400 284 159 25 190 156 143 298 235 462 370 131 526 220 375 70 57 498 244 450 524 340 451 54 112 412 502 275 502 28 141 446 140 129 494 266 104 307 60 520 162 230 189 447 360 160 393 297 218 285 345 487 246 236 481 517 120 513 361 397 189 434 373 67 92 483 302 386 135 238 399 227 61 225 28 294 252 251 68 363 254 289 170 73 507 35 524 348 322 11 122 27 127 519 296 34 330 314 118 403 85 430 332 491 155 228 475 159 471 493 36 150 61 268 155 420 181 478 514 398 256 450 264 199 173 490 276 349 295 279 514 47 186 505 142 407 274 109 7 491 417 63 135 397 90 206 239 469 31 4 397 259 339 297 212 328 307 58 470 176 106 429 65 148 24 444 140 157 306 388 64 457 143 276 408 303 288 227 328 162 179 157 436 63 102 385 509 353 272 470 452 27 445 115 211 143 526 447 133 129 328 212 387 220 76 513 83 141 466 123 306 423 348 250 234 58 269 86 477 164 38 215 496 79 82 25 76 283 178 97 128 53 475 470 377 518 194 77 394 452 513 362 97 475 433 180 349 343 18 8 170 442 434 314 115 59 372 493 347 11 416 373 146 63 499 523 331 439 239 284 528 400 481 343 82 299 475 510 42 11 456 57 459 156 313 218 493 156 287 1 265 405 208 200 310 496 480 518 22 419 164 214 390 412 71 518 73 469 412 64 477 100 195 441 30 7 379 268 200 25 324 157 433 429 320 147 22 233 427 284 43 209 177 448 51 76 505 379 75 465 31 300 489 313 149 252 51 255 422 41 102 328 493 430 460 121 128 90 203 212 232 364 135 454 66 463 151 82 396 270 82 197 486 305 218 262 427 2 157 262 247 177 131 7 486 302 158 503 111 436 229 223 389 232 22 185 98 233 30 94 486 470 163 92 444 422 101 215 375 223 226 210 99 314 276 67 351 434 277 100 506 449 277 436 232 325 127 308 200 343 57 451 514 167 529
849 1774
223 657 804 185 592 529 224 318 244 3 699 113 251 355 445 77 12 808 144 782 303 5 482 404 819 185 256 544 791 46 577 634 220 286 138 422 159 292 187 426 205 380 595 363 133 636 75 154 232 315 841 66 568 64 571 137 233 426 745 84 23 454 216 417 157 1 701 653 756 288 841 685 818 670 193 430 823 645 417 583 112 670 220 497 714 126 450 633 189 340 34 706 407 110 584 326 452 301 436 391 822 371 530 62 569 819 540 320 128 565 304 211 841 631 534 443 748 800 801 307 25 105 377 620 780 48 10 764 10 307 178 255 376 434 291 383 17 69 734 40 208 767 85 656 63 382 420 706 502 424 367 478 108 254 534 822 9 504 563 453 677 565 39 354 655 80 804 740 190 479 117 335 195 703 494 102 277 586 337 458 178 556 12 292 809 527 220 64 38 833 672 660 85 811 467 808 114 500 419 561 481 843 137 62 333 748 462 273 695 541 651 760 807 596 218 806 98 320 577 352 816 446 365 360 495 71 375 289 466 763 251 491 765 94 572 111 819 501 238 729 493 81 288 425 46 336 606 674 220 621 232 471 411 122 155 9 610 754 447 258 176 473 595 521 197 420 594 772 778 504 534 490 270 437 824 724 124 563 801 431 345 14 299 691 441 594 628 437 262 136 612 603 357 466 605 767 284 598 385 579 412 248 292 400 297 538 444 24 347 515 138 136 708 811 35 623 318 428 458 583 791 840 500 320 452 827 377 609 776 1 645 799 737 46 536 462 555 388 279 724 719 705 169 71 650 321 796 740 371 362 363 490 213 419 799 343 316 526 672 608 115 498 68 423 253 425 201 208 67 209 663 561 212 400 510 231 448 294 121 96 447 379 135 258 405 508 481 296 154 821 679 574 175 453 57 822 366 727 770 240 701 629 402 158 220 506 818 316 10 315 169 562 92 844 403 31 780 664 97 489 450 469 403 130 668 321 433 589 267 561 726 688 829 473 165 787 340 783 272 660 549 400 611 192 213 684 506 250 331 184 822 701 149 282 691 79 662 386 647 516 125 469 663 255 250 253 51 16 25 628 209 378 73 739 709 603 368 183 94 200 85 543 192 680 434 772 504 527 331 206 700 43 325 506 549 177 571 540 477 13 285 687 124 263 710 406 264 620 129 429 333 613 439 654 38 77 438 577 563 29 208 654 311 692 281 104 39 94 280 701 402 242 183 116 31 176 737 774 175 198 687 21 550 580 570 779 118 549 305 347 795 515 412 622 694 614 777 610 666 260 604 746 338 399 775 428 548 425 165 318 280 670 194 143 413 463 547 214 112 586 570 414 251 501 262 741 449 723 133 14 257 499 822 828 247 651 793 3 30 685 412 118 791 567 195 698 8 259 836 213 368 828 817 535 103 262 784 709 834 162 358 539 332 591 97 713 665 315 821 603 130 54 127 747 125 214 379 351 114 322 105 740 513 111 794 514 719 417 256 171 387 634 119 378 839 613 132 123 745 249 157 171 462 286 422 52 583 446 485 356 308 185 805 804 373 110 377 58 590 77 224 291 34 529 83 130 144 163 68 827 490 811 55 23 594 171 166 172 561 705 534 383 578 2 273 748 836 73 555 143 67 789 320 160 660 766 403 270 838 585 375 394 576 69 726 364 723 14 252 483 606 347 774 652 512 316 668 741 721 84 770 382 139 95 198 102 66 344 443 686 192 754 756 308 30 591 516 171 443 842 94 141 491 834 525 33 312 723 838 465 86 369 469 697 588 578 558 531 601 259 834 676 103 839 144 654 775 799 426 739 419 6 715 747 67 296 671 466 148 194 587 324 587 55 103 218 92 102 144 302 468 203 475 64 761 477 484 53 9 487 644 334 764 33 536 653 835 273 173 1 659 88 310 541 86 294 141 828 357 300 16 682 159 272 52 196 670 3 641 819 465 347 834 754 247 670 733 65 152 552 30 301 141 107 232 480 777 245 241 376 730 34 550 652 169 725 828 79 507 816 74 355 375 651 531 328 10 318 57 356 227 613 694 73 478 787 324 720 73 146 19 146 246 282 422 800 726 716 188 203 216 210 239 585 809 629 774 657 431 680 686 269 572 406 831 86 259 717 194 499 616 501 312 363 47 442 767 378 206 579 195 538 157 755 459 561 832 633 712 546 175 747 397 683 537 681 815 371 704 321 395 198 646 49 192 608 234 119 537 87 224 737 490 194 249 522 744 268 95 229 190 849 417 833 574 601 528 825 435 389 534 40 326 41 684 423 778 562 796 198 388 148 187 9 457 68 85 367 762 847 457 358 712 42 128 675 19 301 439 71 677 181 604 398 98 601 242 309 57 350 283 602 285 634 595 518 619 300 170 813 125 748 801 800 15 729 841 453 718 253 638 358 638 96 827 37 57 234 126 684 808 340 388 616 65 210 347 547 271 382 478 14 265 499 247 107 688 781 554 361 656 253 242 731 308 691 34 811 607 276 79 177 145 266 113 422 505 253 811 248 172 200 584 364 665 463 224 494 148 479 166 601 178 51 525 5 721 118 159 84 411 755 507 811 333 589 397 236 57 389 608 460 815 557 457 333 26 136 16 358 243 519 348 301 103 86 169 537 156 314 327 404 679 638 317 340 142 247 734 509 364 53 16 579 386 522 441 648 732 343 445 608 16 417 169 501 178 605 465 733 290 300 462 783 148 446 103 817 253 640 433 302 301 259 677 782 538 29 279 74 46 157 711 684 228 180 118 622 726 102 666 715 844 539 575 458 125 23 220 455 144 237 114 564 236 226 274 725 229 633 812 757 99 264 250 622 442 483 156 720 166 239 30 664 18 549 228 778 120 586 844 636 243 613 125 471 811 53 230 537 271 609 339 440 652 706 616 255 450 130 578 762 56 87 465 789 819 748 220 818 173 760 379 705 99 374 68 27 646 664 272 120 20 537 349 727 808 83 355 269 241 499 260 573 218 154 722 239 362 594 178 66 251 315 564 616 548 598 299 519 494 137 738 848 366 459 280 50 764 842 486 276 178 74 382 69 183 95 114 7 575 479 692 623 264 185 404 210 465 102 531 79 296 549 759 635 810 364 271 592 548 588 138 202 511 489 523 746 75 392 304 253 24 414 694 776 25 404 277 781 663 409 319 204 790 356 698 525 440 515 798 190 119 61 128 471 265 502 162 843 474 706 398 594 775 23 449 101 612 200 110 843 117 271 243 54 293 653 554 137 51 687 149 613 113 26 646 493 135 24 99 642 7 231 168 508 105 411 693 832 241 789 761 695 615 172 548 271 801 552 366 476 205 591 114 766 830 420 481 351 666 524 504 816 149 231 356 26 632 732 206 366 822 49 831 593 812 456 541 640 805 244 838 733 241 242 258 637 691 783 780 496 443 294 469 578 345 246 600 307 605 682 651 6 638 756 457 86 38 33 70 599 416 222 377 565 236 266 645 742 555 480 530 505 279 452 677 631 205 59 49 357 451 54 117 437 750 442 814 3 689 286 668 453 607 69 721 750 220 193 827 350 312 811 105 473 30 502 587 717 272 411 73 154 467 7 437 499 644 528 487 335 32 715 218 583 361 84 309 748 154 593 29 603 677 577 566 616 30 802 737 11 254 812 626 115 211 160 250 466 663 185 768 633 520 313 777 231 399 507 362 453 722 776 550 311 740 214 271 73 500 350 475 396 179 87 526 136 106 73 390 44 548 408 737 151 824 136 280 790 553 499 213 313 173 541 745 628 758 640 733 408 22 334 307 240 270 720 796 507 7 29 744 218 64 83 796 288 506 779 646 626 23 200 605 583 732 446 288 617 620 553 798 743 793 462 768 819 814 583 402 93 827 286 299 798 747 42 706 150 719 11 592 567 178 799 498 580 612 1 600 511 667 444 409 343 666 227 135 525 63 705 205 71 125 832 438 247 306 687 745 728 51 478 555 817 359 661 832 649 433 804 287 479 208 68 337 270 161 729 801 79 34 313 457 609 384 541 802 143 330 717 703 124 222 717 668 157 242 199 279 517 334 301 568 420 560 378 139 318 47 729 844 249 656 456 285 793 380 231 775 624 366 276 719 57 35 499 347 509 720 313 251 515 530 655 524 522 834 321 340 772 117 643 177 684 619 586 592 691 238 789 493 695 533 489 153 659 525 582 733 631 507 601 59 466 155 269 818 547 719 762 10 670 265 132 345 229 326 309 797 602 375 642 804 426 722 304 226 86 614 728 823 562 58 542 829 1 254 17 156 333 97 835 819 69 91 661 621 509 481 643 288 549 709 455 144 525 232 248 753 352 679 306 294 421 356 320 196 55 511 702 354 44 45 1 93 717 736 613 142 443 43 248 645 296 447 803 57 206 307 655 25 203 272 717 101 460 470 770 846 96 376 447 157 313 246 517 63 133 243 831 377 603 485 784 578 617 78 4 5 637 805 444 316 830 523 186 178 583 167 388 371 400 645 36 737 741 791 656 134 80 462 466 132 324 525 171 782 80 65 104 791 149 265 283 164 823 118 784 737 259 145 648 447 522 493 522 641 532 59 84 559 641 47 218 531 69 123 53 646 797 746 531 540 216 44 287 807 301 39 519 139 819 28 727 600 471 246 401 144 179 385 797 675 448 795 336 242 735 166 626 618 625 112 320 213 820 362 540 816 522 89 466 190 764 230 557 192 421 693 269 784 179 550 114 436 246 511 779 736 343 618 670 801 637 770 53 597 219 459 848 415 104 500 346 195 364 108 131 345 400 133 571 512 760 97 724 745 272 611 147 343 5 25 735 10 171 148 576 161 585 592 781 844 444 67 89 432 109 213 598 185 537 19 594 634 426 392 231 309 613 595 755 307 126 324 212 841 842 305 684 714 325 494 797 775 375 10 285 740 454 512 122 238 501 711 813 239 625 596 848 77 643 123 9 414 329 844 640 689 615 468 753 189 713 172 231 780 54 457 394 402 62 769 849 762 143 94 356 449 370 296 424 607 654 753 740 685 814 704 444 168 341 189 269 536 335 359 193 449 546 197 766 302 430 220 440 763 48 759 706 833 464 331 762 182 602 15 386 276 3 577 529 361 612 699 552 277 502 411 268 164 38 86 259 703 634 228 341 106 806 267 194 401 211 746 361 646 505 165 612 270 307 357 590 373 88 831 614 213 401 330 343 327 14 213 743 719 714 651 80 15 214 495 322 787 36 830 691 251 203 534 422 809 578 817 457 66 133 299 757 267 533 148 471 188 211 488 44 98 717 152 52 28 555 142 248 480 355 566 575 601 471 548 556 641 519 582 716 386 684 510 300 142 458 566 325 279 565 103 595 768 36 711 349 199 318 813 121 422 275 462 680 719 330 159 790 385 336 820 630 647 583 74 5 778 84 30 45 128 52 790 647 230 839 820 603 330 314 620 505 704 400 433 655 92 804 442 419 164 163 224 777 488 832 777 167 558 739 468 389 112 705 285 70 619 216 401 160 30 377 207 741 52 469 567 675 746 59 575 661 205 233 145 376 182 328 363 231 642 447 662 713 88 174 472 703 192 408 536 226 568 418 838 799 610 809 609 87 606 650 716 302 59 509 710 245 518 556 247 392 485 503 641 261 729 579 769 649 589 518 672 767 393 420 27 799 264 269 776 635 756 388 312 429 283 678 830 346 315 2 677 392 75 692 552 408 138 175 10 577 384 637 279 461 67 509 615 788 639 497 645 642 310 109 218 681 462 216 550 750 192 561 456 454 125 813 124 659 214 661 445 49 599 14 21 87 467 114 82 455 349 551 653 509 168 831 104 340 540 286 618 783 49 263 513 289 370 640 599 35 304 345 210 586 278 660 447 294 724 635 235 199 368 640 57 562 290 401 488 236 241 692 458 463 92 409 32 548 449 846 263 681 474 661 699 361 810 17 696 121 645 268 484 424 472 392 224 255 459 526 46 235 467 375 61 77 397 104 780 76 371 60 508 211 56 473 182 506 264 601 33 579 385 676 468 763 70 515 687 780 276 463 722 756 312 464 563 42 577 190 663 287 550 221 467 409 793 542 348 373 304 445 83 717 205 724 101 829 571 784 807 579 721 657 486 750 658 797 16 296 811 394 822 524 641 200 456 300 56 252 324 256 474 760 532 648 429 750 251 216 173 828 754 259 594 848 558 283 495 411 65 579 198 426 513 259 208 295 297 670 427 542 99 189 428 378 189 425 215 485 845 323 828 240 714 423 201 197 672 172 256 828 241 343 336 3 229 446 260 784 411 687 640 36 415 545 390 328 178 751 328 60 226 341 801 21 78 806 267 275 206 177 550 401 164 57 835 521 715 248 450 746 606 589 737 515 488 634 796 426 845 476 94 529 485 700 296 20 754 209 238 715 74 630 234 788 760 682 97 187 827 356 27 311 689 425 207 602 308 118 304 80 210 421 671 297 135 686 749 180 195 122 114 806 72 804 103 464 214 23 48 609 754 266 345 221 12 545 808 664 121 543 674 371 626 545 742 541 726 423 331 731 567 515 604 568 32 225 395 750 559 327 143 282 283 616 280 70 578 219 558 455 547 543 557 62 517 635 197 128 770 93 301 748 153 664 189 76 674 829 37 258 823 793 154 461 175 471 307 692 331 274 587 357 667 640 716 676 301 713 373 250 178 803 386 418 65 798 360 39 721 758 365 817 592 478 494 147 487 126 293 106 16 439 500 709 92 805 438 744 228 574 641 131 679 449 325 379 820 655 777 432 826 318 39 121 649 102 38 652 438 323 738 564 528 792 429 701 823 442 557 158 810 712 70 623 50 837 181 394 271 3 574 128 272 420 555 266 335 71 547 625 468 708 671 318 443 590 348 221 757 204 569 530 632 557 355 259 285 205 317 643 40 269 695 501 504 524 822 165 640 282 528 248 387 497 230 203 777 819 94 210 528 601 75 46 337 581 232 733 649 538 801 288 70 440 365 371 67 274 559 698 21 516 254 342 588 643 359 185 807 116 847 617 504 83 658 52 101 571 817 837 362 424 327 34 745 291 8 4 142 767 303 576 445 258 740 11 566 521 336 448 618 328 463 93 98 309 181 219 63 449 605 701 685 256 317 613 265 821 379 630 639 419 383 54 494 603 569 372 469 539 220 614 495 147 265 420 25 182 745 845 28 120 791 634 631 747 795 675 142 165 398 848 311 783 252 512 290 811 268 336 669 301 30 270 824 95 50 266 217 238 281 689 142 164 536 275 51 701 327 727 357 269 252 199 708 155 418 460 243 426 695 122 310 67 334 840 75 456 835 676 412 375 503 428 215 701 243 64 281 506 334 540 777 678 718 384 185 448 75 645 549 579 493 417 123 702 793 629 201 132 57 267 19 420 680 3 189 605 457 289 548 637 790 209 75 545 607 37 201 733 824 608 347 251 693 187 233 175 155 814 445 163 133 556 101 843 691 839 817 253 814 261 167 498 810 820 610 33 525 244 208 225 464 702 31 456 97 715 572 709 96 454 438 208 803 497 93 248 199 322 384 209 848 630 443 733 763 842 65 766 188 582 86 571 68 359 793 628 816 341 242 546 791 261 153 65 215 790 631 463 597 385 449 808 655 453 207 800 515 479 380 21 548 330 125 525 512 275 274 480 638 572 374 848 125 670 756 136 731 715 412 809 22 41 492 772 436 275 169 90 275 640 693 735 371 758 399 100 432 419 475 624 316 599 805 790 607 572 233 340 197 522 614 111 751 462 397 204 205 585 662 389 285 95 327 133 215 460 271 198 135 721 525 517 119 287 148 381 340 814 831 35 247 196 223 549 695 26 3 204 756 785 520 23 257 501 703 295 187 79 626 3 159 612 429 379 715 172 708 4 632 605 337 551 103 698 348 509 826 795 576 23 608 179 470 158 530 136 666 447 363 742 218 423 497 400 325 516 415 823 221 200 530 595 312 404 173 783 699 598 646 642 227 77 689 221 646 120 354 624 777 434 777 575 700 799 246 623 405 204 838 715 215 405 148 94 110 298 377 796 458 598 605 381 768 612 82 453 183 526 513 623 57 739 805 266 844 490 307 742 458 158 845 489
1000 2874
253 471 966 994 287 138 618 494 712 580 733 937 60 332 722 679 99 956 6 258 326 506 9 229 608 748 654 319 963 727 163 968 556 16 871 303 12 748 644 839 840 436 187 59 275 810 598 274 554 420 764 19 241 259 794 157 33 682 996 880 182 819 184 183 60 537 761 298 408 391 205 359 94 287 782 345 588 708 596 853 594 811 833 184 953 679 3 858 213 820 967 157 411 478 87 277 99 547 252 992 483 911 91 905 8 885 586 673 849 741 558 273 651 663 851 998 924 891 71 675 972 456 428 76 770 137 144 96 124 180 903 387 996 382 772 423 423 788 974 617 11 790 165 530 86 694 683 848 375 636 493 325 390 735 950 266 843 602 854 364 800 672 130 555 756 5 248 78 679 766 407 981 836 251 892 758 320 500 802 427 383 649 623 474 971 73 456 257 661 841 361 551 284 470 377 130 271 50 286 520 281 612 773 451 23 619 75 20 82 113 537 18 115 973 83 67 99 962 366 650 901 549 955 811 120 500 43 102 452 269 393 947 660 575 89 190 230 580 275 735 485 731 918 312 450 790 903 533 9 985 42 150 423 524 457 862 850 286 18 828 582 885 615 26 576 465 586 261 698 47 186 651 860 627 475 188 547 568 89 151 899 885 182 363 961 199 363 67 848 44 84 578 294 113 19 915 468 612 380 251 14 686 812 705 387 872 140 817 230 378 670 968 368 226 313 945 964 98 455 140 491 682 778 565 553 312 221 575 931 217 181 130 644 121 310 936 738 292 972 827 320 211 335 987 750 104 693 636 34 583 537 798 111 539 46 605 122 462 879 798 589 66 921 506 97 500 484 50 850 695 962 346 283 7 595 572 77 868 107 513 263 514 823 254 411 641 335 814 374 299 158 469 728 988 687 123 803 787 506 654 574 676 948 820 27 785 71 800 803 552 215 687 599 905 25 426 582 124 515 876 547 807 126 438 220 503 980 857 1000 25 956 602 775 992 834 745 317 553 918 228 593 972 302 951 8 740 802 262 221 390 306 451 244 649 856 561 279 346 982 945 60 10 830 405 745 154 411 606 289 67 728 726 998 708 484 413 891 443 85 61 890 380 211 373 314 925 713 527 804 485 265 601 248 897 742 606 83 951 922 606 468 656 832 319 236 78 515 164 922 521 379 209 407 766 863 761 498 395 376 203 953 342 783 492 200 533 79 935 288 622 924 180 450 351 314 517 620 827 630 114 871 555 623 394 808 677 42 113 114 61 237 289 823 554 44 148 259 424 848 930 19 451 119 874 782 754 660 629 651 111 531 906 631 823 281 940 46 630 867 471 646 130 506 485 893 617 235 510 813 272 104 384 664 524 23 944 63 811 186 60 522 247 415 536 62 777 686 453 418 511 859 134 70 867 574 653 20 104 903 304 227 438 139 698 450 409 132 755 109 841 447 935 857 109 669 469 796 590 386 16 564 502 381 286 216 148 51 373 476 936 269 868 870 156 327 417 796 360 94 206 550 548 315 504 797 311 461 273 281 654 296 403 348 446 218 351 711 367 225 26 32 691 38 251 801 216 990 204 664 945 903 638 746 731 767 650 1000 653 785 744 787 16 34 50 423 732 196 58 892 147 896 381 259 57 339 202 926 512 146 624 966 134 522 167 880 852 520 741 181 591 912 197 70 747 993 932 27 997 459 685 339 848 906 293 296 444 968 672 170 546 712 463 403 612 791 48 824 458 845 300 698 501 903 560 444 764 980 669 977 327 428 781 275 805 398 409 38 872 586 624 967 823 144 222 352 746 377 816 784 216 6 112 187 322 863 342 318 140 22 121 142 774 3 785 767 632 615 329 614 414 471 846 70 773 32 150 259 914 597 586 301 461 90 331 10 636 23 893 946 841 159 481 670 259 231 986 495 637 522 89 784 26 953 79 377 926 359 642 454 62 633 34 736 820 987 473 522 563 855 643 773 643 949 367 389 215 281 623 240 7 365 270 757 863 416 685 684 701 64 130 403 430 608 272 87 910 999 846 747 877 9 21 339 613 922 858 642 663 233 133 684 985 691 708 770 592 269 800 491 583 139 122 928 964 840 346 565 58 413 589 707 528 41 884 787 908 229 44 464 520 955 123 665 384 292 440 203 470 669 527 267 172 450 980 941 863 464 428 301 652 859 401 960 853 941 100 698 337 438 460 587 700 706 916 286 585 269 257 221 973 782 563 458 763 230 731 249 632 320 97 69 865 57 609 438 178 35 837 239 668 792 294 147 198 61 701 742 286 898 608 553 750 535 156 186 874 996 49 452 787 508 114 494 217 436 769 976 304 38 788 14 464 793 801 207 44 535 30 111 630 870 848 892 181 429 816 103 433 85 257 125 7 121 391 72 961 867 988 902 637 584 469 690 914 386 834 232 345 217 128 498 969 73 953 241 267 256 485 296 269 624 408 457 494 135 285 483 659 941 435 567 323 281 978 245 405 376 465 230 763 714 834 706 169 87 91 666 249 856 840 952 682 558 463 616 570 923 674 282 10 1 513 929 835 953 911 444 916 195 267 364 106 946 486 932 462 4 925 764 336 614 73 407 907 292 761 323 357 916 609 100 287 772 133 646 908 515 263 569 909 770 321 630 590 248 473 762 168 968 444 783 701 949 428 846 208 376 987 102 909 286 948 987 685 301 614 816 991 194 363 192 777 833 328 722 151 137 525 212 404 641 252 739 419 594 499 963 876 487 915 957 453 62 656 379 527 877 994 579 179 263 699 868 627 230 909 315 851 445 153 872 542 944 775 728 290 551 675 667 44 186 939 555 656 796 810 764 745 789 893 623 35 757 924 928 591 159 251 837 467 749 152 249 180 950 508 239 605 213 808 425 566 813 230 155 78 967 926 425 304 241 407 781 925 935 735 55 59 632 545 486 443 598 349 864 889 586 578 117 686 843 58 133 679 983 664 430 303 733 446 303 766 923 536 842 438 603 341 80 246 954 713 51 663 390 385 290 612 457 945 773 202 764 257 16 198 237 336 70 179 227 619 873 883 929 46 932 856 134 222 914 184 850 275 418 90 944 287 957 474 70 133 781 420 414 766 848 274 329 911 398 132 955 305 586 920 994 401 320 846 224 114 572 148 221 646 576 466 312 605 297 138 223 369 389 974 618 378 756 432 108 518 890 987 823 85 102 699 631 153 411 344 92 710 684 65 670 88 174 829 495 20 844 7 171 785 162 979 960 623 965 394 703 707 818 516 976 79 384 120 997 312 340 613 514 460 738 959 167 311 907 677 351 225 77 487 185 509 693 139 843 368 787 587 757 477 509 300 415 236 928 467 871 857 904 37 261 969 623 862 651 819 691 98 651 325 797 688 596 279 32 784 124 632 454 718 205 985 613 43 348 32 813 224 123 95 64 552 411 638 283 982 675 791 413 384 140 172 421 829 963 343 121 432 836 492 694 785 983 947 90 106 437 858 23 630 517 62 404 727 104 589 416 965 294 417 505 953 941 935 965 959 340 2 595 334 844 820 903 764 596 178 718 481 323 422 497 222 166 992 60 377 817 273 498 3 792 142 936 979 633 978 366 255 728 431 326 370 464 145 181 445 32 217 797 73 234 34 880 587 887 272 103 41 744 66 634 999 297 820 715 626 825 281 756 328 564 459 976 700 541 10 864 741 535 566 887 59 542 549 605 853 448 441 294 524 5 874 667 552 574 38 24 151 961 853 66 908 987 643 381 134 473 184 70 870 464 187 641 353 185 979 582 138 480 763 336 295 870 73 8 907 754 256 693 211 897 37 405 852 877 549 540 912 323 198 999 981 57 88 160 545 863 988 323 61 797 852 728 15 554 837 14 145 564 784 369 700 217 61 205 266 131 748 878 599 544 268 962 188 333 473 514 255 997 628 907 829 508 58 276 728 854 542 763 76 621 251 754 823 270 627 830 570 168 622 496 28 118 664 651 255 544 761 99 524 60 569 746 311 734 549 745 523 381 148 692 494 987 174 309 883 218 999 174 788 575 269 519 331 685 828 352 432 895 133 692 467 799 915 350 948 391 689 304 24 781 347 9 14 725 852 210 426 464 61 100 874 213 748 263 371 960 621 192 943 712 367 554 441 595 471 1 147 339 168 102 911 8 766 173 75 472 902 793 309 250 176 52 224 275 430 383 905 139 790 179 766 289 222 90 346 550 567 639 596 94 32 733 678 946 33 250 380 717 721 21 609 871 761 829 721 900 671 651 74 699 829 605 701 161 435 980 504 123 474 686 745 768 424 383 909 603 360 660 140 718 272 938 465 4 814 526 711 705 465 88 532 782 589 796 734 686 334 84 959 325 774 457 923 36 978 314 45 341 157 960 282 950 478 406 463 936 775 644 452 33 555 949 510 600 769 464 285 815 304 670 24 387 443 256 97 585 626 142 643 761 277 859 262 843 20 541 745 99 550 275 998 207 25 751 485 796 40 855 978 228 258 589 991 438 321 646 382 144 342 250 518 297 876 573 352 239 149 922 810 778 310 397 255 384 436 953 534 284 523 365 158 247 707 490 764 524 795 902 325 278 255 534 743 783 729 600 780 530 842 986 625 990 590 675 346 809 911 977 656 634 984 310 74 657 566 165 906 547 990 15 300 52 389 376 853 480 669 584 355 806 68 728 407 724 391 703 481 169 617 353 349 698 959 517 827 961 677 313 173 867 85 728 6 295 910 372 518 864 189 446 945 579 548 610 794 796 224 185 261 887 220 366 310 641 193 630 587 853 831 978 702 588 829 296 433 102 834 536 600 579 894 968 632 368 299 179 463 284 741 537 753 205 322 652 648 65 939 367 874 296 885 91 665 161 675 847 979 796 832 830 251 63 203 844 97 485 638 597 388 408 50 687 995 974 765 212 744 365 561 249 600 970 953 564 279 21 7 27 62 425 158 301 741 189 198 84 143 722 258 914 469 975 28 613 855 266 795 413 130 809 655 21 438 802 934 576 230 205 651 898 743 369 443 846 807 953 512 805 914 599 656 635 764 229 782 709 965 673 778 4 791 762 151 724 858 284 795 614 164 223 865 593 81 830 674 600 88 937 518 924 911 91 81 954 341 492 6 926 604 505 731 483 136 82 117 977 530 244 41 822 151 689 766 165 930 229 578 284 443 553 962 808 663 949 415 77 670 708 566 468 822 855 156 23 519 389 7 581 688 704 394 564 526 548 907 520 48 627 26 730 991 472 608 213 816 946 37 415 81 309 897 136 982 585 402 232 810 287 385 761 295 971 61 126 84 501 910 227 786 80 608 733 439 579 384 558 102 285 945 238 959 38 202 445 95 662 754 122 580 406 467 162 298 844 506 859 270 998 821 332 110 546 905 413 106 378 441 480 841 207 779 109 462 267 540 170 559 231 292 739 204 944 424 733 923 358 343 856 545 493 19 25 476 502 410 6 228 850 753 546 110 332 573 120 150 404 655 139 436 107 600 929 426 423 58 629 668 55 891 292 326 317 164 21 262 306 548 793 1000 589 334 984 298 236 807 550 358 77 217 82 765 163 242 294 102 327 868 216 262 756 604 446 2 922 995 624 899 770 270 290 394 86 81 101 795 567 667 240 523 533 776 315 172 958 554 696 329 73 122 296 89 508 216 22 368 435 96 361 674 773 974 383 738 294 900 963 76 434 241 996 478 103 667 832 806 515 818 31 360 288 920 101 906 183 334 505 908 726 351 625 689 847 445 130 303 232 179 498 888 471 214 221 461 661 424 376 816 715 60 418 160 4 436 772 441 813 604 335 981 74 542 884 506 126 624 242 486 54 897 29 985 780 805 434 503 718 766 492 100 452 959 161 73 579 714 772 543 501 21 856 663 315 351 121 822 201 834 502 826 154 462 82 269 379 937 883 188 788 119 376 360 471 193 521 252 315 936 901 805 115 731 698 392 815 916 845 546 839 130 130 700 683 732 750 127 567 814 578 254 960 262 33 188 280 805 714 821 944 273 191 494 646 596 182 117 52 573 228 172 651 835 182 30 857 449 318 1000 218 361 269 736 839 243 512 321 745 95 898 390 192 587 423 576 984 112 333 184 199 619 847 239 63 319 770 919 531 499 400 777 947 532 203 32 74 436 482 822 23 104 681 849 223 768 941 460 715 416 218 299 312 731 957 513 326 542 158 38 76 542 79 391 948 897 947 714 877 828 69 748 452 578 97 28 896 564 570 456 224 701 574 47 729 300 977 29 320 860 415 953 202 7 418 623 404 910 848 132 398 588 449 978 77 79 83 171 983 790 873 371 136 884 451 656 660 650 793 279 727 478 910 755 156 437 33 151 589 16 103 177 131 97 538 582 421 239 465 791 46 198 722 130 498 381 836 169 720 724 579 988 332 196 382 445 810 998 165 717 318 266 236 346 848 747 400 666 221 325 940 708 573 298 827 672 40 460 671 609 17 671 125 293 270 510 142 257 770 925 381 50 611 904 207 600 955 119 594 405 382 168 984 166 836 4 338 392 498 166 458 299 4 938 440 432 269 295 593 727 594 264 520 858 812 543 34 777 635 575 396 180 448 136 400 518 330 469 781 246 12 27 284 568 312 788 159 677 253 902 651 55 671 28 550 744 477 628 834 175 475 260 14 128 573 468 239 474 498 725 569 721 457 702 45 491 242 209 345 32 929 767 136 184 316 23 747 442 647 532 531 811 483 490 847 682 589 710 287 437 99 189 726 944 747 102 44 637 509 128 124 353 314 765 958 884 341 47 213 706 988 13 925 469 950 211 787 28 253 278 429 13 164 123 3 24 996 83 111 74 484 604 8 203 421 605 260 272 223 212 681 16 92 260 381 621 783 621 569 695 845 110 434 739 31 988 673 647 43 519 993 898 780 874 92 631 569 271 236 335 533 765 762 826 419 157 1 193 684 262 964 580 540 440 30 598 866 939 464 405 813 842 806 604 226 240 651 192 520 886 398 196 472 686 526 591 234 245 90 380 825 295 849 695 537 831 654 539 60 653 93 662 704 578 989 350 409 727 676 744 446 982 518 740 32 386 136 994 421 55 199 831 329 774 696 128 215 254 503 764 989 4 681 211 551 532 508 744 862 959 644 21 330 106 22 508 598 542 207 965 809 881 215 897 579 700 511 311 642 795 520 794 91 49 646 658 718 117 370 587 913 39 996 524 983 817 386 351 398 258 556 593 448 413 955 771 614 669 289 198 684 939 885 583 118 640 945 303 877 506 512 149 233 658 303 113 126 236 193 769 30 882 540 884 210 628 983 395 556 87 917 672 309 811 935 127 586 876 693 606 996 21 582 781 922 886 957 166 280 873 194 31 683 935 898 137 826 782 726 897 318 65 75 724 202 347 534 424 30 735 124 691 173 750 488 350 383 680 613 293 839 785 90 19 244 833 968 628 562 689 105 725 548 412 579 858 848 391 68 58 567 197 643 559 807 555 82 20 301 45 592 436 145 785 375 801 387 830 227 412 873 705 673 245 207 292 536 285 182 550 156 123 136 197 450 510 17 503 680 939 974 964 449 523 38 978 954 168 380 392 635 485 195 451 278 262 515 30 87 700 847 548 291 374 684 18 857 512 898 393 680 761 750 477 99 53 135 225 666 886 538 478 379 515 705 151 513 591 717 882 34 260 52 400 421 992 591 16 495 519 465 819 118 697 974 747 560 230 749 298 363 490 192 700 353 399 497 45 73 640 573 401 593 959 444 297 280 459 956 551 305 346 418 560 682 702 533 736 69 696 59 198 482 491 704 841 913 416 546 197 494 628 574 965 12 824 896 669 929 18 133 239 878 741 101 594 625 391 152 420 161 4 396 791 946 222 558 651 693 549 101 962 461 665 665 198 737 190 232 482 964 601 502 385 324 838 595 895 362 815 316 684 123 672 933 740 52 385 653 738 272 97 86 526 760 138 579 333 230 45 42 327 854 314 356 531 852 769 613 44 899 208 52 647 340 331 670 435 694 822 575 517 347 151 267 832 540 738 189 621 533 402 569 740 379 621 832 435 306 910 895 473 799 395 553 628 4 433 301 443 793 973 724 527 504 342 212 866 510 119 442 829 276 96 63 583 963 627 615 98 458 188 519 846 223 620 56 436 35 274 261 677 722 703 804 110 786 908 778 18 294 479 923 116 977 757 22 130 247 620 364 985 646 677 919 552 601 489 41 539 126 348 244 321 276 514 59 795 220 981 404 298 932 71 797 589 483 876 38 589 903 184 577 55 793 295 641 512 437 765 753 294 217 277 692 355 18 268 167 321 731 668 70 132 653 183 220 596 428 508 584 146 411 598 785 828 966 219 289 102 601 206 843 999 232 605 238 121 327 57 213 127 553 654 770 149 221 738 454 144 103 214 585 28 635 199 537 945 182 430 182 721 760 628 41 604 237 816 33 645 361 294 399 300 684 459 220 431 866 695 59 679 800 943 767 819 527 300 508 939 571 272 393 610 550 702 13 212 389 177 662 451 773 401 698 386 797 972 826 539 646 568 685 699 23 729 34 725 903 554 575 50 851 906 354 48 139 953 948 337 265 585 592 791 533 438 551 713 205 590 646 535 364 512 501 190 967 21 390 891 720 361 139 417 191 139 597 515 230 446 200 392 218 326 165 595 65 396 683 378 901 145 313 828 753 740 544 958 275 35 955 220 472 426 787 277 306 414 275 580 83 804 146 984 778 433 83 508 412 135 450 969 135 108 301 514 307 899 435 973 667 331 535 880 761 905 479 392 425 191 634 447 916 700 940 583 353 284 899 346 671 392 832 366 221 746 287 917 324 6 340 480 83 789 60 943 931 860 572 311 224 828 611 322 661 939 946 672 547 704 736 510 375 990 910 716 630 260 571 948 707 506 215 179 100 628 976 828 504 834 333 916 586 159 704 17 181 461 674 88 896 943 934 62 140 132 62 632 322 828 454 884 758 691 320 273 946 442 742 320 613 206 603 214 950 865 227 672 383 655 802 127 871 119 825 899 335 289 626 45 825 926 351 682 844 439 531 127 802 515 692 859 852 395 33 184 286 433 960 223 273 992 927 284 32 527 592 908 657 493 224 638 703 287 735 566 27 818 814 702 461 638 363 382 486 740 958 679 715 214 133 936 276 549 64 621 314 831 499 583 494 668 83 192 471 784 912 619 641 105 724 443 879 346 496 828 906 141 36 381 964 131 244 86 562 102 603 609 861 297 942 795 119 811 440 589 31 352 826 610 11 967 180 671 42 305 163 241 333 26 490 352 156 174 327 430 231 79 554 474 405 328 646 370 345 322 215 823 972 435 314 646 613 643 513 663 126 811 17 719 538 567 20 869 121 774 520 975 550 435 624 748 757 67 696 262 633 767 558 919 87 685 571 805 768 510 986 84 72 116 44 612 158 985 558 905 65 517 439 766 336 685 400 523 279 838 17 911 415 112 485 357 909 385 209 196 98 731 896 112 953 819 641 700 247 333 935 478 921 349 69 982 626 985 737 576 278 27 219 616 571 697 504 431 107 804 440 370 953 849 58 875 253 653 291 572 33 110 734 858 762 426 861 816 233 878 219 15 880 510 522 994 579 559 579 592 32 274 614 927 37 689 195 862 186 991 65 779 11 446 92 720 739 73 611 605 744 473 544 402 237 881 456 346 709 810 97 805 574 395 981 190 540 570 383 702 836 294 572 568 336 424 280 17 904 483 120 821 934 239 12 776 564 942 912 688 855 285 400 331 742 378 953 647 870 214 873 295 339 605 174 178 579 47 726 130 376 264 625 61 808 61 316 911 890 197 757 756 401 637 979 982 662 402 781 674 978 555 623 20 51 527 849 910 137 766 980 622 693 457 946 346 926 44 308 592 460 257 883 50 482 852 70 650 576 477 187 48 399 549 341 271 437 96 894 992 780 741 986 616 904 565 318 524 472 546 102 583 482 880 315 503 152 334 253 396 70 368 378 273 826 565 707 590 577 154 681 357 14 869 475 701 931 711 406 240 511 257 863 668 55 744 730 510 648 625 667 921 60 58 105 598 64 48 452 223 407 745 434 961 734 51 510 549 541 826 74 785 370 973 195 708 326 436 105 468 593 519 307 104 89 354 156 451 983 478 889 571 692 765 521 354 142 380 182 814 614 467 634 113 181 784 538 156 856 625 707 154 898 151 488 998 612 527 171 412 191 609 165 347 205 849 250 121 192 8 713 198 42 785 446 628 464 73 99 888 906 456 340 883 80 474 283 26 756 121 22 114 64 906 449 48 290 511 408 474 669 138 340 45 570 875 97 587 579 437 227 760 684 650 783 747 862 924 185 63 182 197 65 442 47 258 662 431 212 50 660 304 673 37 610 453 528 517 880 691 272 257 315 762 624 557 37 424 673 132 733 333 720 692 223 54 895 710 657 882 613 188 260 453 928 243 165 751 325 255 289 282 749 833 974 160 815 818 355 741 562 909 87 980 633 571 561 96 624 777 593 392 353 352 747 711 639 821 92 437 235 822 374 510 556 203 783 899 857 303 67 525 898 254 986 851 155 143 31 800 411 95 207 191 189 748 844 730 435 164 387 945 411 850 316 435 430 510 492 943 383 299 658 222 203 90 335 645 359 467 839 738 895 647 550 650 34 988 50 766 617 628 934 723 946 547 32 816 118 775 55 404 56 823 65 485 303 740 369 675 33 93 241 662 734 743 120 759 558 174 409 542 383 360 526 600 397 865 748 820 887 947 161 363 11 127 611 509 722 748 593 700 469 992 920 375 344 903 93 215 224 656 227 269 481 766 27 75 241 59 922 555 287 557 397 855 309 916 868 256 498 23 756 765 494 506 748 284 552 178 481 117 764 519 970 490 941 21 260 985 813 767 610 29 230 780 573 819 339 574 327 539 115 609 177 764 830 210 812 666 457 566 971 29 667 879 376 576 92 457 328 321 306 257 977 414 341 587 171 162 704 648 792 848 375 981 624 821 69 68 107 990 892 786 53 29 405 485 223 675 269 677 543 843 92 336 597 810 345 784 180 539 636 690 33 143 511 300 544 685 248 97 69 673 704 807 983 378 660 280 641 398 611 557 799 242 263 322 851 197 498 453 912 81 960 680 633 224 284 710 92 754 447 62 473 489 129 678 292 54 105 882 486 249 889 609 38 127 790 193 332 281 24 95 482 271 155 651 419 343 635 230 383 586 763 246 483 544 594 803 526 602 575 275 757 3 182 891 121 57 150 795 161 954 201 368 816 636 947 571 278 771 17 872 758 292 618 168 520 777 661 152 782 466 878 10 196 130 105 711 548 374 341 894 688 888 608 940 577 39 582 34 417 745 280 474 498 741 950 8 92 314 325 271 846 731 584 782 562 384 293 346 119 640 830 380 720 963 667 840 332 973 417 748 476 637 106 268 773 280 520 401 41 701 381 834 232 217 818 899 600 190 426 39 676 766 423 189 536 343 998 736 961 156 726 343 957 840 323 566 301 123 400 685 441 841 800 293 232 127 139 72 287 727 618 664 573 362 383 334 940 116 307 86 777 346 476 128 195 837 292 775 524 154 949 779 111 404 506 470 912 355 916 518 75 978 646 104 55 172 215 38 979 820 352 811 209 380 409 877 613 441 559 453 304 127 752 716 107 984 657 530 761 827 878 419 158 914 629 422 104 456 412 268 126 289 697 523 200 75 693 923 91 836 92 472 913 400 856 763 335 917 479 555 268 478 712 738 684 835 787 360 226 637 857 805 850 156 676 965 560 985 470 343 27 43 673 241 52 486 397 104 497 287 749 612 707 458 146 310 718 216 49 50 63 262 679 746 664 764 377 979 529 992 316 161 975 470 929 714 503 151 200 246 52 627 851 45 577 430 21 820 396 759 596 598 213 494 63 331 91 761 669 800 984 7 291 202 528 891 694 647 285 807 823 150 182 309 370 549 529 542 930 431 215 628 307 510 885 193 234 217 684 499 113 875 825 424 463 788 747 355 978 905 73 239 374 914 250 647 960 942 260 50 563 790 761 615 960 999 192 509 233 757 309 29 317 473 440 492 275 769 953 264 371 914 361 969 201 986 830 439 977 905 223 753 280 936 28 469 985 512 930 769 351 965 382 734 957 376 64 769 75 230 411 542 94 858 192 380 103 224 769 96 804 714 18 178 948 138 535 299 957 759 180 127 660 172 236 557 316 688 620 509 763 596 404 506 83 904 389 176 633 507 421 402 897 437 464 595 233 489 933 807 223 679 552 246 522 598 161 658 475 850 267 829 958 805 314 290 86 428 952 54 126 102 987 39 187 312 351 831 483 440 155 607 492 872 552 474 522 941 865 975 163 212 403 240 935 795 724 886 252 204 269 466 636 303 812 283 232 302 623 701 378 587 340 100 692 111 585 384 165 515 318 469 424 193 761 433 949 487 386 151 463 695 940 744 523 566 540 696 584 47 916 677 56 168 760 555 480 271 582 545 990 368 811 791 684 972 698 173 846 891 952 318 579 744 524 138 365 576 263 805 498 691 281 858 201 785 215 68 130 730 145 654 174 274 51 419 537 935 686 819 219 591 856 183 882 752 867 684 195 365 764 110 232 203 960 631 1 47 673 222 82 757 865 746 822 821 454 272 140 672 388 978 818 829 961 708 242 816 608 388 324 705 695 743 6 969 233 681 263 890 806 677 726 496 331 119 126 425 613 816 925 874 227 712 575 394 607 710 956 525 793 66 231 615 661 873 793 127 72 254 91 871 167 612 3 167 191 212 832 128 709 697 73 337 810 937 292 219 706 694 376 443 680 782 579 48 953 702 621 829 887 379 870 893 994 451 77 742 243 837 133 132 240 285 333 271 721 190 363 493 145 895 541 795 793 982 189 226 229 917 468 906 717 572 205 180 824 672 140 940 509 437 962 19 163 367 52 291 807 474 278 555 942 357 936 460 383 373 772 387 308 219 535 617 5 672 877 923 966 791 838 478 813 158 34 399 826 891 715 826 891 755 367 831 4 20 142 386 369 292 423 252 315 947 196 352 535 460 481 225 861 321 229 908 242 147 484 122 158 725 968 211 269 462

使用时间： 0.012849807739257812s，满足题目 1s内处理10个cases