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

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    A = list(map(int,input().split()))
    B = [0] * n
    for i in range(n):
        x = 0
        for j in range(n):
            if j == i:
                continue
            x ^= A[j]
        B[i] = x
    print(" ".join(map(str,B)))


if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    A = list(map(int,input().split()))
    B = [0] * n
    x = 0
    for a in A:
        x ^= a
    for i in range(n):
        B[i] = x^A[i]
    print(" ".join(map(str,B)))


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

s = input()
q = int(input())
back = 1
for i in range(q):
    query = input().split()
    if query[0] == '1':
        back *= -1
    else:
        if query[1] == '1':
            if back == 1:
                s = ('').join(query[2:]) + s
            else:
                s = s + ('').join(query[2:])
        else:
            if back == 1:
                s = s + ('').join(query[2:])
            else:
                s = ('').join(query[2:]) + s
if back == -1:
    s = s[-1::-1]
print(s)

### FIXED CODE ###

import collections
s = input()
q = int(input())
back = 1
t = collections.deque()
for ss in s:
    t.append(ss)
for i in range(q):
    query = input().split()
    if query[0] == '1':
        back *= -1
    else:
        if query[1] == '1':
            if back == 1:
                t.appendleft(query[2])
            else:
                t.append(query[2])
        else:
            if back == 1:
                t.append(query[2])
            else:
                t.appendleft(query[2])
ans = ''
if back == -1:
    for i in range(len(t)):
        ans += t.pop()
else:
    for i in range(len(t)):
        ans += t.popleft()
print(ans)
### BUGGY CODE ###

N = int(input())
words = [input() for i in range(N)]

word = list(set(words))
counter = list()
dict = {}

for a in word:
    dict[a] = words.count(a)

max = max(dict.values())

for a in word:
    if dict[a] == max:
        continue
    else:
        del dict[a]

dict2 = sorted(dict.keys())

for a in dict2:
    print(a)

### FIXED CODE ###

N = int(input())
words = [input() for i in range(N)]

from collections import Counter

word = list(set(words))

dict = Counter(words)

max = max(dict.values())

for a in word:
    if dict[a] == max:
        continue
    else:
        del dict[a]

dict2 = sorted(dict.keys())

for a in dict2:
    print(a)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
num = []
for Q in range(q):
	l,r = map(int,input().split())
	print(s[l - 1:r].count('AC'))

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
r = [0 for n in range(N)]
l = [0 for n in range(N)]
cnt = 0
for s in range(N - 1):
	if S[s] == 'A':
		if S[s + 1] == 'C':
			cnt += 1
	l[s + 1] = cnt
cnt = 0
for s in range(1,N):
	if S[-s] == 'C':
		if S[-s - 1] == 'A':
			cnt += 1
	r[-s - 1] = cnt
for q in range(Q):
	L,R = map(int,input().split())
	print(cnt - l[L - 1] - r[R - 1])
### BUGGY CODE ###

from collections import Counter
mod = 10**9+7
s = input()
q = 0
a = 0
ab = 0
abc = 0
for c in s:
    k = pow(3, q)%mod
    if c == "A":
        a += k
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = 3*abc + ab
        ab = 3*ab + a
        a = 3*a + k
        q += 1
    a %= mod
    ab %= mod
    abc %= mod
print(abc%mod)



### FIXED CODE ###

from collections import Counter
mod = 10**9+7
s = input()
k = 1
a = 0
ab = 0
abc = 0
for c in s:
    if c == "A":
        a += k
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = 3*abc + ab
        ab = 3*ab + a
        a = 3*a + k
        k *= 3
    a %= mod
    ab %= mod
    abc %= mod
    k %= mod
print(abc%mod)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
mod = 10**9 + 7

dp = [0]*(n+1)
dp[0] = 1
    
for i in range(1,n+1):
    if i in a:
        continue
    dp[i] = dp[i-1] 
    if i > 1:
        dp[i] += dp[i-2]
ans = dp[n] % mod
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
a = {int(input()) for _ in range(m)}
mod = 10**9 + 7

dp = [0]*(n+1)
dp[0] = 1
    
for i in range(1,n+1):
    if i in a:
        continue
    x = dp[i-1] 
    if i > 1:
        x += dp[i-2]
    dp[i] = x % mod
ans = dp[n]
print(ans)
### BUGGY CODE ###

N = int(input())
l = [int(x) for x in input().split()]

L = sorted(l,reverse=True)
a = 0

for x in range(0,N-2):
  for y in range(x+1,N-1):
	   for i in range(y+1,N):
	       if L[i] > L[x] - L[y]:
	           a += 1
print(a)

