길이가 동일한 수열 X = (x₀, x₁, …, x_n-1)와 Y = (y₀, y₁, …, y_n-1)가 있다.

이 두 수열의 각 원소는 음이 아닌 정수이다.

다음은 n=5인 경우의 한 예이다.

X = (1, 0, 0, 0, 1)

Y = (0, 5, 2, 0, 1)

임의의 정수 t가 주어졌을 때 XCorr(t)는 다음과 같이 정의된다.

(i < 0 이거나 i ≥ n 이면 x_i = y_i = 0으로 간주한다.)

예를 들어 t가 0, 1, -1일 때, XCorr(t)값은 다음과 같이 계산된다.

회색 칸에 들어있는 부분은 계산결과에 영향을 주지 않음에 유의하라. 

y₀는 계산식에 포함되지 않고 x_n-1은 곱해지는 y_n = 0이므로 계산 결과에 영향을 주지 않는다.

따라서 예시 수열 X와 Y에서 XCorr(1)은 다음과 같이 계산할 수 있다.

임의의 t값의 범위( a ≤ t ≤ b)에 대해 XCorr(t)를 모두 구해서 더한 값 S(a, b)는 다음과 같이 정의된다.

수열 X, Y와 t의 범위 a, b가 주어졌을 때 S(a, b)를 구하는 프로그램을 작성하시오.

소스파일의 이름은 XCorr.c 또는 XCorr.cpp를 권장하지만, 서버에 제출하는 데는 다른 이름도 상관없다.

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수열 X에서 0 이 아닌 정수의 개수 N이 주어진다.(수열 X의 길이 n이 아님).

다음 N개의 줄에는 수열 X의 각 양의 정수 값 x_i에 대해 인덱스 i와 x_i값이 인덱스의 오름차순으로 주어진다. 

다음 줄부터는 수열 Y가 X와 동일한 방식으로 주어진다. 

(Y에서 0 이 아닌 정수의 개수 M이 주어지고 다음 M개의 줄에는 수열 Y의 각 양의 정수 값 y_i에 대해 인덱스 i와 y_i값이 인덱스의 오름차순으로 주어진다.) 

다음 줄에는 t의 범위의 최솟값인 정수 a가 주어지고 그 다음 줄에는 t의 범위의 최댓값인 정수 b(a <= b)가 주어진다.

표준 출력으로 값을 정수로 출력하라.

[부분문제의 제약 조건] 

* 부분문제 1: 전체 100점 중 19점에 해당하며 1 ≤ N, M ≤ 3,000, 1 ≤ n ≤ 3,000, -3,000 ≤ a ≤ b ≤ 3,000이다. 

* 부분문제 2: 전체 100점 중 42점에 해당하며 1 ≤ N, M ≤ 3 × 10⁵, 1 ≤ n ≤ 3 × 10⁵​, -3 × 10​⁵​ ≤ a ≤ b ≤ 3 × 10​⁵​이다. 

* 부분문제 3: 전체 100점 중 39점에 해당하며 1 ≤ N, M ≤ 3 × 10⁵, 1 ≤ n ≤ 10⁹​, -10⁹​ ≤ a ≤ b ≤ 10⁹​ ​​이다.