Problem:


Score : 500 points

Problem Statement

On a two-dimensional plane, there are m lines drawn parallel to the x axis, and n lines drawn parallel to the y axis.
Among the lines parallel to the x axis, the i-th from the bottom is represented by y = y_i.
Similarly, among the lines parallel to the y axis, the i-th from the left is represented by x = x_i.

For every rectangle that is formed by these lines, find its area, and print the total area modulo 10^9+7.

That is, for every quadruple (i,j,k,l) satisfying 1\leq i < j\leq n and 1\leq k < l\leq m, find the area of the rectangle formed by the lines x=x_i, x=x_j, y=y_k and y=y_l, and print the sum of these areas modulo 10^9+7.

Constraints

2 \leq n,m \leq 10^5

-10^9 \leq x_1 < ... < x_n \leq 10^9

-10^9 \leq y_1 < ... < y_m \leq 10^9

x_i and y_i are integers.

Input

Input is given from Standard Input in the following format:

n m
x_1 x_2 ... x_n
y_1 y_2 ... y_m

Output

Print the total area of the rectangles, modulo 10^9+7.

Sample Input 1

3 3
1 3 4
1 3 6

Sample Output 1

60

The following figure illustrates this input:

The total area of the nine rectangles A, B, ..., I shown in the following figure, is 60.

Sample Input 2

6 5
-790013317 -192321079 95834122 418379342 586260100 802780784
-253230108 193944314 363756450 712662868 735867677

Sample Output 2

835067060



Sample input:
3 3
1 3 4
1 3 6


Sample output:
60

Submission status: Runtime Error

Solution code:
num = input().split(" ")
vertical = list(map(int, input().split()))
horizontal = list(map(int, input().split()))

xlen = list()
ylen = list()
temp = 0

a = int(num[0])
b = int(num[1])

for i in range(a):
	for j in range(1, a - i):
		xlen.append(abs(vertical[i] - vertical[a - j]))

for i in range(b):
	for j in range(1, b - i):
		ylen.append(abs(horizontal[i] - horizontal[a - j]))

for i in range(len(xlen)):
	for j in range(len(ylen)):
		temp += xlen[i] * ylen[j]

ans = temp % (10**9 + 7)

print(ans)

Submission status: Runtime Error

Solution code:
num = input().split(" ")
vertical = list(map(int, input().split()))
horizontal = list(map(int, input().split()))

xlen = list()
ylen = list()
temp = 0

a = int(num[0])
b = int(num[1])

for i in range(a):
	for j in range(1, a - i):
		xlen.append(abs(vertical[i] - vertical[a - j]))

for i in range(b):
	for j in range(1, b - i):
		ylen.append(abs(horizontal[i] - horizontal[a - j]))

print(xlen)
print(ylen)

for i in range(len(xlen)):
	for j in range(len(ylen)):
		temp += xlen[i] * ylen[j]

ans = temp % (10**9 + 7)

print(ans)

Submission status: Runtime Error

Solution code:
num = input().split().int()


print(num)

Submission status: Runtime Error

Solution code:
in1 = list(input().split())
nx = in[0]
ny = in[y]
x = list(input().split())
y = list(input().split())
lx = sum([ x[i]*(2*i - x - 1) for i in range(nx) ])
ly = sum([ y[i]*(2*i - x - 1) for i in range(ny) ])
print(lx*ly%(10**9 + 7))

Submission status: Runtime Error

Solution code:
n, m = input().split()
n = int(n)
m = int(m)
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]

s = 0

map = [[0 for i in range(n)] for j in range(m)]

yokomap = [0] * n
tatemap = [0] * m

for i in range(n-1):
    for j in range(m-1):
        yokomap = (i+1) * (n-1-i)
        tatemap = (j+1) * (m-1-j)
        map[i][j] = yokomap * tatemap

for i in range(n-1):
    for j in range(m-1):
        yoko = x[i+1] - x[i]
        tate = y[j+1] - y[j]
        s += yoko * tate * map[i][j]
        s %= (10**9 + 7)


print(s)

Submission status: Runtime Error

Solution code:
n, m = input().split()
n = int(n)
m = int(m)
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]

s = 0

map = [[0 for i in range(n)] for j in range(m)]

yokomap = [0] * n
tatemap = [0] * m

for i in range(n-1):
    for j in range(m-1):
        yokomap = (i+1) * (n-1-i)
        tatemap = (j+1) * (m-1-j)
        map[i][j] = yokomap * tatemap

for i in range(n-1):
    for j in range(m-1):
        yoko = x[i+1] - x[i]
        tate = y[j+1] - y[j]
        s += yoko * tate * map[i][j]