### FIXED CODE ###

N = int(input())
l = [int(x) for x in input().split()]
l.sort(reverse=True)
 
ans = 0
 
for i in range(N-2):
  j = i + 1
  k = N - 1
  while j < k:
    if l[i] < l[j] + l[k]:
      ans += k - j
      j += 1
    else:
      k -= 1
print(ans)
### BUGGY CODE ###

n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    for f in fl:
        if i+1 in f:
            isContinue = True
            break
    if isContinue:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        for nf in p[r-1]['T']:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    l = [i+1]+ dt['T'] + dt['B']
    for f in fl:
        if i+1 in f:
            ans[i] = len([x for x in f if not x in l])
            break
            

print(' '.join(map(str, ans)))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M,K = map(int,input().split())
    friend = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)
        
    brock = [[] for _ in range(N)]
    for _ in range(K):
        c,d = map(int,input().split())
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
    parent = [-1 for _ in range(N)]
    group = [0 for _ in range(N)]
    
    for i in range(N):
        put = []
        if parent[i] == -1:
            q = deque([i])
            parent[i] = i
            while q:
                now = q.pop()
                put.append(now)
                for fol in friend[now]:
                    if parent[fol] == -1:
                        parent[fol] = i
                        q.append(fol)
            l = len(put)
            for num in put:
                group[num] = l-1
                
        else:
            continue

    for i in range(N):
        group[i] -= len(friend[i])
        for dis in brock[i]:
            if parent[i] == parent[dis]:
                group[i] -= 1
    
    print(*group)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math

n = int(input())

for i in range(1, n + 1):
    cnt = 0
    t = math.floor(i - (i ** 0.5)) + 1
    for j in range(1, t):
        for k in range(1, t):
            for l in range(1, t):
                if ((j ** 2) + (k ** 2) + (l ** 2) + (j * k) + (k * l) + (l * j)) == i:
                    cnt += 1
    print(cnt)

### FIXED CODE ###

n = int(input())
ans = [0] * 10000

for i in range(1, 101):
    for j in range(1, 101):
        for k in range(1, 101):
            m = ((i ** 2) + (j ** 2) + (k ** 2) + (i * j) + (j * k) + (k * i))
            if m < 10001:
                ans[m-1] += 1

for i in range(n):
    print(ans[i])
### BUGGY CODE ###

N, Q = map(int, input().split())
const = [list(map(int, input().split())) for _ in range(N)]
const = sorted(const, key=lambda x: x[2])
for _ in range(Q):
    d = int(input())
    for s, t, x in const:
        if s <= x+d <t:
            print(x)
            break
    else:
        print(-1)

### FIXED CODE ###

from bisect import bisect_left
N, Q = map(int, input().split())
consts = []
for _ in range(N):
    s,t,x = map(int, input().split())
    consts.append((x,s,t))
consts.sort()
D=[int(input()) for _ in range(Q)]
ans=[-1]*Q
jump=[-1]*Q
for x,s,t in consts:
    left=bisect_left(D,s-x)
    right=bisect_left(D,t-x)
    while left<right:
        if jump[left]==-1:
            ans[left]=x
            jump[left]=right
            left += 1
        else:
            left=jump[left]
print(*ans, sep='\n')
### BUGGY CODE ###

import sys
import numpy as np
import math
def input():
    return sys.stdin.readline()[:-1]

N, M = map(int, input().split())

A = list(map(int, input().split()))

for _ in range(M):
    A[np.argmax(A)] = math.floor(max(A) / 2)

print(sum(A))

### FIXED CODE ###

import sys
import numpy as np
import math
import heapq
def input():
    return sys.stdin.readline()[:-1]

N, M = map(int, input().split())
A = list(map(lambda a: int(a)*(-1), input().split()))
heapq.heapify(A)

for _ in range(M):
    heapq.heappush(A, math.trunc(heapq.heappop(A) / 2))

print(sum(A)*(-1))
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

s = []
for _ in range(h):
    s.append(input())

mtx = [[10 ** 9]*w for _ in range(h)]

cnt = -1
now = deque()
nxt = deque()
nxt.append((ch, cw))
mtx[ch][cw] = 0

