# Codeforces Round #383 (Div. 1), problem: (E) Arpa’s abnormal DNA and Mehrdad’s deep interest Solution in C/C++

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#define rank _ran

using namespace std;
typedef long long LL;
const int maxn = 200005;
const int inf = 1<<29;
const int tre = 120;

char S[maxn],T[maxn];
char str[maxn];int len,bit[maxn];
int bac[maxn],sa[maxn],SA[maxn];
int rank[maxn],Rank[maxn],h[maxn];

int ord[maxn],val[maxn];
int n,m,q,ans[maxn],id[maxn],idx;
int l[maxn],r[maxn],K[maxn],x[maxn],y[maxn];

struct RMQ {
int rmq[17][maxn];
void build(int len) {
for (int j=1;j<17;j++)
for (int i=0;i<=len;i++)
rmq[j][i]=min(rmq[j-1][i],rmq[j-1][i-(1<<j-1)]);
}
int query(int l,int r) {
if (l>r) return inf;
int j=bit[r-l+1];
return min(rmq[j][r],rmq[j][l+(1<<j)-1]);
}
}suf,rmq,rmqj;
void upd(int &x,int y) {if (x>y) x=y;}

void suffix(int alp) {
for (int i=0;i<=alp;i++) bac[i]=0;
for (int i=1;i<=len;i++) bac[str[i]]++;
for (int i=1;i<=alp;i++) bac[i]+=bac[i-1];
for (int i=1;i<=len;i++) sa[bac[str[i]]--]=i;
for (int i=1;i<=len;i++) rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
for (int p=1;p<=len;p<<=1) {
for (int i=1;i<=len;i++) bac[rank[sa[i]]]=i;
for (int i=len;i>=1;i--) if (sa[i]>p) SA[bac[rank[sa[i]-p]]--]=sa[i]-p;
for (int i=len-p+1;i<=len;i++) SA[bac[rank[i]]--]=i;
for (int i=1;i<=len;i++) Rank[SA[i]]=Rank[SA[i-1]]+(rank[SA[i]]!=rank[SA[i-1]]||rank[SA[i]+p]!=rank[SA[i-1]+p]);
swap(SA,sa);swap(rank,Rank);
}
for (int i=1;i<=len;i++) {
int j=sa[rank[i]-1],k=max(0,h[i-1]-1);
while (str[i+k]==str[j+k]) ++k;
h[i]=k;suf.rmq[0][rank[i]]=k;
}
suf.build(len);
}
int lcp(int u,int v) {
u=rank[u];v=rank[v];
if (u>v) swap(u,v);
return suf.query(u+1,v);
}
bool comp(int i,int j) {
if (i==j) return false;
bool sw=false;
if (i>j) swap(i,j),sw=true;
if (j-i>=m) {
int d=(j-i)-m,w=j-i;
int lcp1=lcp(n+1,i+1);
if (lcp1<m) return (rank[n+1]<rank[i+1])^sw;
int lcp2=lcp(i+1,i+1+m);
if (lcp2<d) return (rank[i+1]<rank[i+1+m])^sw;
int lcp3=lcp(i+1+d,n+1);
if (lcp3<m) return (rank[i+1+d]<rank[n+1])^sw;
}
else {
int d=m-(j-i),w=j-i;
int lcp1=lcp(n+1,i+1);
if (lcp1<w) return (rank[n+1]<rank[i+1])^sw;
int lcp2=lcp(n+1+w,n+1);
if (lcp2<d) return (rank[n+1+w]<rank[n+1])^sw;
int lcp3=lcp(i+1,n+1+d);
if (lcp3<w) return (rank[i+1]<rank[n+1+d])^sw;
}
return !sw;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("interest.in","r",stdin);
freopen("interest.out","w",stdout);
#endif
scanf("%s",S+1);n=strlen(S+1);
scanf("%s",T+1);m=strlen(T+1);
for (int i=1;i<=n;i++) str[++len]=S[i];
for (int i=1;i<=m;i++) str[++len]=T[i];
for (int i=2;i<=len;i++) bit[i]=bit[i>>1]+1;
suffix(128);

for (int i=0;i<=n;i++) ord[i]=i;
sort(ord,ord+n+1,comp);
for (int i=0;i<=n;i++) val[ord[i]]=i;
for (int i=0;i<=n;i++) rmq.rmq[0][i]=val[i];
rmq.build(n);

scanf("%d",&q);
for (int i=0;i<=q;i++) ans[i]=-1;
for (int i=1;i<=q;i++)
scanf("%d %d %d %d %d",&l[i],&r[i],&K[i],&x[i],&y[i]);
for (int i=1;i<=q;i++)
if (ans[i]<0) {
if (K[i]>tre) {
ans[i]=inf;
for (int j=0;j*K[i]<=r[i];j++)
upd(ans[i],rmq.query(max(l[i],j*K[i]+x[i]),min(r[i],j*K[i]+y[i])));
}
else {
idx=0;
for (int j=0;j<K[i];j++)
for (int k=0;k*K[i]+j<=n;k++)
rmqj.rmq[0][idx]=val[k*K[i]+j],id[k*K[i]+j]=idx++;
rmqj.build(idx);
for (int j=i;j<=q;j++)
if (K[j]==K[i]) {
ans[j]=inf;
for (int k=x[j];k<=y[j];k++) {
int L=l[j]/K[j]*K[j]+k;
int R=r[j]/K[j]*K[j]+k;
while (L<l[j]) L+=K[j];
while (R>r[j]) R-=K[j];
if (L<=R) upd(ans[j],rmqj.query(id[L],id[R]));
}
}
}
}
for (int i=1;i<=q;i++)
printf("%d ",ans[i]!=inf?ord[ans[i]]:-1);
return 0;
}
(Visited 14 times, 1 visits today)