Принц чи самозванець
У давні часи і минулі віки та століття був у Персії великий цар Дарій. І квітнула у ті часи персидська держава, і було усього у достатку. В один прекрасний день у царя народився син, і не було у той день на землі щасливішої людини, ніж Дарій. Велике свято влаштував він на честь цієї події. Але доки йшли всі урочистості з нагоди народження намісника, найняті недругами Дарія ассасіни проникли у спальню і викрали дитину. Страшно розгнівився Дарій і наказав казнити охорону. А крім того, наказав цар оголосити розшук і пообіцяв величезну нагороду тому, хто знайде і поверне принца у дворець...
...Йшли дні, а за ними тижні, місяці і роки, але ніяких звісток про сина не поступало царю. І ось, коли пішов вісімнадцятий рік пошуків, у дворець увійшов стрункий високий юнак з вогником у погляді, який назвався тим самим пропавшим принцем. Неймовірні історії розповідав юнак. І про те, як його було підкинуто у сім'ю простого рибалки, якому під страхом смерті заборонили говорити про принца кому б то не було, і про те, як він жив усі ці роки, і про те, як, вмираючи, старий рибалка відкрив юнаку страшну таємницю про його посходження.
І вже готовий був Дарій повірити юнакові і прийняти його у свїи обійми, але візир порадив царю не поспішати, а спочатку зробити перевірку. Відомо, що кожна клітина організму людини містить ДНК, яка являє собою ланцюжок нуклеотидів, які кодуються символами A, G, T, C, і, кріме того, що ці ланзюжки у близьких родичів повинні бути схожими. Візир запропонував узяти деякий фрагмент ДНК юнака і порівняти з ДНК царя, починаючи з якоїсь позиції. Зорзуміло, найкращий варіант буде тоді, коли фрагмент у точності зустрінеться пачинаючи з обраної позиції. Але, взагалі кажучи, мірою схожості буде вважатись кількість співпадінь при порівнянні відповітдних елементів. Візир з царем просять вас визначити позицію, з якої слід починати порівяння для того, щоб степінь схожості був максимальним.
Вхідні дані
У першому рядку задано ДНК царя – послідовність символів A, G, T, C. У другому рядку аналогічним чином задано фрагмент ДНК юнака. Довжини рядків не перевищують 200000 і другий рядок не довше першого.
Вихідні дані
Виведіть номер позиції, з якої слід починати порівнянння для того, щоб добитись максимально можливої схожості. Якщо таких позицій декілька, виведіть першу з них. Позиції нумеруються з 1.