Desen Sayma#2604

Desen Sayma

1 saniye
128 megabayt

Bir dizi ve bir desen kümesi verildiğinde, her bir desen için bu desenin dizide kaç farklı pozisyonda geçtiğini bulunuz.

Giriş

İlk satırda n~(1 \le n \le 10^5) uzunluğunda bir dizi verilir.

İkinci satırda desen sayısını belirten bir tam sayı k~(1 \le k \le 5 \cdot 10^5) verilir. Sonraki satırın her birinde bir desen bulunur. Tüm desenlerin toplam uzunluğu 5 \cdot 10^5'i geçmez.

Dizi ve desenler küçük Latin harflerinden '' - '' oluşur.

Çıktı

Her bir desen için, bu desenin dizi içinde kaç kez geçtiğini ayrı bir satırda yazdırınız.

Örnekler

Örnek 1

Loading
Loading