Анаграммы-2

시간 제한3초메모리 제한1024 MB

요약

두 배열에서 각각 하나씩 고른 부분배열 중 서로 애너그램이 되는 가장 긴 쌍을 찾고, 길이와 시작 위치를 출력합니다.

난이도: 보통10점 중 7점
유형: 해시맵, 이분 탐색, 슬라이딩 윈도우, 수학
정답자: 아직 제출이 없습니다

문제

Недавно Человек-Невидимка от нечего делать прогуливался по крышам домов и случайно подслушал интересный разговор, доносящийся из открытого окна последнего этажа. Разговаривали два человека, одного из которых звали <<Нолик>>, а второго --- <<Симка>>. <<Странные имена>>, --- подумал Человек-Невидимка. Но для него это было неважно, намного интереснее была тема разговора --- это было что-то, связанное с программированием, а он никогда не мог пройти мимо такого соблазна.

Внимательно все послушав, Человек-Невидимка понял, что суть задачи, которую обсуждали эти два странных человека, состоит в следующем: по данному массиву-шаблону и массиву-тексту надо было понять, существует ли такой подотрезок текста, совпадающий с массивом-шаблоном как анаграмма. Под анаграммами в данном случае понимались два слова, в которых можно как-то переставить буквы, чтобы они стали одинаковыми. Оценив задачу, Человек-Невидимка понял, что она для него слишком простая, поэтому он решил усложнить ее. После некоторых раздумий, ему в голову пришла следующая ее модификация: по данным двум массивам требовалось найти такое максимальное число $k$ , что в первом и втором массивах существуют подотрезки длиной $k$ , совпадающие как анаграммы. Но эта задача уже оказалась Человеку-Невидимке не по силам, поэтому он попросил у вас помощи в решении этой задачи.

입력

В первой строке входного файла дано число $n$ ( $1 \le n \le 1\\,000$ ) --- длина первого массива.

Во второй строке через пробел заданы $n$ чисел $a\_i$ ( $1 \le a\_i \le 100\\,000$ ) --- первый массив.

В третьей строке дано число $m$ ( $1 \le m \le 1\\,000$ ) --- длина второго массива.

В четвертой строке через пробел заданы $m$ чисел $b\_i$ ( $1 \le b\_i \le 100\\,000$ ) --- второй массив.

출력

В единственной строке выходного файла выведите три неотрицательных числа $k, i, j$ --- максимальная длина подотрезков, совпадающих как анаграммы, а также начало отрезка в первом массиве и во втором соответственно. Если максимальная длина подотрезка равна 0, следующие два числа в выходном файле должны равняться -1.

예제2

예제 1
입력
```
3
1 2 3
3
3 2 1
```
예상 출력
```
3 1 1
```
예제 2
입력
```
3
1 2 3
3
4 5 6
```
예상 출력
```
0 -1 -1
```