while True:
    if not now:
        now = nxt
        cnt += 1
        nxt = deque()
        if not now:
            break
    h_ptr, w_ptr = now.pop()
    if h_ptr != 0:
        if s[h_ptr-1][w_ptr] == '.':
            if cnt < mtx[h_ptr-1][w_ptr]:
                mtx[h_ptr-1][w_ptr] = cnt
                now.append((h_ptr-1, w_ptr))
    if w_ptr != 0:
        if s[h_ptr][w_ptr-1] == '.':
            if cnt < mtx[h_ptr][w_ptr-1]:
                mtx[h_ptr][w_ptr-1] = cnt
                now.append((h_ptr, w_ptr-1))
    if h_ptr != h-1:
        if s[h_ptr+1][w_ptr] == '.':
            if cnt < mtx[h_ptr+1][w_ptr]:
                mtx[h_ptr+1][w_ptr] = cnt
                now.append((h_ptr+1, w_ptr))
    if w_ptr != w-1:
        if s[h_ptr][w_ptr+1] == '.':
            if cnt < mtx[h_ptr][w_ptr+1]:
                mtx[h_ptr][w_ptr+1] = cnt
                now.append((h_ptr, w_ptr+1))
    for i in range(h_ptr-2, h_ptr+3):
        for j in range(w_ptr-2, w_ptr+3):
            if 0 <= i < h and 0 <= j < w and s[i][j] == '.':
                if cnt + 1 < mtx[i][j]:
                    mtx[i][j] = cnt + 1
                    nxt.append((i, j))

ret = mtx[dh][dw]

if ret == 10 ** 9:
    print(-1)
else:
    print(ret)


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

s = []
for _ in range(h):
    s.append(input())

mtx = [[10 ** 9]*w for _ in range(h)]

cnt = -1
now = deque()
nxt = deque()
nxt.append((ch, cw))
mtx[ch][cw] = 0

while True:
    flag = False
    if not now:
        now = nxt
        cnt += 1
        nxt = deque()
        if not now:
            break
    h_ptr, w_ptr = now.pop()
    if h_ptr != 0:
        if s[h_ptr-1][w_ptr] == '.':
            if cnt < mtx[h_ptr-1][w_ptr]:
                mtx[h_ptr-1][w_ptr] = cnt
                now.append((h_ptr-1, w_ptr))
    if w_ptr != 0:
        if s[h_ptr][w_ptr-1] == '.':
            if cnt < mtx[h_ptr][w_ptr-1]:
                mtx[h_ptr][w_ptr-1] = cnt
                now.append((h_ptr, w_ptr-1))
    if h_ptr != h-1:
        if s[h_ptr+1][w_ptr] == '.':
            if cnt < mtx[h_ptr+1][w_ptr]:
                mtx[h_ptr+1][w_ptr] = cnt
                now.append((h_ptr+1, w_ptr))
    if w_ptr != w-1:
        if s[h_ptr][w_ptr+1] == '.':
            if cnt < mtx[h_ptr][w_ptr+1]:
                mtx[h_ptr][w_ptr+1] = cnt
                now.append((h_ptr, w_ptr+1))
    for i in range(h_ptr-2, h_ptr+3):
        for j in range(w_ptr-2, w_ptr+3):
            if 0 <= i < h and 0 <= j < w and s[i][j] == '.':
                if cnt + 1 < mtx[i][j]:
                    mtx[i][j] = cnt + 1
                    nxt.append((i, j))

ret = mtx[dh][dw]

if ret == 10 ** 9:
    print(-1)
else:
    print(ret)
### BUGGY CODE ###

from heapq import heappush, heappop

line = input()
v, e = list(map(int, line.split()))
edge = []
for _ in range(0, e):
    line = input()
    s, t, w = list(map(int, line.split()))
    edge += [[s, t, w]]

def solve(v, edge):
    q = []
    vtx = set([i for i in range(0, v)])
    for s, t, w in edge:
        heappush(q, (w, (s, t)))
    vn = set([0])
    en = []
    cost = 0
    while vn != vtx:
        w = s = t = 0
        qq = []
        while q:
            w, st = heappop(q)
            s, t = st
            if s in vn and t not in vn:
                break
            if s not in vn and t in vn:
                s, t = t, s
                break
            qq += [[s, t, w]]
        for s, t, w in qq:
            heappush(q, (w, (s, t)))
        vn.add(t)
        en += [(s, t)]
        cost += w
    return cost
        
print(solve(v, edge))


### FIXED CODE ###

from heapq import heappush, heappop

line = input()
v, e = list(map(int, line.split()))
edge = {}
edge[0] = [[0, 0]]
for _ in range(0, e):
    line = input()
    s, t, w = list(map(int, line.split()))
    if s not in edge:
        edge[s]  = [[t, w]]
    else:
        edge[s] += [[t, w]]
    if t not in edge:
        edge[t]  = [[s, w]]
    else:
        edge[t] += [[s, w]]

