Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from math import floor
import sys
from copy import copy
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for test in range(int(input())):
'''
inf = 100000000000000000  # 1e17
mod = 998244353

S = input().strip()
n = int(input())
reverse = False
for operation in range(n):
    data = input().strip()
    if data[0] == "1":
        if reverse is False:
            reverse = True
        else:
            reverse = False
    else:
        f = data[2]
        ele = data[4]
        if (f == "1" and reverse is False) or (f == "2" and reverse == True):
            S = ele + S
        else:
            S = S + ele
#    print(S)
# print(reverse)
if reverse is False:
    print(S)
else:
    print(S[::-1])


### FIXED CODE ###

from math import floor
import sys
from copy import copy

from collections import deque
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for test in range(int(input())):
'''
inf = 100000000000000000  # 1e17
mod = 998244353




S = input().strip()
D = deque(S)


n = int(input())
reverse = False
for operation in range(n):
    data = input().strip()
    if data[0] == "1":
        if reverse is False:
            reverse = True
        else:
            reverse = False
    else:
        f = data[2]
        ele = data[4]
        if (f == "1" and reverse is False) or (f == "2" and reverse == True):
            D.appendleft(ele)
        else:
            D.append(ele)
#    print(S)
# print(reverse)
if reverse is True:
    D.reverse()
# print(*D,end="")
print("".join(D))
### BUGGY CODE ###

s = input()
q = int(input())

d = 1
for i in range(q):
    t = input()
    if t == '1':
        d *= -1
#        print(d)
    else:
        _, f, c = t.split()
        f = int(f)
        if d == 1 and f == 1:
            s = c + s
        elif d == 1 and f == 2:
            s = s + c
        elif d == -1 and f == 1:
            s = s + c[::-1]
        elif d == -1 and f == 2:
            s = c[::-1] + s
#        print(d, f, c, s)

if d == -1:
    s = s[::-1]
print(s)

### FIXED CODE ###

S = input()
n = int(input())

d = 1
S1 = []
S2 = []
for i in range(n):
    Q = list(input().split())
    if Q[0] == '1':
        d *= -1
    else:
        f = Q[1]
        c = Q[2]
        if f == '1':
            if d == 1:
                S1.append(c)
            else:
                S2.append(c)
        else:
            if d == 1:
                S2.append(c)
            else:
                S1.append(c)
if d == 1:
    ans = ''.join(S1[::-1]) + S + ''.join(S2)
else:
    ans = ''.join(S2[::-1]) + S[::-1] + ''.join(S1)

print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import itertools
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right
from collections import Counter


def solve(N: int, L: "List[int]"):
    ans = 0
    L.sort()

    for x in range(N):
        for y in range(N):
            if x==y : continue
            zs = bisect_right(L, max(L[x],L[y]))
            ze = bisect_left(L, L[x]+L[y])            
            cnt = 0
            if(zs <= x <= ze):
                cnt += 1
            if(zs <= y <= ze):
                cnt += 1
            ans += ((ze-zs)-cnt)

    print(ans//2)

    return
 


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

from bisect import bisect_left, bisect_right



def solve(N: int, L: "List[int]"):
    ans = 0
    L.sort()

    for x in range(N):
        for y in range(x+1,N):
            ze = bisect_left(L, L[x]+L[y])            
            ans += (ze-y-1)
            
    print(ans)

    return
 


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
nums = [int(input()) for i in range(n)]
ans = -10000000000

for j in range(n-1, 0, -1):
    for i in range(j-1,-1, -1):
        ans = max(ans, (nums[j] - nums[i]))
print(ans)

### FIXED CODE ###

N = int(input())
R0 = int(input())
R1 = int(input())
max_profit = R1 - R0
min_R = min(R0, R1)

for i in range(N-2):
    R = int(input())
    max_profit = max(max_profit, R - min_R)
    min_R = min(min_R, R)

print(max_profit)
### BUGGY CODE ###

a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]

max_prod = 0
l=[]
for i in range(a[0] - a[1] + 1):
    chunk = b[i:i + a[1]]  # i, i + 1, ..., i + 12 番目の13個の数字を取り出す。
    prod = sum(chunk)# 部分リストのすべての値の和
    if prod>max_prod:
        l=chunk
    max_prod = max(max_prod, prod)  # 最大値更新

