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

import sys
from collections import deque
readline = sys.stdin.readline
N = int(readline())

testimonies = {}
for i in range(N):
    A = int(readline())
    testimonies[i] = [[], []]
    for _ in range(A):
        x, y = map(int, readline().rstrip().split())
        testimonies[i][y].append(x-1)

def check(honest_persons):
    """矛盾がないか検証する"""
    honest_checked = set()  # 宛先を確認済みの正直者の人
    honest_stack = deque(honest_persons)  # 宛先を確認する正直者の人の待ち行列
    honest, liers = honest_persons, []  # 正直者の人, 不親切な人

    # 正直者の人の証言も元に、正直者の人/不親切な人を追加していく
    while len(honest_stack) > 0:
        honest_person = honest_stack.popleft()
        honest_checked.add(honest_person)
        next_honest_persons = testimonies[honest_person][1]

        # 検証済み以外の人をstackする
        for person in next_honest_persons:
            if person not in honest_checked:
                honest_stack.append(person)

        honest += testimonies[honest_person][1]
        liers += testimonies[honest_person][0]

    # 矛盾がなければOK
    if len(set(honest) & set(liers)) == 0:
        return True
    else:
        return False

def main():
    # bit全探索する
    ans = 0
    for i in range(1, 2**N):
        comb = bin(i)[2:].zfill(N)
        honest_persons = []
        for p, c in enumerate(comb):
            if c == '1':
                honest_persons.append(p)
        if check(honest_persons):
            ans = max(ans, sum(list(map(int, list(comb)))))

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
N = int(sys.stdin.readline())

testimonies = [[-1 for _ in range(N)] for _ in range(N)]
for i in range(N):
    A = int(sys.stdin.readline())
    for _ in range(A):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        testimonies[i][x-1] = y

def check(honest_persons):
    flag = True
    for i in range(N):
        if honest_persons[i]:
            for j in range(N):
                if testimonies[i][j] == -1:
                    continue
                if testimonies[i][j] != honest_persons[j]:
                    flag = False
                    break
    return flag

def main():
    ans = 0
    for i in range(1, 2**N):
        honest_persons = bin(i)[2:].zfill(N)
        honest_persons = list(map(int, list(honest_persons)))

        if check(honest_persons):
            ans = max(ans, sum(honest_persons))

    print(ans)

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

n, q = map(int, input().split())
c = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    query.append(l << 40 | r << 20 | i)

query.sort()
ball = [list() for i in range(n)]
for i, x in enumerate(c):
    ball[x].append(i)

# binary indexed tree
bit = [0] * (n + 1)
def add(i, x):
    i += 1
    while i <= n:
        bit[i] += x
        i += i & -i

def get(i):
    i += 1
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s

for i in ball:
    if i:
        add(i[0], 1)
        i.reverse()

at = 0
ans = [0] * q
for x in query:
    l = x >> 40
    r = x >> 20 & 0xfffff
    i = x & 0xfffff
    while at < l:
        b = ball[c[at]]
        add(b[-1], -1)
        b.pop()
        if b:
            add(b[-1], 1)
        at += 1
    ans[i] = get(r) - get(l - 1)

for i in ans:
    print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    query.append(l << 40 | r << 20 | i)

query.sort()
ball = [list() for i in range(n)]
for i, x in enumerate(c):
    ball[x].append(i)

# binary indexed tree
bit = [0] * (n + 1)
def add(i, x):
    i += 1
    while i <= n:
        bit[i] += x
        i += i & -i

def get(i):
    i += 1
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s

for i in ball:
    if i:
        add(i[0], 1)
        i.reverse()

at = 0
ans = [0] * q
for x in query:
    l = x >> 40
    r = x >> 20 & 0xfffff
    i = x & 0xfffff
    while at < l:
        b = ball[c[at]]
        add(b[-1], -1)
        b.pop()
        if b:
            add(b[-1], 1)
        at += 1
    ans[i] = get(r) - get(l - 1)

for i in ans:
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