s %= (10**9 + 7)

print(s)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from numpy import array, matrix
N, M = [int(n) - 1 for n in input().split()]
pre_x_ = array([int(n) for n in input().split()])
pre_y_ = array([int(n) for n in input().split()])

x_ = pre_x_[1:N+1] - pre_x_[0:N]
y_ = pre_y_[1:M+1] - pre_y_[0:M]

x_length_arr = np.zeros(int(N * (N+1)/2))
y_length_arr = np.zeros(int(M * (M+1)/2))

x_past_sets = np.zeros(N)
y_past_sets = np.zeros(M)

for n in range(N):
    x_past_sets += array([x_[n]]*(n+1) + [0] * (N-n-1))
    x_length_arr[int(n*(n+1)/2):int((n+1)*(n+2)/2)] = x_past_sets[0:n+1]

for m in range(M):
    y_past_sets += array([y_[m]]*(m+1) + [0] * (M-m-1))
    y_length_arr[int(m*(m+1)/2):int((m+1)*(m+2)/2)] = y_past_sets[0:m+1]

x_length_mat = matrix(x_length_arr)
y_length_mat = matrix(y_length_arr)

print(int((x_length_mat.T.dot(y_length_mat)).sum()%(10**9+7)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import os
import sys
import math
import numpy as np

n, m = map(int, input().split())
X = input().split()
X = list(map(int, X))
X = np.array(X)
Y = input().split()
Y = list(map(int, Y))
Y = np.array(Y)


# 1 つの最小長方形は (n-1)*(m-1) 回加算される

S = 0
mod = 10 ** 9 + 7

X_dif = X[1:]-X[:-1]
Y_dif = Y[1:]-Y[:-1]
Y_dif = Y_dif.reshape(m-1,1)
# print(X)
M = X_dif * Y_dif
M = M%mod

# print(M)

x_times = [(x+1) * (n-x-1) for x in range(n-1)]
x_times = np.array(x_times)
y_times = [(y+1) * (m-y-1) for y in range(m-1)]
y_times = np.array(y_times)

y_times = y_times.reshape(m-1,1)
# print(X)
MM = x_times * y_times
MM = MM%mod

# print(MM)

print(np.sum(M*MM)%mod)


# for x in range(n-1):
# 	for y in range(m-1):
# 		var = (X[x+1]-X[x]) * (Y[y+1]-Y[y])
# 		# print(var)
# 		x_times = (x+1) * (n-x-1)
# 		y_times = (y+1) * (m-y-1)

# 		S += ((var * x_times * y_times) % mod)


# # print(S%mod)

Submission status: Runtime Error

Solution code:
    from sys import stdin
    n,m = map(int,stdin.readline().split())
    a = map(int,stdin.readline().split())
    b = map(int,stdin.readline().split())
    a.sort()
    b.sort()
    x = []
    y = []
    for i in xrange(1,n):
        x.append(a[i] - a[i-1])
    for i in xrange(1,m):
        y.append(b[i] - b[i-1])   
    fir = 0
    sec = 0
    n = len(x)
    m = len(y)
    for i in xrange(n):
        fir += (i+1) * (n-i)*x[i]
    for i in xrange(m):
        sec += (i+1) * (m-i) * y[i]
    mod = 10**9 + 7
    print (fir * sec)%mod

Submission status: Runtime Error

Solution code:
import itertools
import math

nm = str(input()).split(' ')
xAry = str(input()).split(' ')
yAry = str(input()).split(' ')

result = 0

nRange = range(int(nm[0]))
mRange = range(int(nm[1]))
nList = itertools.combinations(nRange,2)
mList = itertools.combinations(mRange,2)

for n in nList:
    for m in mList:
        result += (int(xAr[n[1]]) - int(xAry[n[0]])) * (int(yAry[m[1]]) - int(yAry[m[0]]))

'''
for ms in range(int(nm[1])-1):
    for me in range(ms+1,int(nm[1])):
        for ns in range(int(nm[0])-1):
            for ne in range(ns+1,int(nm[0])):
                #print('%s,%s,%s,%s'%(ms,me,ns,ne))
                result += (int(yAry[me])-int(yAry[ms]))*(int(xAry[ne])-int(xAry[ns]))
'''

result %= 1000000007

print(result)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from numpy import array, matrix
N, M = [int(n) - 1 for n in input().split()]
pre_x_ = array([int(n) for n in input().split()])
pre_y_ = array([int(n) for n in input().split()])

x_ = pre_x_[1:N+1] - pre_x_[0:N]
y_ = pre_y_[1:M+1] - pre_y_[0:M]

x_length_arr = np.zeros(int(N * (N+1)/2))
y_length_arr = np.zeros(int(M * (M+1)/2))

x_past_sets = np.zeros(N)
y_past_sets = np.zeros(M)

for n in range(N):
    x_past_sets += array([x_[n]]*(n+1) + [0] * (N-n-1))
    x_length_arr[int(n*(n+1)/2):int((n+1)*(n+2)/2)] = x_past_sets[0:n+1]

for m in range(M):
    y_past_sets += array([y_[m]]*(m+1) + [0] * (M-m-1))
    y_length_arr[int(m*(m+1)/2):int((m+1)*(m+2)/2)] = y_past_sets[0:m+1]

x_length_mat = matrix(x_length_arr)
y_length_mat = matrix(y_length_arr)

print(int((y_length_mat.T.dot(x_length_mat)).sum())%(10**9+7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from numpy import array, matrix
N, M = [int(n) - 1 for n in input().split()]
pre_x_ = array([int(n) for n in input().split()])
pre_y_ = array([int(n) for n in input().split()])

x_ = pre_x_[1:N+1] - pre_x_[0:N]
y_ = pre_y_[1:M+1] - pre_y_[0:M]

x_length_arr = np.zeros(int(N * (N+1)/2))
y_length_arr = np.zeros(int(M * (M+1)/2))

x_past_sets = np.zeros(N)
y_past_sets = np.zeros(M)

for n in range(N):
    x_past_sets += array([x_[n]]*(n+1) + [0] * (N-n-1))
    x_length_arr[int(n*(n+1)/2):int((n+1)*(n+2)/2)] = x_past_sets[0:n+1]

for m in range(M):
    y_past_sets += array([y_[m]]*(m+1) + [0] * (M-m-1))
    y_length_arr[int(m*(m+1)/2):int((m+1)*(m+2)/2)] = y_past_sets[0:m+1]

x_length_mat = matrix(x_length_arr)
y_length_mat = matrix(y_length_arr)

print(int((y_length_mat.T @ x_length_mat).sum())%(10**9+7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from numpy import array, matrix
N, M = [int(n) - 1 for n in input().split()]
pre_x_ = array([int(n) for n in input().split()])
pre_y_ = array([int(n) for n in input().split()])

x_ = pre_x_[1:N+1] - pre_x_[0:N]
y_ = pre_y_[1:M+1] - pre_y_[0:M]

x_length_arr = np.zeros(int(N * (N+1)/2))
y_length_arr = np.zeros(int(M * (M+1)/2))

x_past_sets = np.zeros(N)
y_past_sets = np.zeros(M)

for n in range(N):
    x_past_sets += array([x_[n]]*(n+1) + [0] * (N-n-1))
    x_length_arr[int(n*(n+1)/2):int((n+1)*(n+2)/2)] = x_past_sets[0:n+1]

for m in range(M):
    y_past_sets += array([y_[m]]*(m+1) + [0] * (M-m-1))
    y_length_arr[int(m*(m+1)/2):int((m+1)*(m+2)/2)] = y_past_sets[0:m+1]

x_length_mat = matrix(x_length_arr)
y_length_mat = matrix(y_length_arr)

print(int((y_length_mat.T @ x_length_mat).sum()))

Submission status: Runtime Error

Solution code:
n,m=input().split()
x=input().split()
y=input().split()
d=pow(10,9)+7

i=0
k=0
S=0
while i<int(n)-1:
	i+=1
	S+=i*(int(n)-i)*(int(x[i])-int(x[i-1]))*(int(y[int(n)-1])-int(y[0]))
while k<int(m)-1:
	k+=1
	S+=k*(int(m)-k)*(int(y[k])-int(y[k-1]))*(int(x[int(m)-1])-int(x[0]))
A=S%d
print(A)

Submission status: Runtime Error

Solution code:
mod = 1000000007
def partition(number):
    answer = set()
    answer.add((number, ))
    for x in range(1, number):
        for y in partition(number - x):
            answer.add(tuple(sorted((x, ) + y)))
    return answer
p = lambda n: len(partition(n))

n,m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
print((x[n-1]-x[0])*(y[m-1]-y[0])*p(n-1)*p(m-1) % mod)

Submission status: Runtime Error

Solution code:
n, m = map(int, raw_input().split())
x = map(int, raw_input().split())
y = map(int, raw_input().split())

result = 0
for i in range(len(x)):
    for j in range(len(y)):
        for k in range(i + 1, len(x)):
            for l in range(j + 1, len(y)):
                result += abs(x[i] - x[k]) * abs(y[j] - y[l])
        for k in range():

print(result % (10**9 + 7))