Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

MOD = 10**9+7

def pow(a):
    b = MOD-2
    res = 1
    while b:
        if b & 1: res = res * a % MOD
        a = a**2 % MOD
        b >>= 1
    return res

def permutation(n, r):
    if r == 0: return 1
    return fac[n] * pow(fac[n-r]) % MOD

def dfs(v, p):
    if p == -1: n = permutation(K-1, len(g[v]))
    else: n = permutation(K-2, len(g[v])-1)
    
    for u in g[v]:
        if u == p: continue
        n = n * dfs(u, v) % MOD
    return n

N, K = map(int, input().split())
g = [[] for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)
    
fac = [1] * (K+1)

for i in range(2, K+1): fac[i] = fac[i-1] * i % MOD

n = dfs(0, -1)

print(K*n % MOD)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import *

MOD = 10**9+7

class Comb:
    def __init__(self, N):
        self.fac = [1] * (N+1)
        for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

    def pow(self, a, b):
        res = 1
        while b:
            if b & 1: res = res * a % MOD
            a = a**2 % MOD
            b >>= 1
        return res

    def comb(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.pow(self.fac[r], MOD-2)) % MOD * self.pow(self.fac[n-r], MOD-2) % MOD

    def permutation(self, n, r):
        return self.fac[n] * self.pow(self.fac[n-r], MOD-2) % MOD

def main():
    N, K = list(map(int, input().split()))
    g = [[] for i in range(N+1)]
    ans = K

    for i in range(N-1):
        a, b = list(map(int, input().split()))
        g[a].append(b)
        g[b].append(a)

    comb = Comb(K)

    q = deque([(-1, 1)])
    while q:
        par, chi = q.pop()
        r = len(g[chi])-1
        if par == -1: k = K-1; r += 1
        else: k = K-2
        if k < r: ans = 0; break

        ans = ans * comb.permutation(k, r) % MOD
        for c in g[chi]:
            if c != par: q.append((chi, c))

    print(ans%MOD)
    
if __name__ == '__main__':
    main()
#import re

s=input()
t=input()
#print(s,t)

flag1=0
for j in range(len(s)-len(t)+1):
  flag=0
  for i in range(len(t)):
    if s[i+j]=='?' or s[i+j]==t[i]:
      flag+=1
  if flag==len(t):
    flag1=1
    s=s[0:j]+t[j-2:j+len(t)-2]+s[j+len(t):]
    s=s.replace('?','a')
    print(s)
    
if flag1==0:
  print('UNRESTORABLE') 

### FIXED CODE ###

s=input()
t=input()
#print(s,t)

if len(s) < len(t):
    print('UNRESTORABLE') 
elif len(s) == len(t):
  cnt=0
  for i in range(len(s)):
    if s[i] == t[i]:
      cnt+=1
    elif s[i] == '?':
      cnt+=1
  if len(t)==cnt:
    print(t)
  else:
    print('UNRESTORABLE') 
else:
  flag1=0
  for j in range(len(s)-len(t),-1,-1):
    cnt=0
    for i in range(len(t)):
      if s[i+j]==t[i]:
        cnt+=1
      elif s[i+j]=='?':
        cnt+=1
    if cnt==len(t):
      flag1=1
      if j==0:
        s=t+s[len(t):]
      if 0 < j < len(s)-len(t)+1:
        s=s[0:j]+t+s[j+len(t):]
      if j == len(s)-len(t)+1:
        s=s[0:j]+t      
      s=s.replace('?','a')
      print(s)
    
  if flag1==0:
    print('UNRESTORABLE')
# coding: utf-8

n = int(input()) 
t = sorted([int(input()) for i in range(n)])

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a
	
def lcm(a, b):
  return a * b // gcd(a, b)
	
def nlcm(list):
  lcm_num = lcm(list[0], list[1])
  for i in range(2,len(list)):
    lcm_num = lcm(lcm_num, list[i])
  print(lcm_num)

nlcm(t)

### FIXED CODE ###

# coding: utf-8

n = int(input()) 
t = sorted([int(input()) for i in range(n)])

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a
	
def lcm(a, b):
  return a * b // gcd(a, b)
	