h, w = map(int, input().split())
c = [list(map(ord, input())) for i in range(h)]
INF = 10 ** 9


ans = 0
dq = [0] * ((h + 1) ** 2)
for wi in range(w - 1):
    for diff in range(h + 1):
        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i][wi] == c[i + diff][wi + 1])
        dq[(0 + diff) * (h + 1) + 0] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            cnt -= (c[h - i - 1 - diff][wi] == c[h - i - 1][wi + 1])
            dq[(i + 1 + diff) * (h + 1) + i + 1] = cnt

        cnt = 0
        for i in range(h):
            if i + diff >= h:
                break
            cnt += (c[i + diff][wi] == c[i][wi + 1])
        dq[0 + diff] = cnt
        for i in range(h):
            if i + 1 + diff >= h:
                break
            cnt -= (c[h - i - 1 - diff][wi + 1] == c[h - i - 1][wi])
            dq[(i + 1) * (h + 1) + i + 1 + diff] = cnt
            
    dp = [INF] * ((h + 1) ** 2)
    dp[0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[(i + 1) *(h + 1) + j] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[(i + 1) *(h + 1) + j])
            if j + 1 < h + 1:
                dp[i * (h + 1) + j + 1] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[i * (h + 1) + j + 1])
    ans += dp[-1]

print(ans)

### FIXED CODE ###

def solve(k):
    dp = [[0] * (h + 1) for i in range(h + 1)]
    for i in range(h):
        for diff in range(h - i):
            dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
            dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])

    dq = [[INF] * (h + 1) for i in range(h + 1)]
    dq[0][0] = 0
    for i in range(h):
        dq[i + 1][0] = dq[i][0] + dp[h - i][h]
        dq[0][i + 1] = dq[0][i] + dp[h][h - i]  
    for i in range(h):
        for j in range(h):
            dq[i + 1][j + 1] = min(dq[i + 1][j] + dp[h - (i + 1)][h - j],
                                   dq[i][j + 1] + dp[h - i][h - (j + 1)])

    return dq[h][h]


h, w = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 5
OFFSET = 500

ans = 0
for i in range(w - 1):
    ans += solve(i)
    
print(ans)
### BUGGY CODE ###

N = int(input())

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

max_x = max(numbers) + 1
res = []

for i in range(max_x + 1):
    c = 0
    for n in numbers:
        if n - 1 == i or n == i or n + 1 == i:
            c += 1
    res.append(c)

print(max(res))

### FIXED CODE ###

N = int(input())

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

# max_x = max(numbers) + 1
# max_x = int(sum(numbers) / len(numbers))
# res = 0
test = set()
for n in numbers:
    test.add(n)
    test.add(n - 1)
    test.add(n + 1)
length = len(test)
res = {}
# print(test)
# for i in range(max_x + 1):
for n in numbers:
    c = 0
    sub = set([n - 1, n, n + 1]) & test
    # print(sub)
    for s in sub:
        if res.get(s) is None:
            res[s] = 1
        else:
            res[s] += 1
# for i in test:
#     c = 0
#     for n in numbers:
#         if n - 1 == i or n == i or n + 1 == i:
#             c += 1
#     if res < c:
#         res = c

# print(res)
res = max(res.values())
print(res)
### BUGGY CODE ###

K = int(input())

cnt = 1
sevens = 0

if K % 2 == 0 or K % 5 == 0:
    print(-1)
else:
    while True:
        sevens = sevens * 10 + 7
        if sevens % K == 0:
            print(cnt)
            exit()
        cnt += 1



### FIXED CODE ###

K = int(input())

if K % 2 == 0 or K % 5 == 0:
    print(-1)
else:
    x = 7 % K
    for i in range(1, K + 1):
        if x == 0:
            print(i)
            break
        x = (x * 10 + 7) % K
### BUGGY CODE ###

Q = int(input())
prime = [2]
NUM2017 = []
def setPrime(TOP):
    for x in range(3,TOP+1):
        for y in range(len(prime)):
            if x%prime[y] == 0:
                break
            if y == len(prime)-1:
                prime.append(x)
                if int((x+1)/2) in prime:
                    NUM2017.append(x)
