#include <iostream>
#include <cstring>

using namespace std;

char unu[2000000],doi[2000000];

struct h{
    long long hsha=0,hshb=0,v=37,pow=1,mod=1000000007;
    int lena=strlen(unu),lenb=strlen(doi);
    long long init(char st[]){
        int l=strlen(unu);
        long long po=1,hsh=0;
        for(int i=l-1;i>=0;i--){
           hsh=hsh+((po%mod)*st[i])%mod;
           po*=v;
        }
        pow=po;
        return hsh;
    }
    long long roll(long long hsh,int pos){
        hsh=((hsh-(doi[pos-lenb]*pow))%mod*v)%mod+doi[pos];
        return hsh;
    }
    void RK(char a[], char b[]){
        hsha=init(a);cout<<hsha<<"\n";
        hshb=init(b);cout<<hshb<<"\n";
        int lena=strlen(unu),lenb=strlen(doi);
        for(int i=0;i<=lenb-lena;i++){
            if(hsha==hshb){
                cout<<i<<"\n";
            }
            cout<<hsha<<" "<<hshb<<"\n";
            roll(hshb,i+1);
        }
        return;
    }
}wow;




int main()
{
    cin.getline(unu,2000001);
    cin.getline(doi,2000001);
    wow.RK(unu,doi);
}