마을의 그림자

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

요약

여러 정수 패턴과 하나의 그림자 배열이 주어질 때, 연속한 구간이 어떤 패턴에 양의 실수를 곱한 값과 같아지는 모든 등장 횟수를 센다.

난이도: 어려움10점 중 8점
유형: 문자열 매칭, 수학
정답자: 아직 제출이 없습니다

문제

아주 오래전 멀리 떨어진 은하에 마을이 하나 있었다. 마을은 사라지고 그림자만 남았다.

그 마을의 건물은 모두 한 직선 위에 같은 간격으로 서 있었다고 가정한다. 건물의 너비는 전부 같고 높이만 서로 달랐다. 건물은 이제 없고 그림자만 남아 있다. 그림자의 길이가 원래 건물의 높이와 같을 필요는 없다. 모든 그림자는 같은 양의 상수배로 늘어나거나 줄어들었을 수 있다.

이 행성에 살았던 문명의 건축을 알아내려고 한다. 건물 높이의 수열 여러 개가 주어지고, 이를 패턴이라고 부른다. 각 패턴이 원래 건물 배치에서 나타나는 자리를 모두 찾고 싶다.

보존된 그림자의 길이를 나타내는 양의 정수 수열이 주어진다. 질의도 여러 개 주어지고, 질의 하나가 패턴 하나를 준다. 패턴은 어떤 건물들의 높이를 나타내는 양의 정수 수열이다. 그림자 수열의 연속한 구간 하나가 패턴에 양의 실수 배율을 곱한 것과 완전히 같으면, 그 패턴이 그림자에 나타난다고 한다.

모든 패턴의 등장 횟수를 합해서 구하라. 등장하는 구간은 서로 겹칠 수 있다. 길이가 $1$ 인 패턴은 배율을 어떤 값에도 맞출 수 있으므로 그림자의 모든 자리에서 나타난다.

입력

첫째 줄에 패턴의 개수 $n$ 이 주어진다.

다음 $n$ 개 줄에 패턴이 한 줄에 하나씩 주어진다. 각 줄은 패턴의 길이 $l_i$ 로 시작하고, 이어서 $l_i$ 개의 양의 정수가 공백으로 구분되어 주어진다.

마지막 줄에 그림자가 주어진다. 그림자의 길이 $m$ 으로 시작하고, 이어서 $m$ 개의 양의 정수가 공백으로 구분되어 주어진다.

제한:

$1 \le n$
$1 \le m \le 3 \times 10^5$
$1 \le l_i$
$\sum l_i \le 3 \times 10^5$
입력에 등장하는 모든 높이와 그림자 길이는 $1$ 이상 $10000$ 이하이다.

출력

모든 패턴이 그림자에 나타나는 횟수의 총합을 한 줄에 정수 하나로 출력한다.

예제10

예제 1

입력

4
1 47
2 21 42
2 34 17
3 1 2 1
7 3 6 3 6 12 6 3

예상 출력

예제 2
입력
```
1
1 5
1 9
```
예상 출력
```
1
```
예제 3
입력
```
1
5 2 4 6 8 10
5 1 2 3 4 5
```
예상 출력
```
1
```
예제 4
입력
```
1
2 1 3
5 1 2 4 8 16
```
예상 출력
```
0
```
예제 5
입력
```
1
3 3 3 3
6 6 6 6 6 6 6
```
예상 출력
```
4
```
예제 6
입력
```
1
3 1 2 1
8 1 2 1 2 1 2 1 2
```
예상 출력
```
3
```
예제 7
입력
```
2
2 1 2
2 1 2
8 3 6 3 6 3 6 3 6
```
예상 출력
```
8
```

예제 8

입력

2
2 4 2
2 9999 3333
4 10000 5000 2500 1250

예상 출력

예제 9
입력
```
2
1 7
1 10000
5 4 4 4 4 4
```
예상 출력
```
10
```
예제 10
입력
```
2
4 1 2 4 8
1 3
3 5 10 20
```
예상 출력
```
3
```