l = [0]*Q
r = [0]*Q
for i in range(Q):
    l[i],r[i] = list(map(int,input().split()))

setPrime(max(r))

for n in range(Q):
    left = 0
    right = 0
    for m in range(len(NUM2017)):
        if NUM2017[m] < l[n]:
            left +=  1
            right += 1
        elif l[n] <= NUM2017[m] and NUM2017[m] <= r[n]:
            right += 1
        else:
            break
    print(right-left)

### FIXED CODE ###

import math
Q=int(input())
querys = [list(map(int,input().split())) for x in range(Q)]
large = max(q[1] for q in querys)
like2017 = [0]*(large+1)

#siever
cands = [False if (5 < i and (i%2)*(i%3)*(i%5) == 0) or (i < 2) or (i == 4) else True for i in range(large+1)]
if 5 <= large:
  for i in range(6,int(math.sqrt(large)+1)):
    if cands[i]:
      for j in range(i*i,large+1,i):
        if cands[j]:
          cands[j] = False

#find 2017-like-number          
for x in range(large+1):
  if cands[x] and cands[(x+1)//2]:
    like2017[x] = 1
for y in range(1,large+1):
  like2017[y] += like2017[y-1]

for q in querys:
  print(like2017[q[1]]-like2017[q[0]-1])
### BUGGY CODE ###

# import time

N,P = list(map(int,input().split()))
S = input()

if P == 2:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 2 == 0:
            c += i+1
    print(c)
        
elif P == 5:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 5 == 0:
            c += i+1
    print(c)

else:
    U = [0]
    a = 0
    t = 1
    
    for i in range(N):
        t %= P
        a += int(S[-i-1])*t
        a %= P
        t *= 10
        U.append(a)
    # print(U)
    
    # t3 = time.time()
    
    c = 0
    
    """
    for i in range(P):
        m = U.count(i)
        c += m*(m-1)//2
    print(c)
    """
    U.sort()
    # print(U)
    q = -1
    for i in range(N):
        if q != U[i]:
            q = U[i]
            m = U.count(q)
            c += m*(m-1)//2
    print(c)
    
    # t4 = time.time()
    # print(t4-t3)
    
    # 10032

### FIXED CODE ###

# import time

N,P = list(map(int,input().split()))
S = input()

if P == 2:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 2 == 0:
            c += i+1
    print(c)
        
elif P == 5:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 5 == 0:
            c += i+1
    print(c)

else:
    U = [0]
    a = 0
    t = 1
    
    for i in range(N):
        t %= P
        a += int(S[-i-1])*t
        a %= P
        t *= 10
        U.append(a)
    U.append(10001)
    # print(U)
    
    # t3 = time.time()
    
    c = 0
    
    """
    for i in range(P):
        m = U.count(i)
        c += m*(m-1)//2
    print(c)
    """
    U.sort()
    # print(U)
    idx = 0
    q = -1
    for i in range(N+2):
        if q != U[i]:
            q = U[i]
            m = i - idx
            idx = i
            c += m*(m-1)//2
    print(c)
    # t4 = time.time()
    # print(t4-t3)
    
    # 10032
### BUGGY CODE ###

H, W = map(int, input().split())

a = H * W
b = 0

for i in range(a):
    if(i % 2 == 0):
        b = b + 1

print(b)

### FIXED CODE ###

import math
H, W = map(int, input().split())

a = H * W
b = 0


if H == 1 or W == 1:
    print(1)
else:
    print(math.ceil(a/2))
### BUGGY CODE ###

N = int(input())
X = [int(i) for i in input().split()]

for i in range(N):
    Y = X[:]
    Y.pop(i)
    Y.sort()
    print(Y[int((N-1)/2)])

### FIXED CODE ###

N = int(input())
X = [int(i) for i in input().split()]
Y = X[:]
Y.sort()

for i in range(N):
    print(Y[int(N/2)] if Y[int(N/2)] > X[i] else Y[int(N/2)-1])
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k+1):
    for l in range(i+1):
        for j in range(l+1):
            if i + j + l == s:
                if i == j and j == l:
                    count += 1
                elif i != j and i != l and j!= l:
                    count += 6
                else:
                    count += 3 