def nlcm(list):
  if len(list) > 2:
    lcm_num = lcm(list[0], list[1])
    for i in range(2, len(list)):
      lcm_num = lcm(lcm_num, list[i])
    
    print(lcm_num)
  elif len(list) == 2:
    print(lcm(list[0], list[1]))
  else:
  	print(list[-1])

nlcm(t)
def calc_length(s: str, l1: int, l2: int, n: int) -> int:
  max_len = min([l2 - l1, n - l2])
  for i in range(1, max_len):
    if s[l1 + i] != s[l2 + i]:
      return i
  return max_len

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

longest = 0
for l1 in range(n - 2, -1, -1):
  for l2 in range(l1 + longest + 1, n):
    if s[l1] == s[l2]:
      length = calc_length(s, l1, l2, n)
      if length > longest:
        longest = length

print(longest)


### FIXED CODE ###

weather = input()

if weather == 'Sunny':
  print('Cloudy')
elif weather == 'Cloudy':
  print('Rainy')
else:
  print('Sunny')
N=int(input())
A=map(chr,input().split())
print(len(set(A)))

### FIXED CODE ###

N=int(input())
A=set(input() for i in range(N))
print(len(A))
print("Yes" if int(input())%9==o else "No")

### FIXED CODE ###

S=input()
n=0
for s in S:
  n+=int(s)
print("Yes" if n%9==0 else "No")
import sys


def resolve():
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    read = sys.stdin.read

    s, t = read().split('\n')
    
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]

    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1],
                                   dp[i + 1][j],
                                   dp[i][j + 1])

    # LCSを求めたDPから部分文字列を復元
    res = ''
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res += s[i - 1]
            i -= 1
            j -= 1
    print(res[::-1])


resolve()


### FIXED CODE ###

def resolve():
    import sys
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline
 
    s = readline()
    t = readline()
 
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]
 
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j + 1])
 
    # LCSを求めたDPから部分文字列を復元
    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(res[::-1]))
 
 
resolve()
A=int(input())
B=int(input())
if A+B<=8:
    print('Yay!')
elif abs(A-B)<=(16-min([A,B]*2))/2:
    print('Yay!')
else:
    print(':(')


### FIXED CODE ###

A,B=map(int, input().split(' '))
if A+B<=8:
    print('Yay!')
elif abs(A-B)<=(16-min([A,B])*2)/2:
    print('Yay!')
else:
    print(':(')
import math
A,B = list(map(int, input().split()))

