P17784 [HackerEarth] Ma5termind likes playing with strings a lot. He thinks that he is so good with strings that nobody can challenge him with a string problem. One fine day, ma5termind's best friend shasha
普及
题目描述

Ma5termind likes playing with strings a lot. He thinks that he is so good with strings that nobody can challenge him with a string problem. One fine day, ma5termind's best friend shasha came up with an interesting string problem and decided to challenge him.

Shasha gave him a string S consisting of N lower case letters and an integer Q denoting number of queries to be processed. Each query consists of 2 integers X and Y denoting the indices in the string S. For each query, ma5termind is asked to report the length of longest common prefix between the suffixes starting at position X and position Y.

That day, ma5termind came to know about the truth that he is not good with strings but to show off in front of his friend, he desperately wants to solve this problem. Can you please help him solving this problem ?
Input:
First line will contain two integers N and Q

Next line will contain a string S of length N.

Next Q line will contain two space-seperated integers X and Y.

Ouput:
For each query, print a single integer denoting the length of longest common prefix between the suffixes starting at position X and position Y.
Constraints:

1 ≤ N, Q ≤ 10^5
1 ≤ X, Y ≤ 10^5
S contains only lower case letters

See sample I/O for more clarification.

Scoring:

Subtask 1: 1 ≤ N, Q ≤ 1000 ( 40 pts )
Subtask 2: 1 ≤ N, Q ≤ 10^5 ( 60 pts )

SAMPLE INPUT
12 5
aabbccaabbcc
1 1
1 2
1 7
3 4
3 9

SAMPLE OUTPUT
12
1
6
1
4

Explanation

Q1 : "aabbccaabbcc" is the longest common prefix.
Q2 : "a" is the longest common prefix.
Q3 : "aabbcc" is the longest common prefix.
Q4 : "b" is the longest common prefix.
Q5 : "bbcc" is the longest common prefix.

输入格式

见题面

输出格式

见题面

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