print(count) 


### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k+1):
    for l in range(k+1):
        z = s - i - l
        if 0 <= z <= k:
            count += 1

print(count)
### BUGGY CODE ###

num, capacity = map(int, input().split())
dp = [0]*(capacity+1)

for _ in range(num):
    weight, value = map(int, input().split())
    for w in range(capacity,weight - 1,-1):
        tmp = dp[w - weight] + value
        if dp[w] < tmp:
          dp[w] = tmp
print(dp[capacity])

### FIXED CODE ###

def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]

num, capacity = map(int, input().split())
print(calc(num,capacity))
### BUGGY CODE ###

X = input()
while X.find("ST") != -1:
    Xlist = list(X)
    del Xlist[X.find("ST"):X.find("ST") + 2]
    X = "".join(Xlist)
print(len(X))

### FIXED CODE ###

X = input()
ans = 0

for c in X:
    if c == 'S':
        ans += 1
    if c == 'T' and ans > 0:
        ans -= 1
print(ans * 2)
### BUGGY CODE ###

import sys
import math
input = sys.stdin.readline

n, k = map(int, input().split())
a = list(map(int, input().split()))

if k == 0:
    print(max(a))
    exit()

def check(x):
    res = 0
    for i in a:
        res += i // x
    return res

l = 0
r = 10 ** 9 + 1
while not math.ceil(l) == math.ceil(r):
    x = (l + r) / 2
    if check(x) > k:
        l = x
    else:
        r = x
print(math.ceil(l))


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline

n, k = map(int, input().split())
a = list(map(int, input().split()))

def check(x):
    res = 0
    for i in a:
        res += math.floor(i / x)
    return res

l = 0
r = 10 ** 9 + 1
for _ in range(100):
    x = (l + r) / 2
    if check(x) > k:
        l = x
    else:
        r = x
print(math.ceil(l))
### BUGGY CODE ###

from fractions import gcd
_,a=open(0)
*a,=map(int,a.split())
s=1
for t in a:s*=t//gcd(s,t)
c=0
for i in a:
    c+=s//i
    c%=10**9+7
print(c)

### FIXED CODE ###

