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

# D - We Love ABC

S = input()
N = len(S)
MOD = 10**9 + 7

def find_cumsum(X):
    output = [1] if S[0] == X else [0]    
    for idx in range(1,N):
        if S[idx] == X:
            output.append(output[-1]+1)
        else:
            output.append(output[-1])
    return output

q_count = S.count("?")
A_cumsum = find_cumsum("A")
q_cumsum = find_cumsum("?")
        
# last_b[i][j] : S[j]を末尾の"B"とするABのインデックスのパターンの中で、i個の?を"AB"のために使用したもの
last_b = [[0] for _ in range(3)]
for idx in range(1,N):
    if S[idx] == "B":
        last_b[0].append(A_cumsum[idx-1]) # AB
        last_b[1].append(q_cumsum[idx-1]) # ?B
        last_b[2].append(0)
    elif S[idx] == "?":
        last_b[0].append(0)
        last_b[1].append(A_cumsum[idx-1]) # A?
        last_b[2].append(q_cumsum[idx-1]) # ??
    else:
        for i in [0,1,2]:
            last_b[i].append(0)

last_b_cumsum = [[last_b[0][0]], [last_b[1][0]], [last_b[2][0]]]
for i in range(3):
    for idx in range(1,N):
        last_b_cumsum[i].append((last_b[i][idx] + last_b_cumsum[i][-1]) % MOD)

ans = 0
for idx in range(2,N):
    ans %= MOD
    if S[idx] == "C":
        for n_q in range(min(q_count,2)+1):
            ans += last_b_cumsum[n_q][idx-1] * 3**(q_count-n_q)
    elif S[idx] == "?":
        for n_q in range(1, min(q_count,3)+1):
            ans += last_b_cumsum[n_q-1][idx-1] * 3**(q_count-n_q)
        
print(ans % MOD)

### FIXED CODE ###

# D - We Love ABC

S = list(input())
MOD = 10**9 + 7

n_possible = 1 # その場所以前の文字列としてあり得るパターン
A = 0 # その場所以前の文字列におけるA数
B = 0
C = 0

for s in S:
    if s == "A":
        A += n_possible
    elif s == "B":
        B += A
    elif s == "C":
        C += B
    else:
        # X = 3*X + Y
        # この場所の？を (AorABorABCの一部に含めない場合) + (AorABorABCの一部に含める場合)
        C = 3*C + B
        B = 3*B + A
        A = 3*A + n_possible
        n_possible *= 3
    n_possible %= MOD
    A %= MOD
    B %= MOD
    C %= MOD
        
print(C)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += (a[i] % mod)*(a[j] % mod) % mod

ans %= mod
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0
total = sum(a)
for i in range(n):
    total -= a[i]
    ans += a[i]*total
    ans %= mod
print(ans)
### BUGGY CODE ###

X,Y,A,B,C = [int(i) for i in input().split()]

def input_list(N):
  list = []
  for i in input().split():
    list.append(int(i))
  list.sort(reverse=True)
  return list

P = input_list(A)
Q = input_list(B)
R = input_list(C)

def delete_last(list,X):
  for i in range(X,len(list)):
    list.pop(X)

delete_last(P,X)
delete_last(Q,Y)


Top = P + Q + R
Top.sort(reverse=True)
sum = 0
for i in range(X+Y):
  sum += Top[i]
print(sum)


### FIXED CODE ###

X,Y,A,B,C = [int(i) for i in input().split()]

def input_list(N):
  list = []
  for i in input().split():
    list.append(int(i))
  list.sort(reverse=True)
  return list

P = input_list(A)
Q = input_list(B)
R = input_list(C)
Top = P[:X] + Q[:Y] + R
Top.sort(reverse=True)
sum = 0
for i in range(X+Y):
  sum += Top[i]
print(sum)
### BUGGY CODE ###

