#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#define REP(i,k,n)  for(long long i=k;i<=n;i++)

#define in(a) a=read()

using namespace std;

inline long long read(){

    long long x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

long long ha[];

long long n,m,S;

char s[],t[];

long long sum[],poww[];

long long k=1e9,k1=1e7;

int main(){

    scanf("%s%s",s+,t+);

    n=strlen(s+),m=strlen(t+);

    poww[]=;

    REP(i,,n)  poww[i]=(poww[i-]*k)%k1;

    REP(i,,n)  sum[i]=(sum[i-]*k+(s[i]-'a'))%k1;

    REP(i,,m)  S=(S*k+(t[i]-'a'))%k1;

    REP(i,m,n)

        if(S%k1==(sum[i]-sum[i-m]*poww[m])%k1)  cout<<i<<endl;

}

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#define REP(i,k,n)  for(int i=k;i<=n;i++)

#define in(a) a=read()

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

int n,m;

char s[],t[];

int nxt[];

void getnxt(){

    int j=;

    nxt[]=;

    REP(i,,m){

        while(t[i+]!=t[j+] && j!=)  j=nxt[j];

        if(t[i+]==t[j+])  nxt[i+]=j+,j++;

        else  nxt[i+]=;

    }

}

void pipei(){

    int j=;

    REP(i,,n){

        while(s[i+]!=t[j+] && j!=)  j=nxt[j];

        if(s[i+]==t[j+])  j++;

        if(j==m)  cout<<i<<endl,j=nxt[j];

    }

}

int main(){

    scanf("%s%s",s+,t+);

    n=strlen(s+),m=strlen(t+);

    getnxt();

    pipei();

}
    

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#define REP(i,k,n)  for(int i=k;i<=n;i++)

#define in(a) a=read()

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

queue <int> Q;

int n;

int tree[][],total=,isend[],nxt[];

char t[],s[];

void insert(char *s){

    int l=strlen(s+),u=;

    REP(i,,l){

        if(!tree[u][s[i]-'a'])  tree[u][s[i]-'a']=++total;

        u=tree[u][s[i]-'a'];

    }

    isend[u]=;

    return ;

}

void getnxt(){

    REP(i,,)  tree[][i]=;

    Q.push(),nxt[]=;

    while(!Q.empty()){

        int u=Q.front();Q.pop();

        REP(i,,)

            if(!tree[u][i])  tree[u][i]=tree[nxt[u]][i];

            else  nxt[tree[u][i]]=tree[nxt[u]][i],Q.push(tree[u][i]);

    }

    return ;

}

void search(){

    int u=;

    REP(i,,strlen(s+)){

        int j=tree[u][s[i]-'a'],ans=;

        while(j>)  ans+=isend[j],isend[j]=,j=nxt[j];

        u=tree[u][s[i]-'a'];

        if(ans)  cout<<i<<endl;

    }

}

int main(){

    in(n);

    REP(i,,n)  scanf("%s",t+),insert(t);

    getnxt();

    scanf("%s",s+);

    search();

}

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#define REP(i,k,n)  for(int i=k;i<=n;i++)

#define in(a) a=read()

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

queue <int> Q;

int n,m;

int total,head[],to[],nxt[],val[],dis[],vis[];

void adl(int a,int b,int c){

    total++;

    to[total]=b;

    val[total]=c;

    nxt[total]=head[a];

    head[a]=total;

    return ;

}

void SPFA(){

    memset(dis,,sizeof(dis));

    Q.push(),dis[]=;

    while(!Q.empty()){

        int u=Q.front();Q.pop();vis[u]=;

        for(int e=head[u];e;e=nxt[e])

            if(dis[to[e]]>dis[u]+val[e]){

                dis[to[e]]=dis[u]+val[e];

                if(!vis[to[e]]){

                    vis[to[e]]=;

                    Q.push(to[e]);

                }

            }

    }

    return ;

}

int main(){

    in(n),in(m);

    int a,b,c;

    REP(i,,m)  in(a),in(b),in(c),adl(a,b,c);

    SPFA();

    REP(i,,n)  cout<<dis[i]<<" ";

}

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#define REP(i,k,n)  for(int i=k;i<=n;i++)

#define in(a) a=read()

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

int n,m;

int total,head[],to[],nxt[],val[];

int vis[],dis[];

struct node{

    int ind,val;

};

priority_queue <node> Q;

bool operator < (node a,node b){

    return a.val>b.val;

}

void adl(int a,int b,int c){

    total++;

    to[total]=b;

    val[total]=c;

    nxt[total]=head[a];

    head[a]=total;

    return ;

}

void Dijkstra(){

    memset(dis,,sizeof(dis));

    Q.push(node{,});dis[]=;

    while(!Q.empty()){

        int u=Q.top().ind;Q.pop();vis[u]=;

        for(int e=head[u];e;e=nxt[e])

            if(dis[to[e]]>dis[u]+val[e]){

                dis[to[e]]=dis[u]+val[e];

                Q.push(node{to[e],dis[to[e]]});

            }

    }

    return ;

}

int main(){

    in(n),in(m);

    int a,b,c;

    REP(i,,m)  in(a),in(b),in(c),adl(a,b,c);

    Dijkstra();

    REP(i,,n)  cout<<dis[i]<<" ";

}

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#define REP(i,k,n)  for(int i=k;i<=n;i++)

#define in(a) a=read()

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

int n,m;

int total,head[],to[],nxt[],val[];

int dis[],vis[];

void adl(int a,int b,int c){

    total++;

    to[total]=b;

    val[total]=c;

    nxt[total]=head[a];

    head[a]=total;

    return ;

}

void dfs(int u){

    for(int e=head[u];e;e=nxt[e]){

        if(dis[to[e]]>dis[u]+val[e]){

            dis[to[e]]=dis[u]+val[e];

            if(!vis[to[e]]){

                vis[to[e]]=;

                dfs(to[e]);

                vis[to[e]]=;

            }

            else  cout<<"polite",exit();

        }

    }

    return ;

}

int main(){

    in(n),in(m);

    int a,b,c;

    REP(i,,m)  in(a),in(b),in(c),adl(a,b,c);

    dis[]=;

    dfs();

}
    

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#include <stack>

#define REP(i,k,n)  for(int i=k;i<=n;i++)

#define in(a) a=read()

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

int n,m;

int total,head[],to[],nxt[],val[];

int dis[],vis[],book[];

stack <int> S;

void adl(int a,int b,int c){

    total++;

    to[total]=b;

    val[total]=c;

    nxt[total]=head[a];

    head[a]=total;

    return ;

}

void dfs(int u){

    book[u]=;

    for(int e=head[u];e;e=nxt[e]){

        if(dis[to[e]]>dis[u]+val[e]){

            dis[to[e]]=dis[u]+val[e];

            if(!vis[to[e]]){

                vis[to[e]]=;

                S.push(to[e]);

                dfs(to[e]);

                S.pop();

                vis[to[e]]=;

            }

            else{

                while(!S.empty() && S.top()!=to[e])  cout<<S.top()<<" ",S.pop();

                cout<<S.top(),S.pop(),exit();

            }

        }

    }

    return ;

}

int main(){

    in(n),in(m);

    int a,b,c;

    REP(i,,m)  in(a),in(b),in(c),adl(a,b,c);

    REP(i,,n)  if(!book[i])  S.push(i),vis[i]=,memset(dis,,sizeof(dis)),dfs(i);

    S.push();

}

/*

4 5

1 2 1

2 3 -1

3 1 -2

3 4 2

1 4 3

*/

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#include <stack>

#define REP(i,k,n)  for(int i=k;i<=n;i++)

#define in(a) a=read()

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

int n,m;

int total,head[],to[],nxt[];

int tree[][],depth[];

inline void adl(int a,int b){

    total++;

    to[total]=b;

    nxt[total]=head[a];

    head[a]=total;

    return ;

}

inline void dfs(int u,int fa){

    REP(i,,)  tree[u][i]=tree[tree[u][i-]][i-];

    for(int e=head[u];e;e=nxt[e])

        if(to[e]!=fa){

            depth[to[e]]=depth[u]+;

            tree[to[e]][]=u;

            dfs(to[e],u);

        }

    return ;

}

inline int lca(int u,int v){

    if(depth[u]<depth[v]) swap(u,v);

    int d=depth[u]-depth[v];

    for(int i=;(<<i)<=d;i++)  if((<<i) & d) u=tree[u][i];

    if(u==v)  return u;

    for(int i=;i>=;i--)  if(tree[u][i]!=tree[v][i])  u=tree[u][i],v=tree[v][i];

    return tree[u][];

}

int main(){

    in(n);

    int a,b;

    REP(i,,n-) in(a),in(b),adl(a,b),adl(b,a);

    depth[]=,dfs(,);

    in(m);

    REP(i,,m){

        in(a),in(b);

        printf("%d\n",lca(a,b));

    }

    return ;

}

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#include <stack>

#define REP(i,k,n)  for(int i=k;i<=n;i++)

#define in(a) a=read()

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

int n,m;

int tree[];

inline void add(int i,int a){

    for(;i<=n;i+=(i&-i))  tree[i]+=a;

    return ;

}

inline int get(int i){

    int ans=;

    for(;i>;i-=(i&-i))  ans+=tree[i];

    return ans;

}

int main(){

    in(n);

    int a,b,p;

    REP(i,,n)  in(a),add(i,a);

    in(m);

    REP(i,,m){

        in(p);

        if(p==)  in(a),in(b),add(a,b);

        else  in(a),in(b),printf("%d\n",get(b)-get(a-));

    }

}

/*

3

1 2 3

100

1 2 5

*/

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#include <stack>

#define REP(i,k,n)  for(int i=k;i<=n;i++)

#define in(a) a=read()

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

int n,m,a,b;

int s[][];

int Log[];

int main(){

    in(n);

    REP(i,,n)  in(s[i][]);

    REP(j,,)

        for(int i=;i+(<<j-)<=n;i++)

            s[i][j]=min(s[i][j-],s[i+(<<j-)][j-]);

    Log[]=;

    REP(i,,)  Log[i]=Log[i>>]+;

    in(m);

    REP(i,,m){

        in(a),in(b);

        int x=Log[b-a+];

        cout<<x<<" "<<b-(<<x)+<<endl;

        cout<<min(s[a][x],s[b-(<<x)+][x])<<endl;

    }

    return ;

}

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#include <stack>

#define REP(i,k,n)  for(int i=k;i<=n;i++)

#define in(a) a=read()

using namespace std;

inline int read(){

    int x=,f=;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar())

        if(ch=='-')

            f=-;

    for(;isdigit(ch);ch=getchar())

        x=x*+ch-'';

    return x*f;

}

int a,b,d,x,y,t;

void exgcd(int a,int b,int &d,int &x,int &y){

    if(b==)  x=,y=,d=a;

    else  exgcd(b,a%b,d,x,y),t=x,x=y,y=t-a/b*y;

    return ;

}

int main(){

    in(a),in(b);

    exgcd(a,b,d,x,y);

    cout<<x<<" "<<y<<endl;

}