print(A*B//math.gcd(A,B))


### FIXED CODE ###

import fractions
A,B = list(map(int, input().split()))

print(A*B//fractions.gcd(A,B))
N,M = map(int, input().split())
A = []
quantity = 0
price = 0

for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
print(A)
A = sorted(A)
for i in range(M):
    quantity += A[i][1]
    if quantity <= M:
        price += A[i][0]*A[i][1]
    else:
       price += A[i][0]*(M-(quantity-A[i][1]))
       break
print(price)

### FIXED CODE ###

N,M = map(int, input().split())
A = []
quantity = 0
price = 0

for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
A = sorted(A)
for i in range(M):
    quantity += A[i][1]
    if quantity < M:
        price += A[i][0]*A[i][1]
    else:
       price += A[i][0]*(M-(quantity-A[i][1]))
       break
print(price)
A, B, C = [int(i) for i in input().split()]
if sorted([A,B,C]==[5,5,7]):
  print('YES')
else:
  print('NO')

### FIXED CODE ###

X = [int(i) for i in input().split()]
if sorted(X)==[5,5,7]:
  print('YES')
else:
  print('NO')
a


### FIXED CODE ###

a,b=map(int,raw_input().split())
if (a+b)%2==0:
  print (a+b)/2
else:
  print "IMPOSSIBLE"
N = int(input())
A = [int(input()) for _ in range(N)]
already = []
for a in A:
  if a not in already:
    already.append(a)
print(len(already))

### FIXED CODE ###

N = int(input())
A = [input() for _ in range(N)]
print(len(list(set(A))))
def main():
    
    n = int(input())
    a = []
    for i in range(n): 
        a.append( 1/int(input()))

    print(1/sum(a))
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

n = int(input())
a = [1/int(e) for e in input().split()]

print(1/sum(a))
code = input('security code: ')

num = list((str)code)

if num[0] == num[1]:
    print('Bad')
elif num[1] == num[2]:
    print('Bad')
elif num[2] == num[3]:
    print('Bad')
else:
    print('Good')

### FIXED CODE ###

num = input()
#num = str(code)

if num[0] == num[1] or num[1] == num[2] or num[2] == num[3]:
    print('Bad')
else:
    print('Good')
x,n = [int(x) for x in input().split()]
if n == 0:
  print(x)
else:
  p = [int(x) for x in input().split()]
  p.sort()
  ans = []
  for i in range(1,101):
    if i in p:
      continue
    b = abs(x - i)
    ans.append((i,b))
  ans = sorted(ans,key = lambda x: x[1])
  #print(ans)
  print(ans[0][0])

### FIXED CODE ###

X, N = map(int, input().split())
p = list(map(int, input().split()))
for d in range(X + 1):
  for s in [-1, +1]:
    a = X + s * d
    if p.count(a) == 0:
      print(a)
      exit(0)
n=int(input())
aa=list(map(int,input().split()))
a=[x for x in aa if x!=1]
n=len(a)
# 素因数分解
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0:
        cnt+=1
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr
tmp=[i for i,j in factorization(min(a))]
not_flg=False
for t in tmp:
  flg=True
  for x in a:
    if x%t==0:
      pass
    else:
      flg=False
      break
  if flg:
    not_flg=flg
    break
if not_flg:
  print('not coprime')
  exit()
#if n>78499:
if n>99999:
  print('setwise coprime')
  exit()
ary=set(())
for x in a:
  tmp={i for i,j in factorization(x)}
  for t in tmp:
    if t in ary:
      print('setwise coprime')
      exit()
    else:
      ary.add(t)
print('pairwise coprime')


### FIXED CODE ###

nn=int(input())
aa=list(map(int,input().split()))
a=[x for x in aa if x!=1]
n=len(a)
if n<=1:
  print('pairwise coprime')
  exit()

# 素因数分解
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0:
        cnt+=1
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr
tmp=[i for i,j in factorization(min(a))]
not_flg=False
for t in tmp:
  flg=True
  for x in a:
    if x%t==0:
      pass
    else:
      flg=False
      break
  if flg:
    not_flg=flg
    break
if not_flg:
  if n==nn:
    print('not coprime')
  else:
    print('setwise coprime')
  exit()
#if n>78499:
if n>99999:
  print('setwise coprime')
  exit()
ary=set(())
for x in a:
  tmp={i for i,j in factorization(x)}
  for t in tmp:
    if t in ary:
      print('setwise coprime')
      exit()
    else:
      ary.add(t)
print('pairwise coprime')
S = input()
if S[1]==S[2]==S[3]:
    print("Yes")
elif S[2]==S[3]==S[4]:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

S = input()
if S[0]==S[1]==S[2]:
    print("Yes")
elif S[1]==S[2]==S[3]:
    print("Yes")
else:
    print("No")
input(x)
cube = x * x * x
print cube

### FIXED CODE ###

x = input()
cube = x * x * x
print cube
# -*- coding: utf-8 -*-
def find(tuple_list, num, top_idx):
    length = len(tuple_list)

    if length == 0:
        return top_idx, False

    if length == 1:
        hikaku = tuple_list[0][0]
        if num == hikaku:
            return top_idx, True
        elif num < hikaku:
            return top_idx-1, False
        elif num > hikaku:
            return top_idx, False
    
    if length == 2:
        hikaku1 = tuple_list[0][0]
        hikaku2 = tuple_list[1][0]
        if num == hikaku1:
            return top_idx, True
        elif num == hikaku2:
            return top_idx+1, True
        elif num < hikaku1:
            return top_idx-1, False
        elif hikaku1 < num < hikaku2:
            return top_idx, False
        elif hikaku2 < num:
            return top_idx+1, False

    place = int(length/2)
    hikaku = tuple_list[place][0]
    if num == hikaku:
        return top_idx+place, True
    elif num < hikaku:
        return find(tuple_list[:place], num, top_idx)
    elif num > hikaku:
        return find(tuple_list[place+1:], num, top_idx+place+1)


N = int(input())
A = list(map(int, input().split()))
A_amount = list(collections.Counter(A).items())
A_amount = list(sorted(A_amount, key=lambda x:x[0]))

result = sum(A)

Q = int(input())
for q in range(Q):
    B, C = map(int, input().split())
    B_idx, is_B_exist = find(A_amount, B, 0)
    if is_B_exist:
        old_tuple = A_amount[B_idx]
        C_idx, is_C_exist = find(A_amount, C, 0)
        if is_C_exist:
            new_tuple = (C, A_amount[B_idx][1]+A_amount[C_idx][1])
            A_amount[C_idx] = new_tuple
            A_amount_before = A_amount[:B_idx]
            A_amount_after = A_amount[B_idx+1:]
            A_amount_before.extend(A_amount_after)
            A_amount = A_amount_before
        else:
            new_tuple = (C, A_amount[B_idx][1])
            if B_idx < C_idx:
                A_amount_1 = A_amount[:B_idx]
                A_amount_2 = A_amount[B_idx+1:C_idx+1]
                A_amount_3 = A_amount[C_idx+1:]
                A_amount_1.extend(A_amount_2)
                A_amount_1.append(new_tuple)
                A_amount_1.extend(A_amount_3)
            else:
                A_amount_1 = A_amount[:C_idx+1]
                A_amount_2 = A_amount[C_idx+1:B_idx]
                A_amount_3 = A_amount[B_idx+1:]
                A_amount_1.append(new_tuple)
                A_amount_1.extend(A_amount_2)
                A_amount_1.extend(A_amount_3)
            A_amount = A_amount_1
    
        result += (C-B)*old_tuple[1]
    
    print(result)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
N = int(input())
A = list(map(int, input().split()))
A_amount = dict(collections.Counter(A))

result = sum(A)

Q = int(input())
for q in range(Q):
    B, C = map(int, input().split())
    B_elem = A_amount.get(B, None)
    if B_elem is not None:
        C_elem = A_amount.get(C, None)
        if C_elem is not None:
            A_amount.pop(B)
            A_amount[C] = B_elem+C_elem
        else:
            A_amount.pop(B)
            A_amount[C] = B_elem

        result += (C-B)*B_elem

    print(result)
A = list(map(int, input().split()))
BC = []
for i in range(M):
    b, c = list(map(int, input().split()))
    BC.append([b, c])
BC = sorted(BC, reverse=True, key=lambda x:x[1])
 
cnt = 0
com = []
for b, c in BC:
    cnt += b
    if cnt > N:
        add = N-cnt+b
        com.extend([c]*add)
        break
    else:
        x = [c]*b 
        com.extend(x)
A.extend(com)
A = sorted(A, reverse=True)   
 
print(sum(A[:N]))

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
cards = [list(map(int, input().split())) for i in range(M)]
cards = sorted(cards, key=lambda x: x[1], reverse=True)

cnt = 0
for card in cards:
    A += [card[1]]*card[0]
    cnt += card[0]
    if cnt >= N:
        break
A.sort(reverse=True)
print(sum(A[:N]))
import sys
def fib(a):
  if a==1:
    return 1
  elif a==0:
    return 1
  else:
    return fib(a-1)+fib(a-2)
def count(a,b):
  if a+1==b:
    return 0
  else:
    return fib(b-a-2)
n,m=map(int,input().split())
a=list(map(int,sys.stdin))
for _ in range(m+1):
  if _ == 0:
    sum = fib(a[_]-1)
  elif _ == m:
    sum = sum*fib(n-a[_-1]-1)%1000000007
  else:
    sum = sum*count(a[_-1],a[_])%1000000007
print(sum)

### FIXED CODE ###

import sys
n,m = map(int,input().split())
a = list(map(int,sys.stdin))
a.append(0)
prev=0
cur=1
m=0
for i in range(1,n+1):
  if a[m]==i:
    prev,cur = cur,0
    m += 1
  else:
    prev,cur = cur,(cur+prev)%1000000007
print(cur)
import sys
h,w=map(int,input().split())
maze=[]
for i in range(w):
    maze.append(list(input()))
for i in range(w):
    for j in range(h):
        if maze[i][j]=="#":
            flg=False
            for l,m in [(0,1),(1,0),(-1,0),(0,-1)]:
                if 0<=i+l<w and 0<=j+m<h:
                    if maze[i+l][j+m]=="#":
                        flg=True
            if flg==False:
                print("No")
                sys.exit()
print("Yes")

### FIXED CODE ###

import sys
h,w=map(int,input().split())
maze=[]
for i in range(h):
    maze.append(list(input()))
for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":
            flg=False
            for l,m in [(0,1),(1,0),(-1,0),(0,-1)]:
                if 0<=i+l<h and 0<=j+m<w:
                    if maze[i+l][j+m]=="#":
                        flg=True
            if flg==False:
                print("No")
                sys.exit()
print("Yes")
s = input()
s.sort()
if s.count(s[0]) == s.count(s[-1]):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s = list(input())
s.sort()
if s[0] == s[1] and s[2] == s[3] and s[0] != s[2]:
  print('Yes')
else:
  print('No')
N=int(input())
cnt = [0]*100000
for i in range(N):
  l, r = map(int, input().split())
  for j in range(l, r+1):
    cnt[j]=1
print(sum(cnt))

### FIXED CODE ###

N=int(input())
cnt = [0]*100002
for i in range(N):
  l, r = map(int, input().split())
  for j in range(l, r+1):
    cnt[j]=1
print(sum(cnt))
import sys
def is_unique(seq):
    return len(seq) == len(set(seq))

N = int(input())
W = []
for i in range(N):
    w.append((input()))
if is_unique(W):
    for i in range(N-1):
        if W[i][-1] != W[i+1][0]:
            print("No")
            sys.exit()
    print("Yes")

else:
    print("No")


### FIXED CODE ###

import sys
def is_unique(seq):
    return len(seq) == len(set(seq))

N = int(input())
W = []
for i in range(N):
    W.append((input()))
if is_unique(W):
    for i in range(N-1):
        if W[i][-1] != W[i+1][0]:
            print("No")
            sys.exit()
    print("Yes")

else:
    print("No")
n = int(input())
p = []
for i in range(n):
    p.append(int(input()))

p_max = max(p)

print(int(sum(p) - p_max / 2)


### FIXED CODE ###

n = int(input())
p = []
for i in range(n):
    p.append(int(input()))

p_max = max(p)

print(int(sum(p) - p_max / 2))
n=input()
x=[0,3,5,7]
p=[]
for c1 in x:
  for c2 in x:
    for c3 in x:
      for c4 in x:
        for c5 in x:
          for c6 in x:
            for c7 in x:
              for c8 in x:
                for c9 in x:
                  line=[c1,c2,c3,c4,c5,c6,c7,c8,c9]
                  sum_=0
                  if line.count(7)>0 and line.count(3)>0 and line.count(5)>0:
                    for i in range(9):
                      sum_+=line[i]*10**i
                    p.append(sum_)
p.sort()
for i in range(len(p)):
  if p[i]>n:
    print(i)

### FIXED CODE ###

n=int(input())
x=[0,3,5,7]
p=[]
flag=True
flag2=True
for c1 in x:
  for c2 in x:
    for c3 in x:
      for c4 in x:
        for c5 in x:
          for c6 in x:
            for c7 in x:
              for c8 in x:
                for c9 in x:
                  line=[c1,c2,c3,c4,c5,c6,c7,c8,c9]
                  sum_=0
                  if line.count(7)>0 and line.count(3)>0 and line.count(5)>0:
                    for i in range(9):
                      if flag==False and line[i] in [3,5,7]:
                        flag2=False
                        break
                      if line[i]==0:
                        flag=False
                      sum_+=line[i]*10**i
                    if flag2==False:
                      flag=True
                      flag2=True
                      continue
                    p.append(sum_)
                    flag=True
p.sort()
for i in range(len(p)):
  if p[i]>n:
    print(i)
    exit()
print(i+1)
a = []
for i in range(3):
    a.append(map(int,raw_input().split()))
n = input()
for j in range(n):
    b = input()
    for j in range(3):
        for k in range(3):
            if a[j][k]==b:
                a[j][k] = 0

res = 'NO'
for l in range(3):
    if sum(a[l]) == 0:
        res = 'Yes'

nl = []

for m in range(3):
    nl.append(a[m][l])

if sum(nl) == 0:
    res = 'Yes'
if sum([a[0][0],a[1][1],a[2][2]]) == 0:
    res = 'Yes'
if sum([a[2][2], a[1][1], a[2][1]]) == 0:
    res = 'Yes'
print res


a,b = map(int,raw_input().split())


### FIXED CODE ###

a = []
for i in range(3):
    a.append(map(int,raw_input().split()))
n = input()
for j in range(n):
    b = input()
    for j in range(3):
        for k in range(3):
            if a[j][k] == b:
                a[j][k] = 0

diag1 = [a[0][0],a[1][1],a[2][2]]
diag2 = [a[0][2],a[1][1],a[2][0]]
res = 'No'
if sum(diag1) ==0 or sum(diag2) ==0:
    res ='Yes'

rowsum = [sum(a[i]) for i in range(3) ]
if 0 in rowsum:
    res = 'Yes'

colSum = [sum([a[j][i] for j in range(3)]) for i in range(3)]
if 0 in colSum:
    res = 'Yes'

print res
s = str(input())

if s == "ARC":
  print("ABC")
else if s == "ABC":
  print("ARC")

### FIXED CODE ###

s = input()
b = "ABC"
r = "ARC"

if s == b:
  print("ARC")
elif s == r:
  print("ABC")
height = []
while 1:
    try:
        height.append(input())
    except EOFError:
        break
height.sort(reverse=True)
for i in range(3):
    print height[i]

### FIXED CODE ###

while 1:
    try:
        a,b = map(int, raw_input().split())
        n = a+b
        print len(str(n))
    except EOFError:
        break
N, X = map(int, input().split())
xs = list(map(int, input().split()))
xs.append(X)
xs.sort()
xs = [_ - xs[0] for _ in xs]
diffs = [xs[i]-xs[i-1] for i in range(1, len(xs))]
def gcd(a, b):
    if(a>b): return gcd(b, a)
    if a % b == 0:
      return b
    else:
      r = a % b
      return gcd(b, r)

prev = diffs[0]
for cur in diffs[1:]:
    prev = gcd(prev, cur)
print(prev)

### FIXED CODE ###

N, X = map(int, input().split())
xs = list(map(int, input().split()))
xs.append(X)
xs.sort()
xs = [_ - xs[0] for _ in xs]
diffs = [xs[i]-xs[i-1] for i in range(1, len(xs))]
def gcd(a, b):
    if(a<b): return gcd(b, a)
    if a % b == 0:
      return b
    else:
      r = a % b
      return gcd(b, r)

prev = diffs[0]
for cur in diffs[1:]:
    prev = gcd(prev, cur)
print(prev)
N = int(input())
#掛け算表は対称行列
#対角成分に移動するときが最短移動
def make_divisors(n):
    divisors = []
    for i in range(1,int(n**0.5)+1):
        for n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors
div = make_divisors(N)
a = div[0]
b = N // a
ans = (a - 1) + (b - 1)
print(ans)

### FIXED CODE ###

N = int(input())
#掛け算表は対称行列
#対角成分に移動するときが最短移動
def make_divisors(n):
    divisors = []
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors
div = make_divisors(N)
l = len(div) // 2
a = div[l]
b = N // a
ans = (a - 1) + (b - 1)
print(ans)
n = int(input())
res = 1
for i in range(1,n+1):
    for k in range(1,1+n):
        num = i**k
        if num <= n :
            res = max(res,num)
    
print(res)

### FIXED CODE ###

a,b,c,d = map(int,input().split())
if abs(a-b)<=d and abs(b-c)<=d:
     print("Yes")
elif abs(a-c)<=d:
    print("Yes")
else:
    print("No")
raw_input()
a = [int(x) for x in raw_input().split()]
bsc = 1e10
for i in range(-101, 102):
  sc = 0
  for j in a:
    sc += (j-i)**2
  bsc = min(bsc, sc)
print bsc

### FIXED CODE ###

N = input()
print N * (N + 1) / 2