from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
P = [p for _, _, p in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: M -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cx, cy = costX[stateX], costY[stateY]
    cost, an = 0, ans[M]
    for s in map(min, zip(cx, cy)):
        cost += s
        if cost >= an:
            break
    else:
        ans[M] = cost

print(*ans, sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = ["#" *(w+2) ] + ["#" + input()+ "#" for _ in range(h)] + ["#" *(w+2) ]
v = [[10 ** 6]*(w+2) for _ in range(h+2)]
v[ch][cw] = 0
Q = deque([(ch,cw)])
while Q :
    y,x = Q.popleft()

    for i,j in [(0,1),(1,0),(-1,0),(0,-1)] :
        if S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x]:
            v[y+i][x+j] = v[y][x]
            Q.append((y+i,x+j))
    for i in range(-2,3) :
        for j in range(-2,3) :
            if i == j == 0 :
                continue
            elif 1 <= y+i <= h and 1 <= x+j <= w and S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x] + 1 :
                v[y+i][x+j] = v[y][x] + 1
                Q.appendleft((y+i,x+j))
ans = v[dh][dw]
if ans == 10 ** 6 :
    print(-1)
else :
    print(ans)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = ["#" *(w+2) ] + ["#" + input()+ "#" for _ in range(h)] + ["#" *(w+2) ]
v = [[10 ** 6]*(w+2) for _ in range(h+2)]
v[ch][cw] = 0
Q = deque([(ch,cw)])
while Q :
    y,x = Q.pop()
    for i,j in [(0,1),(1,0),(-1,0),(0,-1)] :
        if S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x]:
            v[y+i][x+j] = v[y][x]
            Q.append((y+i,x+j))
    for i in range(-2,3) :
        for j in range(-2,3) :
            if i == j == 0 :
                continue
            elif 1 <= y+i <= h and 1 <= x+j <= w and S[y+i][x+j] == "." and v[y+i][x+j] > v[y][x] + 1 :
                v[y+i][x+j] = v[y][x] + 1
                Q.appendleft((y+i,x+j))
ans = v[dh][dw]
if ans == 10 ** 6 :
    print(-1)
else :
    print(ans)
### BUGGY CODE ###

from collections import deque

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

q = deque()

i = 2
ans=1
while(True):
    if(P%(i**N)==0):
        q.append(i)
        P=P//(i**N)
        ans*=i
    else:
        i+=1
    if(P<i):
        break
print(ans)
    

### FIXED CODE ###

import collections

n,p=map(int,input().split())

a=[]
while p % 2 == 0:
  p //= 2
  a.append(2)
f = 3
while f * f <= p:
  if p % f == 0:
    a.append(f)
    p //= f
  else:
    f += 2
if p != 1:
  a.append(p)

dct=collections.Counter(a)

ans=1

li=dct.items()

for tt in li:
  if tt[1]//n>=1:
    ans*=tt[0]**(tt[1]//n)
print(ans)
### BUGGY CODE ###

from fractions import gcd
N=int(input())
a = list(map(int, input().split()))
lcm = 1
for i in range(N):
    lcm = lcm * a[i] // gcd(lcm, a[i])
import numpy as np
aa = np.array(a)
print(sum(lcm//aa)%(10**9+7))


### FIXED CODE ###

from fractions import gcd
N=int(input())
a = list(map(int, input().split()))
lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm, i)
ans = 0
for i in a:
    ans += (lcm//i)#%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

Q = int(input())

a = [0]*10**5
ans = []

prime = isPrime_np(10**5)
pset = set(prime)

for i in range(Q):
    l,r = map(int,input().split())
    for p in prime:
        if p>r:
            break
        if (p+1)/2 in pset:
            a[p] = 1
    ans.append(sum(a[l:r+1]))

print(*ans,sep="\n")

### FIXED CODE ###

import numpy as np

def isPrime_np(n):
    maxp = int(np.sqrt(n))
    searchlist = [i for i in range(2,n+1)]
    primeNum = []

    while searchlist[0] <= maxp:
        primeNum.append(searchlist[0])
        tmp = searchlist[0]
        searchlist = [i for i in searchlist if i % tmp != 0]
    primeNum.extend(searchlist)
    
    return primeNum

MaxQ = 10**5+1
Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]

a = [0]*MaxQ
s = [0]*MaxQ
prime = isPrime_np(MaxQ)
pset = set(prime)
for p in prime:
    if (p+1)/2 in pset:
        a[p] = 1

ans = []
for i in range(MaxQ-1):
    s[i+1] = s[i] + a[i]
    
for l,r in lr:
    ans.append(s[r+1] - s[l])
print(*ans,sep="\n")
### BUGGY CODE ###

n,m = map(int,input().split())
br = [list(map(int,input().split())) for i in range(m)]
ans = [(n*(n-1))//2]
member = [[i] for i in range(n)]

def search_member(br_i, member):
     flag = 0
     br_mem_num =[]
     mem_1 = br_i[0] - 1
     mem_2 = br_i[1] - 1
     for i in range(len(member)):
          if mem_1 in member[i]:
               br_mem_num.append(i)
               flag += 1
          if mem_2 in member[i]:
               br_mem_num.append(i)
               flag += 1
          if flag == 2:
               break
     return br_mem_num
     
def change_member(br_mem_num, member):
     mem1_num = br_mem_num[0]
     mem2_num = br_mem_num[1]
     member[mem1_num] += member[mem2_num]
     member[mem1_num].sort()
     member[mem2_num] = []

for i in range(m-1,-1,-1):
     br_i = br[i]
     br_mem_num = search_member(br_i, member)
     if br_mem_num[0] != br_mem_num[1]:
          len_1, len_2 = len(member[br_mem_num[0]]), len(member[br_mem_num[1]])
          ans.append(ans[-1] - (len_1*len_2))
          change_member(br_mem_num, member)
     else:
          ans.append(ans[-1])

for i in range(m-1,-1,-1):
     print(ans[i])

### FIXED CODE ###

#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])
### BUGGY CODE ###

n, q = map(int,input().split())
s = input()
lr_list = []
for i in range(q):
    lr_list.append(list(map(int,input().split())))
    
for i in range(q):
    l,r = lr_list[i]
    print(s[l-1:r].replace('AC','1').count('1'))
    

### FIXED CODE ###

n, q = map(int,input().split())
s = input()
ruiseki = [0]*(n+1)
for i in range(n):
    if s[i:i+2] == 'AC':
        ac = 1
    else:
        ac = 0
    ruiseki[i+1] = ruiseki[i] + ac
ans_list = []
for i in range(q):
    l,r = map(int,input().split())
    ans_list.append(ruiseki[r-1]-ruiseki[l-1])
for i in range(q):
    print(ans_list[i])
### BUGGY CODE ###

n=int(input())
l=list(map(int, input().split()))
s=set(l)
d=dict()

for x in s:
    d[x] = l.count(x)

d2=dict()

sum = 0
for key in d.keys():
    a = d[key]
    sum += (a*(a - 1)) // 2


for x in l:
    print(sum - d[x] +1)

### FIXED CODE ###

n=int(input())
l=list(map(int, input().split()))
s=set(l)
d=dict()

for x in l:
    d[x]=0
for x in l:
    d[x]+=1


sum = 0
for key in d.keys():
    a = d[key]
    sum += (a*(a - 1)) // 2


for x in l:
    print(sum - d[x] +1)
### BUGGY CODE ###

n,k=map(int,input().split())
ans=0
while n>=0:
    n//k
    ans+=1
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
ans=0
while(n>0):
    n=n//k
    ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())

Ss = [None for _ in range(N)]

dic = dict()

for i in range(N):
  Ss[i] = input()

for s in Ss:
  if s in dic:
    dic[s] += 1
  else:
    dic[s] = 1

# dic = sorted(dic.items(), key=lambda x:x[0])

max_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())]

max_list.sort()

for lis in max_list:
  print(lis)


### FIXED CODE ###

N = int(input())

s = [None for _ in range(N)]

for i in range(N):
  s[i] = input()

s.sort()

max_list = []
max_v = 1

count = 1
prev = s[0]


for i in range(1, N):
  # print(s[i], prev, count)
  if s[i] == prev:
    count += 1
  else:
    if max_v == count:
      max_list.append(prev)
    elif max_v < count:
      max_list = [prev]
      max_v = count
    count = 1
    prev = s[i]


if max_v == count:
  max_list.append(prev)
elif max_v < count:
  max_list = [prev]
  max_v = count

for k in max_list:
  print(k)
### BUGGY CODE ###

monsters, special = map(int, input().split())
HP = list(map(int, input().split()))

for i in range(special):
  HP.remove(max(HP))
  if HP == []:
    break

print(sum(HP))

### FIXED CODE ###

import heapq
ceruleans, skills = map(int, input().split())
HP = list(map(lambda x: int(x) * (-1), input().split())) # OK! 次に進もうぜ
heapq.heapify(HP)

for i in range(skills):
  heapq.heappop(HP)

  if HP == []:
    break

