एल्गोरिदम और डेटा संरचनाएँ

सबस्ट्रिंग (Substring) सर्च

आपको एक लंबा टेक्स्ट t दिया गया है और एक स्ट्रिंग s दी गई है। आपका कार्य है टेक्स्ट t में मौजूद स्ट्रिंग s के सभी अवतरण (occurrences) खोजना। आपको उन सभी शुरुआती पोज़ीशन को ढूँढना है जहाँ t में s संपूर्ण रूप से मिलता है।

इनपुट

पहली पंक्ति में टेक्स्ट t होता है (1 ≤ |t| ≤ )।

दूसरी पंक्ति में स्ट्रिंग s होती है (1 ≤ |s| ≤ |t|)।

आउटपुट

टेक्स्ट t में जहाँ-जहाँ स्ट्रिंग s मिलता है, उन सभी शुरुआत पोज़ीशन को स्पेस से अलग करते हुए प्रिंट करें। ये पोज़ीशन आरोही क्रम (टेक्स्ट की शुरुआत से अंत की ओर) में होने चाहिए। पोज़ीशन की गिनती 0 से शुरू होती है।

Examples

Input

Output

habababohabo
ba

2 4

barfoobarfoobarfoobarfoobarfoo
foobarfoo

3 9 15 21

Explanation

  1. habababohabo → habababohabo, habababohabo

  2. barfoobarfoobarfoobarfoobarfoo → barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB