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

import sys
input = sys.stdin.readline


def main():
    s = input().strip()
    q = int(input())
    queries = [input().split() for _ in range(q)]
    for query in queries:
        if query[0] == "1":
            s = s[::-1]
            continue
        if query[1] == "1":
            s = "".join(query[2] + s)
        else:
            s = "".join(s + query[2])
    print(s)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    s = input().strip()
    q = int(input())
    queries = [input().split() for _ in range(q)]
    pre = []
    post = []
    flg = True
    for query in queries:
        if query[0] == "1":
            flg = not flg
            continue
        if query[1] == "1":
            if flg:
                pre.append(query[2])
            else:
                post.append(query[2])
        else:
            if flg:
                post.append(query[2])
            else:
                pre.append(query[2])
    pre.reverse()
    pre.append(s)
    pre.extend(post)
    s = "".join(pre)
    if not flg:
        s = s[::-1]
    print(s)


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

l = [int(x) for x in input().split()]
N = l[0]
K = l[1]
P = [int(x) for x in input().split()]

expected = []
a = 0
ans = []

for i in range(len(P)):
    a = 0
    for j in range(P[i]):
        a += ((j+1)/P[i])
    expected.append(a)
#print(expected)

for k in range(N - K + 1):
    a = 0
    for x in range(K):
        a += expected[k+x]
    ans.append(a)
#print(ans)
print(max(ans))


### FIXED CODE ###

from itertools import accumulate
n,k=map(int, input().split())
A=[((int(i)*(int(i)+1))/2)/int(i) for i in input().split()]
al = list(accumulate(A))
ans = al[k-1]
for i in range(k, n):ans=max(ans, al[i]-al[i-k])
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
q = []
for i in range(m):
    b,c = map(int,input().split())
    q.append([c,b])
q.sort(reverse=True)
for i in range(m):
    cnt = 0
    for j in range(n):
        if a[j] < q[i][0]:
            a[j] = q[i][0]
            cnt+=1
        if cnt == q[i][1]:
            break
print(sum(a))

### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
q = []
for i in range(m):
    b,c = map(int,input().split())
    q.append([c,b])
q.sort(reverse=True)
j = 0
for i in range(m):
    while j < len(a) and q[i][1]>0:
        if a[j]<q[i][0]:
            a[j] = q[i][0]
            q[i][1] -= 1
        j+=1
print(sum(a))
### BUGGY CODE ###

n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

loop=set()
d=[-10**15 for _ in [0]*n]
d[0]=0
q=[[0,1]]
s=set()
l=[]
while q:
    item,depth=q.pop()
    if depth<=len(s):
        for _ in range(len(s)-depth+1):
            rmv=l.pop()
            s.remove(rmv)
    l.append(item)
    s.add(item)
    for i,dist in g[item]:
        if d[i]<d[item]+dist:
            if i in s:
                loop.add(i)
                continue
            d[i]=d[item]+dist
            q.append([i,depth+1])
    
def check(x):
    q=[x]
    c=[False for _ in [0]*n]
    c[x]=True
    while q:
        item=q.pop()
        for i,j in g[item]:
            if c[i]==False:
                c[i]=True
                q.append(i)
        if c[n-1]==True:
            return True
            break
    else:
        return False
    
for i in loop:
    if check(i)==True:
        print("inf")
        break
else:
    print(d[n-1])

### FIXED CODE ###

n,m=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]

dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for _ in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j)
    a,b=b,dist[n-1]

if a==b:
    print(a)
else:
    print("inf")
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
l=[0]*Q
r=[0]*Q

for i in range(Q):
  l[i],r[i]=map(int,input().split())

for i in range(Q):
  s=S[l[i]-1:r[i]]
  s=s.replace('AC','1')
  print(s.count('1'))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()

