use std::cmp::Ordering; use std::cmp; use std::cmp::min; use std::collections::BTreeMap; use std::process; use std::cmp::Ord; use std::collections::HashMap; use std::collections::HashSet; use std::collections::VecDeque; use std::collections::BTreeSet; use std::mem; use std::collections::BinaryHeap; use std::hash::{Hash, Hasher}; pub struct Scanner { stdin: R, } impl Scanner { pub fn read(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::>(); std::str::from_utf8(&buf).unwrap() .parse() .ok() .expect("Parse error.") } pub fn vec(&mut self, n: usize) -> Vec { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec { self.read::().chars().collect() } } pub trait BinarySearch { fn lower_bound(&self, x:&T) -> usize; fn upper_bound(&self, x:&T) -> usize; } impl BinarySearch for VecDeque{ fn lower_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less => { low = mid + 1; } Ordering::Equal | Ordering::Greater => { high = mid; } } } low } fn upper_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less | Ordering::Equal => { low = mid + 1; } Ordering::Greater => { high = mid; } } } low } } impl BinarySearch for [T]{ fn lower_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less => { low = mid + 1; } Ordering::Equal | Ordering::Greater => { high = mid; } } } low } fn upper_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less | Ordering::Equal => { low = mid + 1; } Ordering::Greater => { high = mid; } } } low } } fn comb(a:usize, b:usize, fac:&Vec, ifac:&Vec)->usize{ let mut a = a; let mut b = b; if a == 0 && b == 0{return 1;} if a, ifac:&Vec)->usize{ if n == 0 && r == 0{ return 1; } return comb(n+r-1, r, fac, ifac); } fn modinv(a:usize, M:usize)->usize{ let mut b = M as i64; let mut u = 1 as i64; let mut v = 0 as i64; let mut a = a as i64; let mut m = M as i64; while(b>0){ let mut t = a/b; a -= t*b; mem::swap(&mut a, &mut b); u-=t*v; mem::swap(&mut u, &mut v); } u%=m; if u<0{u+=m;} return u as usize; } fn modpow(x:usize, n:usize) -> usize{ let mut ans = 1; let mut n = n as usize; let mut x = x; while(n != 0){ if (n&1 == 1){ans = ans*x%MODu;} x = x*x%MODu; n = n>>1; } ans } fn modpow2(x:i64, n:i64, m:i32) -> i64{ let mut ans = 1; let mut n = n as i64; let mut x = x; while(n != 0){ if (n&1 == 1){ans = ans*x%m as i64;} x = x*x%m as i64; n = n>>1; } ans } fn invs(max:usize)->(Vec, Vec){ let mut fac = vec![0;max+1]; let mut ifac = vec![0;max+1]; fac[0] = 1; ifac[0] = 1; for i in 0..max{ fac[i+1] = fac[i] * (i+1)%MODu; ifac[i+1] = ifac[i] * modpow(i+1, MODu - 2)%MODu; } (fac, ifac) } #[derive(Copy, Clone, Eq, PartialEq)] struct x{ a:i64, b:i64, c:i64, d:i64, } impl Ord for x{ fn cmp(&self, other:&Self)->Ordering{ (other.b * (self.a)).cmp(&((self.b)*other.a)) } } impl PartialOrd for x { fn partial_cmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } fn gcd(a:usize, b:usize)->usize{ if b==0{return a;} return gcd(b, a%b); } fn prime_factor(n:usize)->HashMap{ let mut res = HashMap::new(); let mut n = n; for i in 2..n{ if i*i>n{break;} while(n%i==0){ *res.entry(i).or_insert(0)+=1; n/=i; } } if n != 1{ res.insert(n, 1); } res } fn usize_multiply_is_overflow(a:usize, b:usize)->bool{ if a usize{ let mut ans = 1; let mut n = n; let mut x = x; while(n != 0){ if (n&1 == 1){ if usize_multiply_is_overflow(ans, x){ return 0; } ans = ans*x; } n = n>>1; if n == 0{ break; } if usize_multiply_is_overflow(x, x){ return 0; } x = x*x; } ans } fn tmp(x:usize, y:usize)->usize{ let mut ub = x+1; let mut lb = 1; while(ub-lb>1){ let mut mid = (ub+lb)/2; let mut now = pow2(mid, y); let mut ok = true; if now == 0{ ok = false; } if now>x { ok = false; } if ok{ lb = mid; } else{ ub = mid; } } return lb; } struct segment_tree{ n: usize, dat: Vec, op:Op, e:I, } impl segment_tree where Op: Fn(I, I) -> I, I:Copy{ pub fn new(n_:usize, op: Op, e:I)->Self{ let mut n = 1; while(n0){ k = (k-1)/2; self.dat[k] = (self.op)(self.dat[k*2 + 1], self.dat[k*2+2]); } } pub fn query_sub(&self, a:usize, b:usize, k:usize, l:usize, r:usize) -> I{ if r<=a || b<=l{return self.e;} if a<=l && r<=b{return self.dat[k];} else{ let mut vl = self.query_sub(a, b, k*2+1, l, (l+r)/2); let mut vr = self.query_sub(a, b, k*2+2, (l+r)/2, r); return (self.op)(vl, vr); } } pub fn query(&self, a:usize, b:usize)->I{ return self.query_sub(a, b, 0, 0, self.n); } } fn matmul_m(A:&Vec>, B:&Vec>) -> Vec>{ let mut C = vec![vec![0;B[0].len()];A.len()]; for i in 0..A.len(){ for k in 0..B.len(){ for j in 0..B[0].len(){ C[i][j] += A[i][k]*B[k][j]; C[i][j] %= MOD; } } } return C; } fn matpow(A:&mut Vec>, n:usize) -> Vec>{ let mut B = vec![vec![0;A.len()];A.len()]; for i in 0..A.len(){ B[i][i] = 1; } let mut n = n; let mut tmp = A.clone(); while(n>0){ if n&1 == 1{B = matmul_m(&B, &tmp);} tmp = matmul_m(&tmp, &tmp); n>>=1; } return B; } fn solve(){ let sssss = std::io::stdin(); let mut sc = Scanner { stdin: sssss.lock() }; let mut x:String = sc.read(); let mut x:Vec = x.chars().collect(); let mut y:String = sc.read(); let mut y:Vec = y.chars().collect(); let mut cx = vec![vec![0;x.len()+1];26]; let mut cy = vec![vec![0;y.len()+1];26]; for i in 0..x.len(){ cx[x[i] as usize- 'a' as usize][i+1]+=1; for j in 0..26{ cx[j][i+1]+=cx[j][i]; } } for i in 0..y.len(){ cy[y[i] as usize- 'a' as usize][i+1]+=1; for j in 0..26{ cy[j][i+1]+=cy[j][i]; } } let mut Q:usize = sc.read(); let mut L = x.len(); let mut size= vec![0;100]; size[1] = L; let mut now = 1; while(L>, cy:&Vec>, size:&Vec, c:usize, dp:&mut HashMap<(usize, usize, usize), usize> )->usize{ if dp.contains_key(&(l, r, c)){ return dp[&(l, r, c)]; } let mut level = size.lower_bound(&r); if l>r{ return 0; } if level == 1{ return cx[c][r]-cx[c][l-1]; } if level == 0{ return 0; } let mut leng = size[level]; let mut befl = size[level-1]; let mut a = befl; let mut b = befl+cy[0].len()-1; let mut res = 0usize; if r<=a{ res+=dfs(1, r, cx, cy, size, c, dp) } else if a