def solve(v, edge):
    q = []
    vtx = set([i for i in range(0, v)])
    for t, w in edge[0]:
        heappush(q, (w, 0, t))
    vn = set([0])
    en = []
    cost = 0
    while len(vn) < v:
        w = s = t = 0
        qq = []
        while q:
            w, s, t = heappop(q)
            if s in vn and t not in vn:
                s, t = t, s
                break
            if s not in vn and t in vn:
                break
        vn.add(s)
        en += [(s, t)]
        cost += w
        for t, w in edge[s]:
            heappush(q, (w, s, t))
    return cost
        
print(solve(v, edge))
### BUGGY CODE ###

N,M = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]
for i in range(N):
    H[i] = H[i]%M
SumH = [0 for i in range(N+1)] 
for i in range(1,N+1):
    SumH[i] = (SumH[i-1]+H[i-1])%M
Ctr = [-1 for i in range(N+1)]
Ans = [0 for i in range(N+1)]
for i in range(N+1):
    if SumH[i] in Ctr:
        continue
    Ctr[i] = SumH[i]
    Ans[i] = (SumH.count(SumH[i]))
for i in range(N+1):
    Ans[i] = Ans[i]*(Ans[i]-1)//2
print(sum(Ans))

### FIXED CODE ###

def inpl(): return [int(i) for i in input().split()]

N,M = inpl()
H = {0: 1}
k = 0
ans = 0
for i in inpl():
    k += i
    t = k % M
    if t not in H:
        H[t] = 0
    H[t] += 1
    
for i in H.values():
   ans += i * (i - 1) // 2

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys

sys.setrecursionlimit(int(1e5))


def lcs(A, B):
    m, n = len(A), len(B)
    dp = tuple([[0] * (n + 1) for _ in range(m + 1)])
    max_l = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            max_l = max(max_l, dp[i][j])

    return max_l


def lcs_recursive(A, B, m, n):
    if m == 0 or n == 0:
        return 0
    elif A[m - 1] == B[n - 1]:
        return 1 + lcs_recursive(A, B, m - 1, n - 1)
    else:
        return max(lcs_recursive(A, B, m, n - 1), lcs_recursive(A, B, m - 1, n))


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    # for k in range(0, len(word_list), 2):
    #     print(lcs(word_list[k].strip(), word_list[k + 1].strip()))

    for pair in zip(word_list[::2], word_list[1::2]):
        w1, w2 = map(lambda x: x.strip(), pair)
        # l1, l2 = len(w1), len(w2)
        print(lcs(w1, w2))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            elif count_list[i - 1][j] >= count_list[i][j - 1]:
                count_list[i][j] = count_list[i - 1][j]
            else:
                count_list[i][j] = count_list[i][j - 1]

    return count_list[m][n]


def lcs_better(A, B):
    costs = [0]
    for c in B:
        for index in range(len(costs) - 1, -1, -1):
            # print(costs, index + 1)
            x_findex_index = A.find(c, costs[index])
            if x_findex_index != -1:
                if index + 1 < len(costs):
                    costs[index + 1] = min(costs[index + 1], x_findex_index + 1)
                else:
                    costs.append(x_findex_index + 1)
    return len(costs) - 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs_better(word_list[k].strip(), word_list[k + 1].strip()))
### BUGGY CODE ###

K, S = list(map(int, input('').split()))
count = 0
for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x + y + z == S:
      	count += 1
print(count)

### FIXED CODE ###

K, S = list(map(int, input('').split()))
count = 0
for x in range(K+1):
  for y in range(K+1):
    if x + y <= S and x + y + K >= S:
      count += 1
print(count)
### BUGGY CODE ###

import sys

def main():
    A, B = map(int, input().split())

    for i in range(1, 9999900000):
        if(i%A==0 and i%B==0):
            print(i)
            sys.exit()
main()


### FIXED CODE ###

import sys
from fractions import gcd

def main():
    A, B = map(int, input().split())

    print(int(A * B / gcd(A, B)))

main()
### BUGGY CODE ###

n = int(input())
h = list(map(int,input().split()))
submax = 0

for i in range(n-1):
  for j in range(i+1,n):
    if h[i] - h[j] >= 2:
      submax = 1

if submax == 1:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
d = [1]+[0]*(n-1)

for i in range(n-1):
  if h[i] >= 2+ h[i+1]:
    print('No')
    exit()
  if d[i] == 1 and h[i] <= h[i+1]:
    d[i+1] = 1
  elif d[i] == 0:
    if h[i] +1 <=h[i+1]:
      d[i+1] = 1
    elif h[i] -1 == h[i+1]:
      print('No')
      exit()
      
print('Yes')
### BUGGY CODE ###

s = input()
k = int(input())
x = 0
substr = set()
while x < len(s):
    x += 1
    for i in range(len(s) - x + 1):
        if s[i:i+x] not in substr:
            substr.add(s[i:i+x])
