macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; input_inner ! { iter , $ ( $ r ) * } } ; ( iter = $ iter : ident , $ ( $ r : tt ) * ) => { let s = { use std :: io :: Read ; let mut s = String :: new ( ) ; std :: io :: stdin ( ) . read_to_string ( & mut s ) . unwrap ( ) ; s } ; let mut $ iter = s . split_whitespace ( ) ; input_inner ! { $ iter , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let s = { use std :: io :: Read ; let mut s = String :: new ( ) ; std :: io :: stdin ( ) . read_to_string ( & mut s ) . unwrap ( ) ; s } ; let mut iter = s . split_whitespace ( ) ; input_inner ! { iter , $ ( $ r ) * } } ; }
macro_rules ! input_inner { ( $ iter : expr ) => { } ; ( $ iter : expr , ) => { } ; ( $ iter : expr , mut $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let mut $ var = read_value ! ( $ iter , $ t ) ; input_inner ! { $ iter $ ( $ r ) * } } ; ( $ iter : expr , mut $ var : ident $ ( $ r : tt ) * ) => { input_inner ! { $ iter , mut $ var : usize $ ( $ r ) * } } ; ( $ iter : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ iter , $ t ) ; input_inner ! { $ iter $ ( $ r ) * } } ; ( $ iter : expr , $ var : ident $ ( $ r : tt ) * ) => { input_inner ! { $ iter , $ var : usize $ ( $ r ) * } } ; }
macro_rules ! read_value { ( $ iter : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ iter , $ t ) ) ,* ) } ; ( $ iter : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ iter , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ iter : expr , { chars : $ base : expr } ) => { read_value ! ( $ iter , String ) . chars ( ) . map ( | c | ( c as u8 - $ base as u8 ) as usize ) . collect ::< Vec < usize >> ( ) } ; ( $ iter : expr , { char : $ base : expr } ) => { read_value ! ( $ iter , { chars : $ base } ) [ 0 ] } ; ( $ iter : expr , chars ) => { read_value ! ( $ iter , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ iter : expr , char ) => { read_value ! ( $ iter , chars ) [ 0 ] } ; ( $ iter : expr , usize1 ) => { read_value ! ( $ iter , usize ) - 1 } ; ( $ iter : expr , $ t : ty ) => { $ iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) } ; }
#[derive(Clone, Debug)]
pub struct Xorshift {
    y: u64,
}
impl Xorshift {
    pub fn new(seed: u64) -> Self {
        Xorshift { y: seed }
    }
    pub fn time() -> Self {
        let seed = std::time::SystemTime::now()
            .duration_since(std::time::UNIX_EPOCH)
            .ok()
            .unwrap_or_default()
            .as_secs() as u64;
        Xorshift::new(seed)
    }
    #[inline]
    pub fn next(&mut self) -> u64 {
        self.y ^= self.y << 5;
        self.y ^= self.y >> 17;
        self.y ^= self.y << 11;
        self.y
    }
    #[inline]
    pub fn rand(&mut self, k: u64) -> u64 {
        self.next() % k
    }
    #[inline]
    pub fn rands(&mut self, k: u64, n: usize) -> Vec<u64> {
        (0..n).map(|_| self.rand(k)).collect::<Vec<_>>()
    }
    #[inline]
    pub fn randf(&mut self) -> f64 {
        const UPPER_MASK: u64 = 0x3FF0000000000000;
        const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF;
        let tmp = UPPER_MASK | (self.next() & LOWER_MASK);
        let result: f64 = unsafe { std::mem::transmute(tmp) };
        result - 1.0
    }
}
#[derive(Clone, Debug)]
pub struct RollingHash {
    base: u64,
    hash: Vec<u64>,
    pow: Vec<u64>,
}
const MASK30: u64 = (1 << 30) - 1;
const MASK31: u64 = (1 << 31) - 1;
const MASK61: u64 = (1 << 61) - 1;
pub const MOD: u64 = MASK61;
impl RollingHash {
    #[inline]
    pub fn mersenne_mod(a: u64) -> u64 {
        let mut res = (a >> 61) + (a & MASK61);
        if res >= MASK61 {
            res -= MASK61;
        }
        res
    }
    #[inline]
    pub fn mersenne_mul(a: u64, b: u64) -> u64 {
        let au = a >> 31;
        let ad = a & MASK31;
        let bu = b >> 31;
        let bd = b & MASK31;
        let mid = ad * bu + au * bd;
        let midu = mid >> 30;
        let midd = mid & MASK30;
        au * bu * 2 + midu + (midd << 31) + ad * bd
    }
    #[inline]
    pub fn mersenne_mul_mod(a: u64, b: u64) -> u64 {
        Self::mersenne_mod(Self::mersenne_mul(a, b))
    }
    pub fn new(v: &Vec<u64>, base: u64) -> Self {
        let n = v.len();
        let mut hash = vec![0; n + 1];
        let mut pow = vec![1; n + 1];
        for i in 0..n {
            hash[i + 1] = Self::mersenne_mod(Self::mersenne_mul(hash[i], base) + v[i]);
            pow[i + 1] = Self::mersenne_mul_mod(pow[i], base);
        }
        RollingHash {
            base: base,
            hash: hash,
            pow: pow,
        }
    }
    #[doc = " S [l, r)"]
    pub fn find(&self, l: usize, r: usize) -> u64 {
        Self::mersenne_mod(
            self.hash[r] + MOD - Self::mersenne_mul_mod(self.hash[l], self.pow[r - l]),
        )
    }
    pub fn concat(&self, h1: u64, h2: u64, l2: usize) -> u64 {
        Self::mersenne_mod(Self::mersenne_mul(h1, self.pow[l2]) + h2)
    }
}
pub struct MultipleRollingHash {
    rh: Vec<RollingHash>,
}
impl MultipleRollingHash {
    pub fn new(v: &Vec<u64>, bases: &Vec<u64>) -> Self {
        let rh = bases
            .iter()
            .map(|&base| RollingHash::new(v, base))
            .collect::<Vec<_>>();
        MultipleRollingHash { rh: rh }
    }
    pub fn new_rand(v: &Vec<u64>, n: usize) -> Self {
        let mut rand = Xorshift::time();
        let bases = rand
            .rands(MASK61 - 2, n)
            .into_iter()
            .map(|base| base + 2)
            .collect::<Vec<_>>();
        Self::new(v, &bases)
    }
    pub fn find(&self, l: usize, r: usize) -> Vec<u64> {
        self.rh.iter().map(|h| h.find(l, r)).collect::<Vec<_>>()
    }
    pub fn concat(&self, h1: &Vec<u64>, h2: &Vec<u64>, l2: usize) -> Vec<u64> {
        self.rh
            .iter()
            .zip(h1.iter().zip(h2.iter()))
            .map(|(h, (&hi1, &hi2))| h.concat(hi1, hi2, l2))
            .collect::<Vec<_>>()
    }
}
#[allow(unused_imports)]
use std::io::{stdout, BufWriter, StdoutLock, Write};
fn with_bufwriter<F: FnOnce(&mut BufWriter<StdoutLock>) -> std::io::Result<()>>(
    f: F,
) -> std::io::Result<()> {
    let stdout = stdout();
    let mut writer = BufWriter::new(stdout.lock());
    f(&mut writer)
}
fn main() {
    input! { t: chars, p: chars };
    let mut s = vec![];
    let n = t.len();
    let m = p.len();
    s.extend(t.iter().map(|&x| x as u64));
    s.push(1000);
    s.extend(p.iter().map(|&x| x as u64));
    let rh = MultipleRollingHash::new_rand(&s, 2);
    let h = rh.find(n + 1, n + m + 1);
    with_bufwriter(|out| {
        for i in 0..n {
            if rh.find(i, i + m) == h {
                writeln!(out, "{}", i)?;
            }
        }
        Ok(())
    })
    .unwrap();
}



Measured memory_bytes: 51100