ans=0
for i in range(len(l)):
    ans+=(l[i]+1)/2
print(ans)

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
exp=list(map(lambda x: (int(x)+1)/2,input().split()))
l=np.cumsum(exp)
 
ans=l[k-1]
for i in range(0,n-k):
  x=l[i+k]-l[i]
  ans=max(ans,x)
print(ans)
### BUGGY CODE ###

def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
p=L()
size=(n+1)**2+1
ans=[0]*size
for i in range(1,n+1):
    for j in range(1,n+1):
        k=i*(n+1)+j
        ans[k]=min(i-1,j-1,n-i,n-j)
c=[1]*size
di=[-1,1,n+1,-n-1]
def f(k,i):
    if k+i>=size:
        return
    if ans[k]+c[k]<ans[k+i]:
        ans[k+i]-=1
        q.append(k+i)
t=0
for i in p:
    y=i%n
    if y==0:
        y=n
    x=(i+n-1)//n
    k=x*(n+1)+y
    c[k]=0
    t+=ans[k]
    q=[k]
    while q:
        k=q.pop()
        f(k,1)
        f(k,-1)
        f(k,n+1)
        f(k,-n-1)
print(t)

### FIXED CODE ###

def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
n=N()
p=L()
size=(n+1)**2+1
ans=[0]*size
for i in range(1,n+1):
    for j in range(1,n+1):
        k=i*(n+1)+j
        ans[k]=min(i-1,j-1,n-i,n-j)
c=[1]*size
di=[-1,1,n+1,-n-1]
def f(k,i):
    if k+i>=size:
        return
    if ans[k]+c[k]<ans[k+i]:
        ans[k+i]-=1
        q.append(k+i)
t=0
for i in p:
    y=i%n
    if y==0:
        y=n
    x=(i+n-1)//n
    k=x*(n+1)+y
    c[k]=0
    t+=ans[k]
    q=[k]
    while q:
        k=q.pop()
        f(k,1)
        f(k,-1)
        f(k,n+1)
        f(k,-n-1)
print(t)
### BUGGY CODE ###

nums = [1, 1]
def step_div(n):
	i = len(nums)
	while i <= n:
		nums.append(nums[i-1] * i)
		i += 1
	return nums[n]

n, m = map(int, input().split(" "))

remain = abs(n-m)
if remain <= 1:
	print((step_div(n) * step_div(m) * (2 if remain==0 else 1)) % (10**9+7))
else:
	print(0)

### FIXED CODE ###

import math

n, m = map(int, input().split(" "))

remain = abs(n-m)
if remain <= 1:
	print((math.factorial(n) * math.factorial(m) * (2 if remain==0 else 1)) % (10**9+7))
else:
	print(0)
### BUGGY CODE ###

from itertools import product
 
x1 = int(input())
x2 = input()
 
R = [i for i, x in enumerate(x2) if x == "R"]
G = [i for i, x in enumerate(x2) if x == "G"]
B = [i for i, x in enumerate(x2) if x == "B"]
 
group = map(sorted, product(R, G, B))
voter = [(i[1] - i[0]) != (i[2] - i[1]) for i in group]
print(sum(voter))

### FIXED CODE ###

from itertools import product

x1 = int(input())
x2 = input()

R_i = [i for i, x in enumerate(x2) if x == "R"]
G_i = [i for i, x in enumerate(x2) if x == "G"]
B_i = {i for i, x in enumerate(x2) if x == "B"}

R = len(R_i)
G = len(G_i)
B = len(B_i)

xs = map(sorted, product(R_i, G_i))

s = 0
for a in xs:
    k = a[1]*2 - a[0]  # 2j-i
    if k in B_i:
        s +=1
    i = a[0]*2 - a[1]  # 2j-k
    if i in B_i:
        s +=1
    j = (a[0] + a[1]) / 2
    if j.is_integer():
        j = int(j)
        if j in B_i:
            s +=1
print(R*G*B - s)
### BUGGY CODE ###