substr = list(substr)
substr.sort()
print(substr[k-1])

### FIXED CODE ###

s = input()
k = int(input())
x = 0
substr = set()
while x < k:
    x += 1
    for i in range(len(s) - x + 1):
        if s[i:i+x] not in substr:
            substr.add(s[i:i+x])
substr = list(substr)
substr.sort()
print(substr[k-1])
### BUGGY CODE ###

A, B, C, D = map(int, input().split())
result = 0
size = B - A + 1
for i in range(size):
    if((A + i)%C != 0 and (A + i)%D != 0):
      result += 1
print(result)


### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())
Cdiv = B // C - (A - 1) // C
Ddiv = B // D - (A - 1) // D
gcd_CD = int(C * D / fractions.gcd(C, D))
CDdiv = B // gcd_CD - (A - 1) // gcd_CD
result = int(B - (A - 1) - Cdiv - Ddiv + CDdiv)
print(result)
### BUGGY CODE ###

s = input()
q = int(input())
for _ in range(q):
    t = input().split()
    if t[0]=="1":
        s=s[::-1]
    elif t[0]=="2":
        if t[1]=="1":
            s = t[2]+s
        elif t[1]=="2":
            s = s+t[2]
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
f = False
# Falseだと左が先頭
for _ in range(q):
    t = input().split()
    if t[0]=="1":
        f = not f
    elif t[0]=="2":
        t[2]=list(t[2])
        if f:
            t[2]=t[2][::-1]
            if t[1]=="1":
                s.extend(t[2])
            elif t[1]=="2":
                s.extendleft(t[2])
        else:
            if t[1]=="1":
                s.extendleft(t[2])
            elif t[1]=="2":
                s.extend(t[2])
if f:
    print("".join(s)[::-1])
else:
    print("".join(s))
### BUGGY CODE ###

import itertools

n = int(input())
s = list(input())

ans = 0


for i in range(10):
    for j in range(10):
        for k in range(10):
            flag1 = 0
            flag2 = 0
            
            for l in range(n):
                if flag1 == 0 and s[l] == str(i):
                    flag1 = 1
                    continue
                
                if flag1 == 1 and flag2 == 0 and s[l] == str(j):
                    flag2 = 1
                    continue
                
                if flag1 == 1 and flag2 == 1 and s[l] == str(k):
                    ans += 1
                    break
                
print(ans)


### FIXED CODE ###

n = int(input())
s = list(input())

li = [[] for _ in range(10)]

for i in range(n):
    t = int(s[i])
    li[t].append(i)

a = 0
b = 0
c = 0
cnt = 0

for i in range(10):
  for j in range(10):
    for k in range(10):
      b = 0
      a = 0
      
      if len(li[i]) > 0:
        a = li[i][0]
          
        for d in li[j]:
            if d > a:
                b = d
                break
        else:
            break
        
        for e in li[k]:
            if e > b:
                cnt += 1
                break
        

print(cnt)
### BUGGY CODE ###

def resolve():
    N,M = map(int,input().split())
    LL,RR = [],[]
    for i in range(M):
        L,R = map(int,input().split())
        LL.append(L)
        RR.append(R)

    ans = 0
#    print()
#    print(N,M)
#    print(LL,RR)
    bool_id = [1]*N
#    print(bool_id)
    for i in range(M): #Gate num
#        print(LL[i],RR[i])
        l,r = LL[i]-1,RR[i]
        #bool_id[l:r] = [True]*(r-l)
        bool_id[:l] = [0]*(l)
        bool_id[r:] = [0]*(N-r)
#        print(bool_id)
    print(sum(bool_id))

resolve()


### FIXED CODE ###

def resolve():
    N,M = map(int,input().split())
    LL,RR = [],[]
    for i in range(M):
        L,R = map(int,input().split())
        LL.append(L)
        RR.append(R)

    bool_id = [1]*N
    lmin = -1
    rmax = 10**10
    for i in range(M):
        lmin = max(lmin,LL[i])
        rmax = min(rmax,RR[i])
    print(max(rmax-lmin+1,0))

resolve()
### BUGGY CODE ###

a=int(input())
b = list(map(int, input().split()))
b.sort()
S=0

for i in range(0,a):
    for j in range(i+1,a):
        S=S+b[i]*b[j]
print(S % (10**9+7))

### FIXED CODE ###

a=int(input())
b = list(map(int, input().split()))
b.sort()
S=0
c=sum(b)
for i in range(0,a):
    c=c-b[i]
    S=S+b[i]*c
print(S % (10**9+7))