from fractions import*
from functools import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=reduce(lambda x,y:x//gcd(x,y)*y,a)%M
c=0
for i in a:
    c+=s*pow(i,M-2,M)
    c%=M
print(c)
### BUGGY CODE ###

n,k=[int(i) for i in raw_input().split()]
p=[int(i)-1 for i in raw_input().split()]
c=[int(i) for i in raw_input().split()]
maxx=-10**18
for i in range(n):
  ct=0;j=0;pos=i
  while j<k:
    ct+=c[pos]
    pos=p[pos]
    j+=1
    maxx=max(maxx,ct)
print maxx

### FIXED CODE ###

n,k=[int(i) for i in raw_input().split()]
p=[int(i)-1 for i in raw_input().split()]
c=[int(i) for i in raw_input().split()]
maxx=-10**18
for i in range(n):
  ct=0;j=0;pos=i
  v=[0]*n
  arr=[]
  while j<k:
    if(v[pos]==1):
  	    break
    v[pos]=1
    ct+=c[pos]
    pos=p[pos]
    arr.append(ct)
    j+=1
  val=0
  if(ct>0):
  	val=ct*((k-j)/j)
  else:
  	val=0
  k1=k
  k1%=j
  k1+=j
  for i1 in range(len(arr)):
  	if(k1-i1>j):
  	    maxx=max(maxx,val+arr[i1],val+ct+arr[i1])
  	else:
  	    maxx=max(maxx,val+arr[i1])
print maxx
### BUGGY CODE ###

N = int(input())
S = input()
ans = 10000000

for i in range(N):
    left = S[0:i]
    right = S[i+1:N]
    count = left.count('W') + right.count('E')
    if ans > count:
        ans = count
    
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
e_count = S.count('E')
w_count = 0
ans = e_count

for s in S:
    if s == 'E':
        e_count -= 1
    else:
        w_count += 1
    if e_count + w_count < ans:
        ans = e_count+w_count

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

import fractions
from functools import reduce
import numpy as np
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
mod = 10**9 + 7
n = int(input())
lst = list(map(int, input().split()))

koubai = lcm_list(lst)
tmp = np.array([koubai for _ in range(n)])
tmp2 = tmp//lst
print(tmp2.sum() % mod)

### FIXED CODE ###

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

def gcd(a, b):
    if a > b:
        a, b = b, a
    while b > 0:
        a, b = b, a % b
    return a

for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
mod = 10**9 + 7
ans = 0
for i in range(n):
    ans += lcm // a[i]
print(ans % mod)
### BUGGY CODE ###

import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
ans = 0
for ai in a:
    idx_b = bisect.bisect_right(b, ai)
    if idx_b == n:
        break
    for bi in b[idx_b:]:
        ans += n - bisect.bisect_right(c, bi)
print(ans)

### FIXED CODE ###

from itertools import accumulate
import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
ans = 0
b_ = []
for bi in reversed(b):
    b_.append(n - bisect.bisect_right(c, bi))
b_ = list(accumulate(b_))[::-1]
for ai in a:
    idx_b = bisect.bisect_right(b, ai)
    if idx_b == n:
        break
    ans += b_[idx_b]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def solve_e(n, a_list):
    days = 0
    ind_list = [0] * n
    match_count = 0
    queue = list(range(n))
    stack = dict()
    while len(queue) > 0:
        days += 1
        new_queue = []
        for p in queue:
            if ind_list[p] < n - 1:
                q = a_list[p][ind_list[p]] - 1
                k = str(min(p, q)) + "_" + str(max(p, q))
                if k in stack.keys():
                    ind_list[p] += 1
                    ind_list[q] += 1
                    # print(days, p, q)
                    new_queue.append(p)
                    new_queue.append(q)
                    match_count += 1
                else:
                    stack[k] = 1
        queue = new_queue
    if match_count == n * (n - 1) // 2:
        return days - 1
    else:
        return -1


def test():
    N = 1000
    A_list = []
    for i in range(N):
        A_list.append(list(range(1, i + 1)) + list(range(i + 2, N + 1)))
    print(solve_e(N, A_list))


def main():
    N = int(input())
    A_list = []
    for _ in range(N):
        A_list.append(list(map(int, input().split())))
    print(solve_e(N, A_list))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def solve_e(n, a_list):
    days = 0
    ind_list = [0] * n
    match_count = 0
    queue = list(range(n))
    stack = dict()
    while len(queue) > 0:
        days += 1
        new_queue = []
        for p in queue:
            if ind_list[p] < n - 1:
                q = a_list[p][ind_list[p]] - 1
                k = str(min(p, q)) + "_" + str(max(p, q))
                if k in stack.keys():
                    ind_list[p] += 1
                    ind_list[q] += 1
                    # print(days, p, q)
                    new_queue.append(p)
                    new_queue.append(q)
                    match_count += 1
                else:
                    stack[k] = 1
        queue = new_queue
    if match_count == n * (n - 1) // 2:
        return days - 1
    else:
        return -1


def test():
    N = 1000
    A_list = []
    for i in range(N):
        A_list.append(list(range(1, i + 1)) + list(range(i + 2, N + 1)))
    print(solve_e(N, A_list))


def main():
    N = int(input())
    A_list = []
    for _ in range(N):
        A_list.append(list(map(int, input().split())))
    print(solve_e(N, A_list))


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

num = int(input())
item_list = []
count = 0

for i in range(num):
    item = input()
    # print(item in item_list)
    if (item in item_list) == False:
        item_list.append(item)
        count += 1
        
print(count)

### FIXED CODE ###

import collections

num = int(input())
item = [input() for i in range(num)]

item_count = collections.Counter(item)

print(len(item_count.keys()))
### BUGGY CODE ###

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

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

def lcm(a, b):
    return (a * b)//gcd(a,b)

lcm_a = 1

for i in range(N):
    lcm_a = lcm(lcm_a,A[i])

B = []

for i in range(N):
    B.append(lcm_a//A[i])

mod = int(1e9+7)

print(sum(B)%mod)

### FIXED CODE ###

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

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

def lcm(a, b):
    return (a * b)//gcd(a,b)

lcm_a = 1

for i in range(N):
    lcm_a = lcm(lcm_a,A[i])

ans = 0
for i in range(N):
    ans += lcm_a//A[i]

mod = int(1e9+7)

print(ans%mod)
### BUGGY CODE ###

n1 = int(input())
A = list(map(int, input().split()))
n2 = int(input())
q = list(map(int, input().split()))

B = []

n = n1
ans = list("no" for i in range(n2))

for i in range(2 ** n):
    C0 = []
    B = list(map(int, format(i, "b").zfill(n)))[::-1]
    C0 = [ x*y for x, y in zip(A, B)]
    C = sum(C0)
    for j, r in enumerate(q):
        if  C == r:
            ans[j] = "yes"
print(*ans, sep="\n")

### FIXED CODE ###

n1 = int(input())
A = list(map(int, input().split()))
n2 = int(input())
q = list(map(int, input().split()))

B = []
C = []
n = n1
ans = list("no" for i in range(n2))

for i in range(2 ** n):
    C0 = []
    B = list(map(int, format(i, "b").zfill(n)))[::-1]
    C0 = [ x*y for x, y in zip(A, B)]
    C.append(sum(C0))

for j, r in enumerate(q):    
    if  r in C:
        ans[j] = "yes"

print(*ans, sep="\n")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
N, M = (int(i) for i in input().split())
input_list = [[int(i) for i in input().split()] for i in range(M)] 
 
m_list = [[] for j in range(N+1)]
 
for inputs in input_list:
    m_list[inputs[0]].append(inputs[1])
 
for arr in m_list:
    arr.sort()
    arr.insert(0,-10000)
 
for inputs in input_list:
    num = m_list[inputs[0]].index(inputs[1])
    print(str(inputs[0]).zfill(6) + str(num).zfill(6))

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N, M = (int(i) for i in input().split())
py_list = [[int(i) for i in input().split()] + [0] for i in range(M)] 
m_list = [[] for j in range(N+1)]
 
sorted_py_list = sorted(py_list, key=lambda x:x[1])

city_list = {}
for py in sorted_py_list:
    city_list[py[0]] = city_list[py[0]]+1 if py[0] in city_list else 1
    py[2] = city_list[py[0]]
 
for py in py_list:
    print(str(py[0]).zfill(6) + str(py[2]).zfill(6))
### BUGGY CODE ###

import numpy as np
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
if len(np.unique(a)) == 1:
    print(len(a))
else:
    for i in a[::-1][1:]:
        if max(c) <= i:
            c.append(i)
        else:
            c[np.where(np.array(c)>i)[0][0]] = i
    print(len(c))

### FIXED CODE ###

def se(c, x, h, l):
    if h == l:
        return l
    t = (h+l)//2
    if c[t] <= x:
        a = se(c,x,h,t+1)
    else:
        a = se(c,x,t,l)
    return a
        
    
import numpy as np
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
diff = np.diff(a)
tmp = np.sum(diff<=0)
if tmp == len(diff):
    print(len(a))
elif tmp == 0:
    print(1)
else:
    for i in a[::-1][1:]:
        if c[-1] <= i:
            c.append(i)
        else:
            c[se(c,i,len(c),0)] = i
    print(len(c))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

ans = 0

for i in range(n - 1):
    for j in range(i + 1, n):
        ans += a[i] * a[j]

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

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0
v = sum(a)

for i in range(n - 1):
    v -= a[i]
    ans += a[i]*v

print(ans % mod)