input = """
1 2 0 0
1 3 0 0
1 4 0 0
1 5 0 0
1 6 0 0
1 7 0 0
1 8 0 0
1 9 0 0
1 10 0 0
1 11 0 0
1 12 0 0
1 13 0 0
1 14 0 0
1 15 0 0
1 16 0 0
1 17 0 0
1 18 0 0
1 19 0 0
1 20 0 0
1 21 0 0
1 22 0 0
1 23 0 0
1 24 0 0
1 25 0 0
1 26 0 0
1 27 0 0
1 28 0 0
1 29 0 0
1 30 0 0
1 31 0 0
1 32 0 0
1 33 0 0
1 34 0 0
1 35 0 0
1 36 0 0
1 37 0 0
1 38 0 0
1 39 0 0
1 40 0 0
1 41 0 0
1 42 0 0
1 43 0 0
1 44 0 0
1 45 0 0
1 46 0 0
1 47 0 0
1 48 0 0
1 49 0 0
1 50 0 0
1 51 0 0
1 52 0 0
1 53 0 0
1 54 0 0
1 55 0 0
1 56 0 0
1 57 0 0
1 58 0 0
1 59 0 0
1 60 0 0
1 61 0 0
1 62 0 0
1 63 0 0
1 64 0 0
1 65 0 0
1 66 0 0
1 67 0 0
1 68 0 0
1 69 0 0
1 70 0 0
1 71 0 0
1 72 0 0
1 73 0 0
1 74 0 0
1 75 0 0
1 76 0 0
1 77 0 0
1 78 0 0
1 79 0 0
1 80 0 0
1 81 0 0
1 82 0 0
1 83 0 0
1 84 0 0
1 85 0 0
1 86 0 0
1 87 0 0
1 88 0 0
1 89 0 0
1 90 0 0
1 91 0 0
1 92 0 0
1 93 0 0
1 94 0 0
1 95 0 0
1 96 0 0
1 97 0 0
1 98 0 0
1 99 0 0
1 100 0 0
1 101 0 0
1 102 0 0
1 103 0 0
1 104 0 0
1 105 0 0
1 106 0 0
1 107 0 0
1 108 0 0
1 109 0 0
1 110 0 0
1 111 0 0
1 112 0 0
1 113 0 0
1 114 0 0
1 115 0 0
1 116 0 0
1 117 0 0
1 118 0 0
1 119 0 0
1 120 0 0
1 121 0 0
1 122 0 0
1 123 0 0
1 124 0 0
1 125 0 0
1 126 0 0
1 127 0 0
1 128 0 0
1 129 0 0
1 130 0 0
1 131 0 0
1 132 0 0
1 133 0 0
1 134 0 0
1 135 0 0
1 136 0 0
1 137 0 0
1 138 0 0
1 139 0 0
1 140 0 0
1 141 0 0
1 142 0 0
1 143 0 0
1 144 0 0
1 145 0 0
1 146 0 0
1 147 0 0
1 148 0 0
1 149 0 0
1 150 0 0
1 151 0 0
1 152 0 0
1 153 0 0
1 154 0 0
1 155 0 0

1 156 0 0
1 157 0 0
1 158 0 0
1 159 0 0
1 160 0 0
1 161 0 0
1 162 0 0
1 163 0 0
1 164 0 0
1 165 0 0
1 166 0 0
1 167 0 0
1 168 0 0
1 169 0 0
1 170 0 0
1 171 0 0
1 172 0 0
1 173 0 0
1 174 0 0
1 175 0 0
1 176 0 0
1 177 0 0
1 178 0 0
1 179 0 0
1 180 0 0
1 181 0 0
1 182 0 0
1 183 0 0
1 184 0 0
1 185 0 0
1 186 0 0
1 187 0 0
1 188 0 0
1 189 0 0
1 190 0 0
1 191 0 0
1 192 0 0
1 193 0 0
1 194 0 0
1 195 0 0
1 196 0 0
1 197 0 0
1 198 0 0
1 199 0 0
1 200 0 0
1 201 0 0
1 202 0 0
1 203 0 0
1 204
 0 0
1 205 0 0
1 206 0 0
1 207 0 0
1 208 0 0
1 209 0 0
1 210 0 0
1 211 0 0
1 212 0 0
1 213 0 0
1 214 0 0
1 215 0 0
1 216 0 0
1 217 0 0
1 218 0 0
1 219 0 0
1 220 0 0
1 221 0 0
1 222 0 0
1 223 0 0
1 224 0 0
1 225 0 0
1 226 0 0
1 227 0 0
1 228 0 0
1 229 0 0
1 230 0 0
1 231 0 0
1 232 0 0
1 233 0 0
1 234 0 0
1 235 0 0
1 236 0 0
1 237 0 0
1 238 0 0
1 239 0 0
1 240 0 0
1 241 0 0
1 242 0 0
1 243 0 0
1 244 0 0
1 245 0 0
1 246 0 0
1 247 0 0
1 248 0 0
1 249 0 0
1 250 0 0
1 251 0 0
1 252 0 0
1 253 0 0
1 254 0 0
1 255 0 0
1 256 0 0
1 257 0 0
1 258 0 0
1 259 0 0
1 260 0 0
1 261 0 0
1 262 0 0
1 263 0 0
1 264 0 0
1 265 0 0
1 266 0 0
1 267 0 0
1 268 0 0
1 269 0 0
1 270 0 0
1 271 0 0
1 272 0 0
1 273 0 0
1 274 0 0
1 275 0 0
1 276 0 0
1 277 0 0
1 278 0 0
1 279 0 0
1 280 0 0
1 281 0 0
1 282 0 0
1 283 0 0
1 284 0 0
1 285 0 0
1 286 0 0
1 287 0 0
1 288 0 0
1 289 0 0
1 290 0 0
1 291 0 0
1 292 0 0
1 293 0 0
1 294 0 0
1 295 0 0
1 296 0 0
1 297 0 0
1 298 0 0
1 299 0 0
1 300 0 0
1 301 0 0
1 302 0 0
1 303 0 0
1 304 0 0
1 305 0 0
1 306 0 0
1 307 0 0
1 308 0 0
1 309 0 0
1 310 0 0
1 311 0 0
1 312 0 0
1 313 0 0
1 314 0 0
1 315 0 0
1 316 0 0
1 317 0 0
1 318 0 0
1 319 0 0
1 320 0 0
1 321 0 0
1 322 0 0
1 323 0 0
1 324 0 0
1 325 0 0
1 326 0 0
1 327 0 0
1 328 0 0
1 329 0 0
1 330 0 0
1 331 0 0
1 332 0 0
1 333 0 0
1 334 0 0
1 335 2 1 336 337
1 336 2 1 335 337
1 337 0 0
1 338 2 1 339 340
1 339 2 1 338 340
1 340 0 0
1 341 2 1 342 343
1 342 2 1 341 343
1 343 0 0
1 344 2 1 345 346
1 345 2 1 344 346
1 346 0 0
1 347 2 1 348 349
1 348 2 1 347 349
1 349 0 0
1 350 2 1 351 352
1 351 2 1 350 352
1 352 0 0
1 353 2 1 354 355
1 354 2 1 353 355
1 355 0 0
1 356 2 1 357 358
1 357 2 1 356 358
1 358 0 0
1 359 2 1 360 361
1 360 2 1 359 361
1 361 0 0
1 362 2 1 363 364
1 363 2 1 362 364
1 364 0 0
1 365 2 1 366 367
1 366 2 1 365 367
1 367 0 0
1 368 2 1 369 370
1 369 2 1 368 370
1 370 0 0
1 371 2 1 372 373
1 372 2 1 371 373
1 373 0 0
1 374 2 1 375 376
1 375 2 1 374 376
1 376 0 0
1 377 2 1 378 379
1 378 2 1 377 379
1 379 0 0
1 380 2 1 381 382
1 381 2 1 380 382
1 382 0 0
1 383 2 1 384 385
1 384 2 1 383 385
1 385 0 0
1 386 2 1 387 388
1 387 2 1 386 388
1 388 0 0
1 389 2 1 390 391
1 390 2 1 389 391
1 391 0 0
1 392 2 1 393 394
1 393 2 1 392 394
1 394 0 0
1 395 2 1 396 397
1 396 2 1 395 397
1 397 0 0
1 398 2 1 399 400
1 399 2 1 398 400
1 400 0 0
1 401 2 1 402 403
1 402 2 1 401 403
1 403 0 0
1 404 2 1 405 406
1 405 2 1 404 406
1 406 0 0
1 407 2 1 408 409
1 408 2 1 407 409
1 409 0 0
1 410 2 1 411 412
1 411 2 1 410 412
1 412 0 0
1 413 2 1 414 415
1 414 2 1 413 415
1 415 0 0
1 416 2 1 417 418
1 417 2 1 416 418
1 418 0 0
1 419 2 1 420 421
1 420 2 1 419 421
1 421 0 0
1 422 2 1 423 424
1 423 2 1 422 424
1 424 0 0
1 425 2 1 426 427
1 426 2 1 425 427
1 427 0 0
1 428 2 1 429 430
1 429 2 1 428 430
1 430 0 0
1 431 2 1 432 433
1 432 2 1 431 433
1 433 0 0
1 434 2 1 435 436
1 435 2 1 434 436
1 436 0 0
1 437 2 1 438 439
1 438 2 1 437 439
1 439 0 0
1 440 2 1 441 442
1 441 2 1 440 442
1 442 0 0
1 443 2 1 444 445
1 444 2 1 443 445
1 445 0 0
1 446 2 1 447 448
1 447 2 1 446 448
1 448 0 0
1 449 2 1 450 451
1 450 2 1 449 451
1 451 0 0
1 452 2 1 453 454
1 453 2 1 452 454
1 454 0 0
1 455 2 1 456 457
1 456 2 1 455 457
1 457 0 0
1 458 2 1 459 460
1 459 2 1 458 460
1 460 0 0
1 461 2 1 462 463
1 462 2 1 461 463
1 463 0 0
1 464 2 1 465 466
1 465 2 1 464 466
1 466 0 0
1 467 2 1 468 469
1 468 2 1 467 469
1 469 0 0
1 470 2 1 471 472
1 471 2 1 470 472
1 472 0 0
1 473 2 1 474 475
1 474 2 1 473 475
1 475 0 0
1 476 2 1 477 478
1 477 2 1 476 478
1 478 0 0
1 479 2 1 480 481
1 480 2 1 479 481
1 481 0 0
1 482 2 1 483 484
1 483 2 1 482 484
1 484 0 0
1 485 2 1 486 487
1 486 2 1 485 487
1 487 0 0
1 488 2 1 489 490
1 489 2 1 488 490
1 490 0 0
1 491 2 1 492 493
1 492 2 1 491 493
1 493 0 0
1 494 2 1 495 496
1 495 2 1 494 496
1 496 0 0
1 497 2 1 498 499
1 498 2 1 497 499
1 499 0 0
1 500 2 1 501 502
1 501 2 1 500 502
1 502 0 0
1 503 2 1 504 505
1 504 2 1 503 505
1 505 0 0
1 506 2 1 507 508
1 507 2 1 506 508
1 508 0 0
1 509 2 1 510 511
1 510 2 1 509 511
1 511 0 0
1 512 2 1 513 514
1 513 2 1 512 514
1 514 0 0
1 515 2 1 516 517
1 516 2 1 515 517
1 517 0 0
1 518 2 1 519 520
1 519 2 1 518 520
1 520 0 0
1 521 2 1 522 523
1 522 2 1 521 523
1 523 0 0
1 524 2 1 525 526
1 525 2 1 524 526
1 526 0 0
1 527 2 1 528 529
1 528 2 1 527 529
1 529 0 0
1 530 2 1 531 532
1 531 2 1 530 532
1 532 0 0
1 533 2 1 534 535
1 534 2 1 533 535
1 535 0 0
1 536 2 1 537 538
1 537 2 1 536 538
1 538 0 0
1 539 2 1 540 541
1 540 2 1 539 541
1 541 0 0
1 542 2 1 543 544
1 543 2 1 542 544
1 544 0 0
1 545 2 1 546 547
1 546 2 1 545 547
1 547 0 0
1 548 2 1 549 550
1 549 2 1 548 550
1 550 0 0
1 551 2 1 552 553
1 552 2 1 551 553
1 553 0 0
1 554 2 1 555 556
1 555 2 1 554 556
1 556 0 0
1 557 2 1 558 559
1 558 2 1 557 559
1 559 0 0
1 560 2 1 561 562
1 561 2 1 560 562
1 562 0 0
1 563 2 1 564 565
1 564 2 1 563 565
1 565 0 0
1 566 2 1 567 568
1 567 2 1 566 568
1 568 0 0
1 569 2 1 570 571
1 570 2 1 569 571
1 571 0 0
1 572 2 1 573 574
1 573 2 1 572 574
1 574 0 0
1 575 2 1 576 577
1 576 2 1 575 577
1 577 0 0
1 578 2 1 579 580
1 579 2 1 578 580
1 580 0 0
1 581 2 1 582 583
1 582 2 1 581 583
1 583 0 0
1 584 2 1 585 586
1 585 2 1 584 586
1 586 0 0
1 587 2 1 588 589
1 588 2 1 587 589
1 589 0 0
1 590 2 1 591 592
1 591 2 1 590 592
1 592 0 0
1 593 2 1 594 595
1 594 2 1 593 595
1 595 0 0
1 596 2 1 597 598
1 597 2 1 596 598
1 598 0 0
1 599 2 1 600 601
1 600 2 1 599 601
1 601 0 0
1 602 2 1 603 604
1 603 2 1 602 604
1 604 0 0
1 605 2 1 606 607
1 606 2 1 605 607
1 607 0 0
1 608 2 1 609 610
1 609 2 1 608 610
1 610 0 0
1 611 2 1 612 613
1 612 2 1 611 613
1 613 0 0
1 614 2 1 615 616
1 615 2 1 614 616
1 616 0 0
1 617 2 1 618 619
1 618 2 1 617 619
1 619 0 0
1 620 2 1 621 622
1 621 2 1 620 622
1 622 0 0
1 623 2 1 624 625
1 624 2 1 623 625
1 625 0 0
1 626 2 1 627 628
1 627 2 1 626 628
1 628 0 0
1 629 2 1 630 631
1 630 2 1 629 631
1 631 0 0
1 632 2 1 633 634
1 633 2 1 632 634
1 634 0 0
1 635 2 1 636 637
1 636 2 1 635 637
1 637 0 0
1 638 2 1 639 640
1 639 2 1 638 640
1 640 0 0
1 641 2 1 642 643
1 642 2 1 641 643
1 643 0 0
1 644 2 1 645 646
1 645 2 1 644 646
1 646 0 0
1 647 2 1 648 649
1 648 2 1 647 649
1 649 0 0
1 650 2 1 651 652
1 651 2 1 650 652
1 652 0 0
1 653 2 1 654 655
1 654 2 1 653 655
1 655 0 0
1 656 2 1 657 658
1 65