问题描述

给定一个字符串 $S$，以及一个模式串 $P$，询问模式串 $P$ 在字符串 $S$ 中所有出现位置的下标。

下标从 $0$ 开始。

字符串仅由小写字母构成。

输入格式

第一行输入一个正整数 $N$，表示 $P$ 的长度。

第二行输入字符串 $P$。

第三行输入整数 $M$，表示字符串 $S$ 的长度。

第四行输入字符串 $S$。

$(1\le N\le 10^5,1\le M\le 10^6,N\le M)$

输出格式

输出一行，为所有出现位置的起始下标（下标从 $0$ 开始计数），整数之间用空格隔开。

样例输入

2
cb
6
abcbcb

样例输出

2 4