a = list(map(int,input().split()))
n = a[0]
m = a[1]

if m != 0:
  ab = [map(int, input().split()) for _ in range(m)]
  a, b = [list(i) for i in zip(*ab)]
  set_list = [{a[0],b[0]}]
  for i in range(1,m):
    flag = 0
    for j in range(len(set_list)):
      if a[i] in set_list[j] or b[i] in set_list[j]:
        set_list[j].add(a[i])
        set_list[j].add(b[i])
        flag = 1
        break
    if flag == 0:
      set_list.append({a[i],b[i]})

  #print(set_list)

  ans = 1
  for i in range(len(set_list)):
    ans = max(ans, len(set_list[i]))

  print(ans)
else:
  print(1)

### FIXED CODE ###

n, m = [int(x) for x in input().split()]

if m != 0:
  g = [set() for _ in range(n)]
  valid = [-1] * n
  set_list = []
  for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a-1].add(b-1)
    g[b-1].add(a-1)

  j = -1
  for i in range(n):
    if valid[i] == -1:
      set_list.append(set())
      j += 1
      stack = [i]
      while len(stack)!=0:
        v = stack.pop()
        set_list[j].add(v)
        valid[v] = 1
        for i in g[v]:
          if valid[i] == -1:
            stack.append(i)
            set_list[j].add(i)
            valid[i] = 1
  ans = 1
  for i in range(len(set_list)):
    ans = max(len(set_list[i]),ans)

  print(ans)

else:
  print(1)
### BUGGY CODE ###

def solve():
    n, q = map(int, input().split())
    s = input()
    lrs = list(list(map(int, input().split())) for _ in range(q))
    ans = [s[l - 1:r].count("AC") for l, r in lrs]
    print(*ans, sep="\n")


if __name__ == "__main__":
    solve()


### FIXED CODE ###

def solve():
    n, q = map(int, input().split())
    s = input()
    lrs = list(list(map(int, input().split())) for _ in range(q))
    # ans = [s[l - 1:r].count("AC") for l, r in lrs]
    c = [0] * n
    for i in range(1, n):
        c[i] = c[i - 1]
        if s[i - 1] == "A" and s[i] == "C":
            c[i] += 1
    ans = [c[r - 1] - c[l - 1] for l, r in lrs]
    print(*ans, sep="\n")


if __name__ == "__main__":
    solve()
### BUGGY CODE ###