print(-sum(HP))
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    sum_amount = 0
    dists = []
    dists_comb = {}

    for i in range(len(A)):
        k = 1
        if A[i] == 1:
            dists.append((i, k, k))
        else:
            while A[i] // 2**k > 0:
                dists.append((i, (A[i] // 2**(k - 1) - A[i] // 2**k), k))
                k += 1
    
    dists = sorted(dists, key=lambda x: x[1], reverse=True)
    
    for d in dists:
        if M == 0:
            break
        if dists_comb.get(d[0], 0) != 0:
            M -= (d[2] - dists_comb[d[0]])
            dists_comb[d[0]] = d[2]
        else:
            dists_comb[d[0]] = d[2]
            M -= d[2]
    
    if M > 0:
        print(0)
    else:
        for i in range(N):
            sum_amount += A[i] // (2 ** dists_comb.get(i, 0))
        print(sum_amount)
         

if __name__ == '__main__':
    main()

### FIXED CODE ###

import heapq
from math import ceil


def main():
    N, M = map(int, input().split())

    # As heapq.heappop returns the mininum value of the sequence,
    # we need to multiply -1 in order to attain the maximum
    # value of the sequence.
    A = list(map(lambda x: (-1) * int(x), input().split()))
    heapq.heapify(A)
    for i in range(M):
        heapq.heappush(A, ceil(heapq.heappop(A) / 2))

    print(-sum(A))


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

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

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
def solve(a):
    ans = 1
    if 0 in a:
        return 0
    for i in a:
        ans *= i
        if ans > pow(10, 18):
            return -1
    return ans
ans = solve(a)
print(ans)
### BUGGY CODE ###

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

A.sort()
B = [0]*N

for i in range(N):
    if B[i]:
        continue
    if i < N-1:
        if A[i] == A[i+1]:
            B[i] = 1
    x = A[i]
    for j in range(i+1, N):
        if A[j]%x == 0:
            B[j] = 1

print(N-sum(B))

### FIXED CODE ###

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

dlen = A[-1]+3
d = [True]*dlen
for a in A:
    if d[a]:
        for i in range(a*2, dlen, a):
            d[i] = False

res = 0
for i in range(N):
    if i > 0:
        if A[i] == A[i-1]:
            continue
    if i < N-1:
        if A[i] == A[i+1]:
            continue
    if d[A[i]]:
        res += 1
print(res)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
work=[]
while l:
    if len(l)==1 or l[1]!=l[0]:work.append(l[0])
    l=[x for x in l[1:] if x%l[0]!=0]
print(len(work))

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
m=l[-1]
work=[0]*(m+1)
for i in l:
    if work[i]<=1:
        for j in range(i,m+1,i):
            work[j]+=1
sm=0
for s in l:
    if work[s]==1: sm+=1
print(sm)
### BUGGY CODE ###

import itertools as it

n, x, y = list(map(int, input().split(' ')))

dist_list = []
dist_a = dist_list.append
for i, j in it.combinations(list(range(n)), 2):
    warp_dist = abs(i - (x - 1)) + 1 + abs(j - (y - 1))
    if abs(j - i) < warp_dist:
        dist_a(abs(j - i))
    else:
        dist_a(warp_dist)

for i in range(1, n):
    print(dist_list.count(i))


### FIXED CODE ###

import itertools as it
import collections
 
n, x, y = list(map(int, input().split(' ')))
 
dist_list = []
dist_a = dist_list.append
for i, j in it.combinations(list(range(n)), 2):
    warp_dist = abs(i - (x - 1)) + 1 + abs(j - (y - 1))
    if abs(j - i) < warp_dist:
        dist_a(abs(j - i))
    else:
        dist_a(warp_dist)
 
dist_c = collections.Counter(dist_list)
 
for i in range(1, n):
    print(dist_c[i])
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
ans = "Yes"
for i in range(N - 1):
  if H[i] > H[i + 1]:
    H[i] = H[i] - 1
    if H[i] > H[i + 1] or max(H[:i]) != H[i]:
      ans = "No"
print(ans)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
ans = "Yes"
for i in range(0, N - 1):
  diff = H[i + 1] - H[i]
  if diff >= 1:
    H[i + 1] -= 1
  elif diff < 0:
    ans = "No"
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0]*(max(A))

for i in A:
    B[i-1] += 1

ans = 0
C = set()
for i in sorted(set(A)):
    if i in C:
        continue
    if B[i-1] == 1:
        ans += 1
    for j in range(2 * i,max(A)+1,i):
        if B[j-1]:
            C.add(j)
            B[j-1] = 0

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
maxA = max(A)
B = [0]*(maxA)

for i in A:
    B[i-1] += 1

ans = 0
for i in sorted(A):
    if B[i-1] == 0:
        continue
    if B[i-1] == 1:
        ans += 1
    for j in range(i,maxA+1,i):
        B[j-1] = 0

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

def NextAmari(prev,d):
    return((prev*10+d)%13)

S = input()
mod = 10**9 + 7
DP = [[0]*13 for i in range(len(S)+1)]#DP[i][j] = 上位i桁目まで見たときの、j(mod13)の数　0<=j<13

DP[0][0] = 1
for n,s in enumerate(S):
    i = n
    if s != "?":
        d = int(s)
        for j,num in enumerate(DP[i]):
            DP[i+1][NextAmari(j,d)] += num
    else:
        for d in range(10):
            for j,num in enumerate(DP[i]):
                DP[i+1][NextAmari(j,d)] += num
    for a in range(13):
        DP[i+1][a] %= mod
print(DP[-1][5])

### FIXED CODE ###

def NextAmari(prev,d):
    return((prev*10+d)%13)

S = input()
mod = 10**9 + 7
DP = [[0]*13 for i in range(len(S)+1)]#DP[i][j] = 上位i桁目まで見たときの、j(mod13)の数　0<=j<13

DP[0][0] = 1
for n,s in enumerate(S):
    i = n
    if s != "?":
        d = int(s)
        for j,num in enumerate(DP[i]):
            DP[i+1][NextAmari(j,d)] += num
    else:
        for d in range(10):
            for j,num in enumerate(DP[i]):
                DP[i+1][NextAmari(j,d)] += num
    for a in range(13):
        DP[i+1][a] %= mod
print(DP[-1][5])
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    for i in range(M):
        a = AB[2*i]
        b = AB[2*i+1]
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    stack = []
    seen[1] = True
    heappush(stack, (0, 1, 0))# (distance, node, prev)
    INF = 1<<64
    mark = [INF] * (N+1)


    while stack:
        dist, current, prev = heappop(stack)
        seen[current] = True
        if mark[current] == INF:
            mark[current] = prev
        for next in to[current]:
            if not seen[next]:
                heappush(stack, (dist+1, next, current))

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
def run():
    N, M = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    for a,b in zip(A,B):
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    queue = deque([])
    seen[1] = True
    queue.append((1, 0))# (node, prev)
    mark = [0] * (N+1)

    while queue:
        current, prev = queue.popleft()
        for next in to[current]:
            if not seen[next]:
                queue.append((next, current))
                mark[next] = current
                seen[next] = True

    print('Yes')
    mark = [str(val) for val in mark]
    print('\n'.join(mark[2:]))

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

from collections import defaultdict
from itertools import permutations
n = int(input())
dicts = []
sets = []
da = dicts.append
sa = sets.append
for i in [input() for _ in range(n)]:
    tmp_dict = defaultdict(lambda: 0)
    for j in i:
        tmp_dict[j] += 1
    tmp_set = set(tmp_dict.keys())
    da(tmp_dict)
    sa(tmp_set)

intersection = sets[0]
for i in sets:
    intersection = intersection & i

final_dict = {}
final_words = ''
for i in list(intersection):
    tmp = 100
    for j in dicts:
        t = j[i]
        if t < tmp:
            tmp = t
    final_words += i*tmp
words = [i for i in permutations(final_words)]
for i in sorted(words[0]):
    print(i, end='')

### FIXED CODE ###

from collections import defaultdict
n = int(input())
dicts = []
sets = []
da = dicts.append
for i in [input() for _ in range(n)]:
    tmp_dict = defaultdict(lambda: 0)
    for j in i:
        tmp_dict[j] += 1
    da(tmp_dict)

intersection = set(dicts[0].keys())
for i in dicts[1:]:
    intersection = intersection & i.keys()
final_words = ''
for i in sorted(list(intersection)):
    tmp = 100
    for j in dicts:
        t = j[i]
        if t < tmp:
            tmp = t
    final_words += i*tmp
print(final_words)