t=[0]*(N+1)
for i in range(N):
  t[i+1]=t[i]+(1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import collections
s = (input())

"""
n = len(s)
ans = 0
for i in range(n-4):
    for j in range(i+4,n+1):
        if int(s[i:j]) % 2019 == 0:
            ans += 1
print(ans)
"""

n = len(s)
ans = 0
l = 0
#r = l
num = int(s)

tmp = [0 for _ in range(n+1)]
tmp1 = 0
for i in range(0,n):
    tmp1 += (int(s[n-i-1]) * pow(10, i))
    tmp[i+1] = tmp1 % 2019
#print(tmp)

c = collections.Counter(tmp)
#print(c)
for i in range(0, 2020):
    if c[i] > 0:
        ans += ((2 * c[i] - 1) // 2)
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
s = (input())

"""
n = len(s)
ans = 0
for i in range(n-4):
    for j in range(i+4,n+1):
        if int(s[i:j]) % 2019 == 0:
            ans += 1
print(ans)
"""

n = len(s)
ans = 0
l = 0
#r = l
num = int(s)

tmp = [0 for _ in range(n+1)]
ten = [0 for _ in range(n)]
tmp1 = 0
val = 1
for i in range(0,n):
    ten[i] = val
    tmp1 += (int(s[n-i-1]) * val)
    tmp[i+1] = tmp1 % 2019
    val = (val * 10) % 2019
#print(tmp)

c = collections.Counter(tmp)
#print(c)
for i in range(0, 2020):
    a = c[i]
    if a > 0:
        ans += ((a * (a - 1)) // 2)
print(ans)
### BUGGY CODE ###

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

cnt = 1
min = N

for i in range(1, N):
  if P[i] > min:
    continue
  for j in range(i-1, -1, -1):
    if P[i] > P[j]:
      break
  else:
    if min >P[i]:
      min = P[i]
    cnt += 1
    if min == 1:
      break


print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
min_p = P[0]
cnt = 0

for p in P:
  if p <= min_p:
    min_p = p
    cnt += 1

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

import collections

n = int(input())
l = [input() for i in range(n)]
c = collections.Counter(l)

m = c.most_common()[0][1]

ans = []
for i in range(len(c)):
    if m > c.most_common()[i][1]:
        break
    ans.append(c.most_common()[i][0])

ans.sort()
print(*ans)


### FIXED CODE ###

import collections
import itertools

n = int(input())
l = [input() for _ in range(n)]
counter = collections.Counter(l)

mode_v = counter.most_common()[0][-1]
it = itertools.takewhile(
    lambda kv: kv[-1] == mode_v, counter.most_common()
)

l2 = list((k for k, v in it))
l2.sort()
print(*l2)
### BUGGY CODE ###

N, K = map(int, input().split())
cnt = 0

for i in range(N):
  a = i+1
  for j in range(N):
    b = j+1
    if (a+b) % K == 0:
      for k in range(N):
        c = k+1
        if (b+c)%K==0 and (c+a)%K==0:
          cnt += 1

print(cnt)

### FIXED CODE ###

N, K = map(int, input().split())
 
if K % 2 == 1:
  print(pow(int(N / K), 3))
else:
  even = int(N / K)
  odd = int(N / int(K / 2)) - even
  print(pow(even, 3) + pow(odd, 3))
### BUGGY CODE ###

k,s = [int(n) for n in input().split()]
ac = 0
for x in range(k+1):
  if s-x <= 2*k:
    for y in range(k+1):
      if s-x-y <= k:
        for z in range(k+1):
          if x+y+z == s:
            ac += 1
print(str(ac))

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if 0<=z<=k:
            ans+=1
print(ans)
### BUGGY CODE ###

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

    def feelGood(table: list):
        pos = value = 0
        if len(table) == 0:
            return pos, value
        circle = table + [table[0]]
        for i in range(len(circle)-1):
            v = min(circle[i], circle[i+1])
            if (v > value):
                pos = i
                value = v
        return pos, value

    A.sort(reverse=True)
    table = []
    total = 0

    for i in A:
        pos, value = feelGood(table)
        table.insert(pos, i)
        total += value
    print(total)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import math

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

    A.sort()

    total = 0
    for i in range(1, N):
        total += A[N - 1 - math.floor(i/2)]
    print(total)

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

import sys
input=sys.stdin.readline

N,M = (int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
As = sorted(As)
for _ in range(M):
  d = As[-1]
  As[-1] = d//2
  As = sorted(As)
print(sum(As))

### FIXED CODE ###

import sys
input=sys.stdin.readline

N,M = (int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
As = sorted(As,reverse = True)
rest = M
for _ in range(M):
  if rest == 0:
    break
  d = As[0]
  b = d//2 - d//4
  for i in range(N):
    a = As[i]
    check = 0
    if a-a//2<b:
      if rest > i:
        ad = [x//2 for x in As[:i]]
        As = As[i:]
        As.extend(ad)
        rest -= i
        check += 1
        As = sorted(As,reverse = True)
        break
      else:
        ad = [x//2 for x in As[:rest]]
        As = As[rest:]
        As.extend(ad)
        check += 1
        rest = 0
        break
    if i == N-1:
      if check == 0:
        if rest > N:
          As = [x//2 for x in As]
          rest -= N
        else:
          ad = [x//2 for x in As[:rest]]
          As = As[rest:]
          As.extend(ad)
          rest = 0
          break
print(sum(As))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    def bit(n):
        b = [0] * 20

        for i in range(20, -1, -1):
            f = 2**i
            if n >= f:
                n -= f
                b[i] = 1

        return b

    # B = []
    BM = [[] for _ in range(20)]
    for j, a in enumerate(A):
        for i, b in enumerate(bit(a)):
            if b == 1:
                BM[i].append(j)

    error_print('-----')

    ans = N
    for i in range(0, N):
        min_r = sys.maxsize
        for bm in BM:
            c = 0
            r = sys.maxsize
            for b in bm:
                if b >= i:
                    c += 1
                if c > 1:
                    r = b - 1
                    break
            else:
                r = N - 1
            min_r = min_r if min_r < r else r
        ans += min_r - i
    return ans


def main():
    N = read_int()
    A = read_int_n()
    # N = 2 * 100000
    # A = [0] * N
    print(slv(N, A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import time
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ans = 0
    S = 0
    X = 0
    r = 0
    for l in range(N):
        while r != N and S + A[r] == X ^ A[r]:
            S += A[r]
            X ^= A[r]
            r += 1
        ans += r - l
        S -= A[l]
        X ^= A[l]

    return ans


def main():
    N = read_int()
    A = read_int_n()

    print(slv(N, A))


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

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n=INT()
    s=STR()
    r=s.count('R')
    g=s.count('G')
    b=s.count('B')
    ans=r*g*b
    #print(ans)
    for i in range(n+1):
        for j in range(1,n//2+2):
            k=i+2*j
            if k<=n-1:
                ch=set()
                ch.add(s[i])
                ch.add(s[i+j])
                ch.add(s[k])
                #print(ch)
                if len(ch)==3:
                    ans-=1
                    
    print(ans)

                
if __name__ == '__main__':
    do()

### FIXED CODE ###

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n=INT()
    s=STR()
    r=s.count('R')
    g=s.count('G')
    b=s.count('B')
    ans=r*g*b
    #print(ans)
    for i in range(n+1):
        for j in range(1,n//2+2):
            k=i+2*j
            if k<=n-1:
                #print(ch)
                if (s[i]!=s[i+j] and s[k]!=s[i+j] and s[i]!=s[k]):
                    ans-=1
                    
    print(ans)

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

#!/usr/bin/env python3

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    visited = [False for i in range(n)]
    color_used = [set() for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, color_used, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    for j in adjs[i]:
        if visited[j]:
            continue
        for c in range(1, 100005):
            if c in color_used[j]:
                continue
            if c in color_used[i]:
                continue
            color_used[i].add(c)
            color_used[j].add(c)
            mi = min(i, j)
            ma = max(i, j)
            colors[(mi, ma)] = c
            break
        dfs(j, adjs, visited, color_used, colors)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import random

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    for i in range(n):
        random.shuffle(adjs[i])
    visited = [False for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, -1, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    c = 1
    for j in adjs[i]:
        if visited[j]:
            continue
        if c == color_used:
            c += 1
        mi = min(i, j)
        ma = max(i, j)
        colors[(mi, ma)] = c
        dfs(j, adjs, visited, c, colors)
        c += 1

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

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    a,b,c,k = map(int,input().split())
    high=a
    middle=b
    low=c
    count=0

    while count<k:
        if abs(high-middle) >10**18:
            print("Unfair")
            exit()
        elif a == b == c:
            print(0)
            exit()
        high = b+c
        middle = a+c
        low = a+b
        a=high
        b=middle
        c=low
        count+=1
    print(high-middle) 
    

if __name__=="__main__":
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    a,b,c,k = map(int,input().split())

    if abs(a-b)>10**18:
        print("Unfair")
    elif k % 2==0:
        print(a-b)
    else:
        print(b-a) 

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

S=str(input())
Q=int(input())

Query=[]
for i in range(Q):
    Query.append(list(input().split()))
#print(Query)

for j in range(Q):
    if len(Query[j])==1:
        S=S[::-1]
        #print(S)
    else:
        if Query[j][1]=='1':
            S=Query[j][2]+S
            #print(S)
        else:
            S+=Query[j][2]
            #print(S)

print(S)

### FIXED CODE ###

S=str(input())
Q=int(input())

Query=[]
for i in range(Q):
    Query.append(list(input().split()))

N=len(S)//2
S_left_reverse=S[:N+1][::-1]
S_right=S[N+1:]
#print(S_left_reverse,S_right)


check=1
for j in range(Q):
    if len(Query[j])==1:
        check*=-1
        #print(S_left_reverse,S_right)
    else:
        if Query[j][1]=='1':
            if check==1:
                S_left_reverse+=Query[j][2]
                #print(S_left_reverse,S_right)
            else:
                S_right+=Query[j][2]
                #print(S_left_reverse,S_right)
        else:
            if check==1:
                S_right+=Query[j][2]
                #print(S_left_reverse,S_right)
            else:
                S_left_reverse+=Query[j][2]
                #print(S_left_reverse,S_right)


ans=S_left_reverse[::-1]+S_right
if check==1:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

# ソートしている(a < b < c)として，三角形の存在条件は以下になる
def triangle_check(a, b, c):
    if c < a + b:
        return True
    else:
        return False
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
cnt = 0
for i in range(N - 2):
    for k in range(i + 1, N - 1):
        for l in range(k + 1, N):
            if triangle_check(L[i], L[k], L[l]):
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

import bisect
# ソートしている(a < b < c)として，三角形の存在条件は以下になる
def triangle_check(a, b, c):
    if c < a + b:
        return True
    else:
        return False
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
cnt = 0
for i in range(N - 2):
    for k in range(i + 1, N - 1):
        tmp = bisect.bisect_left(L, L[i] + L[k])
        ans += max(tmp - 1 - k, 0)
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
def input():
  return sys.stdin.readline()[:-1]

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]<0 and S[data[0]-1][data[1]]=='.':
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]<0 and S[data[0]+1][data[1]]=='.':
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]<0 and S[data[0]][data[1]-1]=='.':
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]<0 and S[data[0]][data[1]+1]=='.':
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-1]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
    tmp=max([max(m[i]) for i in range(1, H+1)])
    if tmp>out:
      out=tmp
      
print(out)

### FIXED CODE ###

from collections import deque
import sys
def input():
  return sys.stdin.readline()[:-1]

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]==-2 and S[data[0]-1][data[1]]=='.':
    m[data[0]-1][data[1]]=-1
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]==-2 and S[data[0]+1][data[1]]=='.':
    m[data[0]+1][data[1]]=-1
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]==-2 and S[data[0]][data[1]-1]=='.':
    m[data[0]][data[1]-1]=-1
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]==-2 and S[data[0]][data[1]+1]=='.':
    m[data[0]][data[1]+1]=-1
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-2]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
      if data[2]>out:
        out=data[2]
      
print(out)
### BUGGY CODE ###

from collections import deque
N,M = map(int,input().split())
T = {}
for _ in range(N+M-1):
    a,b = map(int,input().split())
    if a not in T:
        T[a] = [[],[]]
    T[a][1].append(b)
    if b not in T:
        T[b] = [[],[]]
    T[b][0].append(a)
for i in range(1,N+1):
    if len(T[i][0])==0:
        rt = i
        break
dist = [-1 for _ in range(N+1)]
que = deque([(rt,0)])
dist[rt] = 0
while que:
    a,d = que.popleft()
    for x in T[a][1]:
        dist[x]=d+1
        que.append((x,d+1))
pa = {i:0 for i in range(1,N+1)}
for i in range(1,N+1):
    if i!=rt:
        for x in T[i][0]:
            if dist[x]==dist[i]-1:
                pa[i] = x
                break
for i in range(1,N+1):
    print(pa[i])

### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())
G = {i:[0,[]] for i in range(1,N+1)}
for _ in range(N+M-1):
    a,b = map(int,input().split())
    G[a][1].append(b)
    G[b][0] += 1
hist = [0 for _ in range(N+1)]
for i in range(1,N+1):
    if G[i][0]==0:
        cur = i
        break
que = deque([cur])
hist[cur] = 1
T = [-1 for _ in range(N+1)]
T[cur] = 0
while que:
    i = que.popleft()
    for j in G[i][1]:
        if hist[j]==0:
            G[j][0] -= 1
        if G[j][0]==0:
            que.append(j)
            T[j] = i
            hist[j] = 1
for i in range(1,N+1):
    print(T[i])
### BUGGY CODE ###

n = int(input())
D = sorted(list(map(int, input().split())))[::-1]
m = int(input())
T = sorted(list(map(int, input().split())))[::-1]
for t in T:
	for i, d in enumerate(D):
		if d <= t:
			D[i] = 0
			t -= d
			if t == 0:
				break
	if t:
		print("NO")
		exit()
else:
	print("YES")

### FIXED CODE ###

n = int(input())
D = list(map(int, input().split()))
m = int(input())
T = list(map(int, input().split()))

from collections import Counter
DC = Counter(D)
TC = Counter(T)
for k, v in TC.items():
	if v > DC[k]:
		print("NO")
		exit()
else:
	print("YES")
### BUGGY CODE ###

N = int(input())
S = list(input())

if '#' not in S or '.' not in S:
    ans = 0
else:
    ans = 2*10**5
    for i in range(N):
        ans = min(S[:i].count('#') + S[i:].count('.'), ans)

print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())

white = S.count('.')
black = 0
ans = white + black

for x in S:
    if x == '.':
        white -= 1
    else:
        black += 1
    ans = min(ans, white+black)

print(ans)