def main():
    
    N,W = map(int,input().split())
    wa = []
    va = []
    for i in range(N):
        w,v = map(int,input().split())
        wa.append(w)
        va.append(v)
    dp = [[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            if j-wa[i] >= 0:
                dp[i+1][j] = max(dp[i][j],dp[i][j-wa[i]]+va[i])
            else:
                dp[i+1][j] = dp[i][j]

    print(dp[-1][-1])
main()

### FIXED CODE ###

N,W = map(int,input().split())
array = []
for i in range(N):
    wv = list(map(int,input().split()))
    array.append(wv)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j-array[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j-array[i][0]]+array[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][-1])
### BUGGY CODE ###

import queue
MAX = 10 ** 10
def m():
    def dijkstra(ds, start):
        q = queue.PriorityQueue()
        visited = []
        for to, cost in graph[start]:
            q.put((cost, to))
        visited.append(start)
        while not q.empty():
            cost, to = q.get()
            if to in visited: continue
            if cost == MAX: continue
            visited.append(to)
            ds[start][to] = cost
            for k, cost in graph[to]:
                if (k in visited) == False:
                    q.put((cost + ds[start][to], k))
        return ds

    n = int(input())
    graph = [[] for _ in range(n+1)]
    for _ in range(1,n):
        a, b, c = map(int, input().split())
        graph[a].append((b,c))
        graph[b].append((a,c))

    q, k = map(int, input().split())
    ds = [[MAX for _ in range(n+1)] for _ in range(n+1)]
    for i in range(n+1): ds[i][i] = 0
    ds = dijkstra(ds, k)
    for _ in range(q):
        x, y = map(int, input().split())
        ds = dijkstra(ds, x)
        print(ds[x][k] + ds[k][y])

m()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
 
def ans():
    def dfs(v, p, d):
        depth[v] = d
        for e, cost in tree[v]:
            if e == p:
                continue
            dfs(e, v, d + cost)
 
    n = int(input())
    tree = [[] for _ in range(n + 1)]
    depth = [0] * (n * 2)
    for _ in range(1, n):
        a, b, c = map(int, input().split())
        tree[a].append((b, c))
        tree[b].append((a, c))
 
    q, k = map(int, input().split())
    dfs(k, -1, 0)
    for _ in range(q):
        x, y = map(int, input().split())
        print(depth[x] + depth[y])
 
 
ans()
### BUGGY CODE ###

import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def reset(self):
        for i in range(len(self.tree)):
            self.tree[i] = 0

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
comb = N*(N+1) // 2

bit = Bit(2*N+1)
def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    if lft >= half:
        return half
    summed = 0
    res = 0
    bit.reset()
    bit.add(N, 1)
    for x in inarr:
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    if res >= math.ceil(comb/2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

res = binsearch(0, N)
print(sorted_in[res])


### FIXED CODE ###

import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

get_ints = lambda: [int(st) for st in input().split()]
N=int(input())
inarr=get_ints()

sorted_in = sorted(inarr)
# print(sorted_in)
comb = N*(N+1) // 2

def binsearch(lft, rgt):
    half = (lft + rgt) // 2
    # print("investigate: lft {} rgt {} half {} value {}".format(lft, rgt, half, sorted_in[half]))
    if lft >= half:
        return half
    summed = 0
    res = 0

    bit = Bit(2*N+1)
    bit.add(N, 1)
    for i, x in enumerate(inarr):
        value = 1 if x >= sorted_in[half] else -1
        summed += value
        # print("summed: {}, bit: {}".format(summed, bit.sum(N + summed)))
        count = bit.sum(N + summed)
        bit.add(N + summed, 1)
        res += count

    # print("num {} cnt {} judge {}".format(sorted_in[half], res, math.ceil(comb/2)))
    if res >= math.ceil(comb/2):
        return binsearch(half, rgt)
    else:
        return binsearch(lft, half)

# print(sorted_in)
res = binsearch(0, N)
# print(res, sorted_in[res])
print(sorted_in[res])
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
t = input()
s_idx = ["a"]*26
t_idx = ["a"]*26
for i in range(len(s)):
    s_idx[ord(s[i])-97] += str(i)
for i in range(len(s)):
    t_idx[ord(t[i])-97] += str(i)
for i in range(26):
    if s_idx[i] in t_idx:
        continue
    else:
        print("No")
        exit()
#print(s_idx,t_idx)
print("Yes")

### FIXED CODE ###

#!/usr/bin/env python3
s = input()
t = input()
s_idx = [[] for _ in range(26)]
t_idx = [[] for _ in range(26)]
for i in range(len(s)):
    s_idx[ord(s[i])-97].append(i)
visit = []
for i in range(26):
    cnt = 0
    for j in s_idx[i]:
        if cnt == 0 and t[j] in visit:
            print("No")
            exit()
        if cnt == 0:
            visit.append(t[j])
            cnt += 1
        else:
            if t[j] != visit[-1]:
                print("No")
                exit()
print("Yes")
### BUGGY CODE ###

import itertools
import copy
N=input()
a=[]
a=map(int, raw_input().split())
#print N
#print a

n_l=[ i for i in range(len(a))]
#print n_l
c = list(itertools.combinations(n_l,N))
#c=[(3,1)]
#print c

score=0.1
for i in c:
	a_t=copy.deepcopy(a)
	#print "#Loop start"
	#print i
	for j in range(N):
		a_t.pop(i[j]-j)
	#print a_t
	a1=zip(*[iter(a_t)]*N)
	#print a1
	if score==0.1 or score<sum(a1[0])-sum(a1[1]):
		score=sum(a1[0])-sum(a1[1])
		#print "score::"+str(score)

print score

### FIXED CODE ###

import itertools
from heapq import heapify,heappush,heappop

N=input()
a=[]
a=map(int, raw_input().split())
a1=a[0:N]
#print a1

heapify(a1)

l1=[]
sum_a1=sum(a1)
l1.append(sum_a1)

# Max
for i in range(N,2*N):
	if a[i]>a1[0]:
		sum_a1=sum_a1+a[i]-a1[0]
		heappop(a1)
		heappush(a1, a[i])

	l1.append(sum_a1)


l2=[]
a2=[ -x for x in a[2*N:3*N]]
heapify(a2)
sum_a2=-1*sum(a2)
l2.append(sum_a2)

# Min
for i in reversed(range(N,2*N)):
	if a[i]<-1*a2[0]:
		sum_a2=sum_a2+a[i]-(-1*a2[0])
		heappop(a2)
		heappush(a2,-1*a[i])
	l2.append(sum_a2)


ans=[]
for i in range(N+1):
	ans.append(l1[i]-l2[N-i])

print max(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
favor = [tuple(input().split()) for _ in range(n)]
square = [[0 for _ in range(k)] for _ in range(k)]
initscore = 0
for xc, yc, c in favor:
    x = int(xc)
    y = int(yc)
    x %= 2*k
    y %= 2*k
    if (x in range(k) and y in range(k)) or (x in range(k, 2*k) and y in range(k, 2*k)):
        if c == 'B':
            square[x%k][y%k] += 1
        else:
            square[x%k][y%k] -= 1
            initscore += 1
    else:
        if c == 'B':
            square[x%k][y%k] -= 1
            initscore += 1
        else:
            square[x%k][y%k] += 1
cum = [[0 for _ in range(k+1)] for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + square[i][j]
maxscore = 0
for i in range(k):
    for j in range(k):
        score1 = 2*cum[i][j] + cum[k][k] - cum[i][k] - cum[k][j]
        score2 = cum[k][k] - score1
        maxscore = max(maxscore, initscore + max(score1, score2))
print(maxscore)

### FIXED CODE ###

n, k = map(int, input().split())
favor = [tuple(input().split()) for _ in range(n)]
square = [[0 for _ in range(k)] for _ in range(k)]
initscore = 0
for xc, yc, c in favor:
    x = int(xc)
    y = int(yc)
    x %= 2*k
    y %= 2*k
    if (x in range(k) and y in range(k)) or (x in range(k, 2*k) and y in range(k, 2*k)):
        if c == 'B':
            square[x%k][y%k] += 1
        else:
            square[x%k][y%k] -= 1
            initscore += 1
    else:
        if c == 'B':
            square[x%k][y%k] -= 1
            initscore += 1
        else:
            square[x%k][y%k] += 1
cum = [[0 for _ in range(k+1)] for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + square[i][j]
maxscore = 0
for i in range(k):
    for j in range(k):
        score = cum[i][k] + cum[k][j] - 2*cum[i][j]
        maxscore = max(maxscore, max(cum[k][k] - score, score))
print(maxscore + initscore)
### BUGGY CODE ###

import sys
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[2147483647]*(n+1)
h.insert(0,0)
dp[0]=0
dp[1]=0
dp[2]=abs(h[2]-h[1])
for i in range(3,n+1):
    for j in range(i-1,max((i-k-1),0),-1):
        dp[i]=min(dp[i],abs(h[i]-h[j])+dp[j])
print(dp[n])



### FIXED CODE ###

import sys
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[2147483647]*(n+1)
h.insert(0,0)
dp[0]=0
dp[1]=0
dp[2]=abs(h[2]-h[1])
for i in range(3,n+1):
    for j in range(i-1,max((i-k-1),0),-1):
        dp[i]=min(dp[i],abs(h[i]-h[j])+dp[j])
print(dp[n])
### BUGGY CODE ###

n = int(input())
for bit in range(1<<n):
  sum = 0
  for i in range(n):
    if bit & (1<<i):
      sum += i+1
      
  if sum == n:
    a = bin(bit)
    break
s = str(a)
s = s[2:]
s = s[::-1]


for i in range(len(s)):
  if s[i] == '1':
    print(i + 1)

### FIXED CODE ###

n = int(input())

aa =[]
i = 0
score = 0

while score < n:
  i += 1
  score += i
  aa.append(i)
  
if score == n:
  for k in range(len(aa)):
    print(aa[k])
    
else:
  aa.remove(score - n)
  for k in range(len(aa)):
    print(aa[k])
### BUGGY CODE ###

import numpy as np
from collections import Counter

N = int(input())
X = list(map(int, input().split()))

for i in range(N):
    print(np.median(X[:i] + X[i+1:]).astype(int))

### FIXED CODE ###

import numpy as np

N = int(input())
X = list(map(int, input().split()))
Xs = sorted(X)
c1 = np.median(Xs[1:]).astype(int)
c2 = np.median(Xs[:-1]).astype(int)

for i in range(N):
    if X[i] < c1:
        print(c1)
    else:
        print(c2)
### BUGGY CODE ###

from collections import Counter
s=input()[::-1]
m=len(s)
DP=[0]
word=""

for i in s:
    word=i+word
    DP.append(int(word)%2019)

DP=Counter(DP)
ans=0
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)

### FIXED CODE ###

from collections import Counter
s=input()[::-1]
DP=[0]

num,point=0,1
for i in s:
    num +=int(i)*point
    num %=2019
    DP.append(num)
    point *=10
    point %=2019

ans=0
DP=Counter(DP)
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

N = int(input())
A = list(map(int,input().split()))
ans = 1
for i in A:
    ans *= i
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

N = int(input())
A = list(map(int,input().split()))
ans = 1
if 0 in A:
    print(0)
    exit()
else:
    for i in A:
        ans *= i
        if ans > 10**18:
            print(-1)
            exit()
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p_list = list(map(int, input().split()))
e_list = [(p+1)/2 for p in p_list]
max_nums = 0
max_targets = []
for j in range(0, len(e_list)-k+1):
  targets = [e_list[j+m] for m in range(k)]
  t_sum = sum(targets)
  if t_sum >= max_nums:
    max_nums = t_sum
    max_targets = targets
print(sum(max_targets))

### FIXED CODE ###

n, k = map(int, input().split())
p_list = list(map(int, input().split()))
tmp = sum(p_list[:k])
max_num = sum(p_list[:k])
for i in range(len(p_list)-k):
  tmp = tmp - p_list[i] + p_list[i+k]
  if tmp >= max_num:
    max_num = tmp
print((max_num+k)/2)
### BUGGY CODE ###

import sys
s = input()
t = input()
for c in set(t):
  if s.find(c) == -1:
    print(-1)
    sys.exit()
p = 0
slen = len(s)
for i in range(1, 10 ** 5 + 1):
  for j in range(slen):
    if s[j] == t[p]:
      p += 1
      if p == len(t):
        print((i - 1) * slen + j + 1)
        sys.exit()

### FIXED CODE ###

s=input()
t=input()
ans=0
s1=s
ans=0
flag=1
for i in t:
    if i not in s1:
        flag=0
if flag==0:
    print(-1)
else:
    for i in t:
        if i in s1:
            ans+=s1.index(i)+1
            s1=s1[s1.index(i)+1:]
        else:
            ans = ((ans+len(s)-1)//len(s))*len(s) 
            ans+=s.index(i)+1   
            s1=s[s.index(i)+1:]
    print(ans)
### BUGGY CODE ###

nm = input().split()
n = int(nm[0])
m = int(nm[1])
X = input().split()
Y = input().split()
S = 0
for i in range(n):
	for j in range(n - i):
		for k in range(m):
			for l in range(m - k):
				S += (int(X[i + j]) - int(X[i])) * (int(Y[k + l]) - int(Y[k]))
ans = S % 1000000007
print(ans)

### FIXED CODE ###

#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M = getlist()
	x = getlist()
	y = getlist()
	X = 0
	Y = 0
	for i in range(N - 1):
		X += ((x[i + 1] - x[i]) * (i + 1) * (N - i - 1)) % con
		X %= con
	for i in range(M - 1):
		Y += ((y[i + 1] - y[i]) * (i + 1) * (M - i - 1)) % con
		Y %= con
	print(X * Y % con)


if __name__ == '__main__':
	main()