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

import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
x = eval('0b' + input())

memo = {}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

def solve(x, cnt):
    if x == 0:
        return cnt

    if x in memo:
        return cnt + memo[x]
    else:
        ans = solve(x % bin(x).count("1"), cnt + 1)
        memo[x] = ans - cnt
        return ans


ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y, 0))

for ansi in reversed(ans):
    print(ansi)


    

        


### FIXED CODE ###

from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)
### BUGGY CODE ###

#!/usr/bin/env python
# encoding: utf-8


class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """

    @staticmethod
    def swap(a, b):
        a, b = b, a
        return a, b

    def bubble_sort(self):
        # write your code here
        array_length = int(input())
        unsorted_array = [int(x) for x in input().split()]

        flag = 1
        count = 0
        while flag:
            flag = 0
            for j in range(array_length - 1, 0, -1):
                if unsorted_array[j] < unsorted_array[j - 1]:
                    self.swap(unsorted_array[j], unsorted_array[j - 1])
                    flag = 1
                    count += 1
        print(" ".join(map(str, unsorted_array)))
        print(str(count))


if __name__ == '__main__':
    solution = Solution()
    solution.bubble_sort()

### FIXED CODE ###

#!/usr/bin/env python
# encoding: utf-8


class Solution:

    @staticmethod
    def bubble_sort():
        # write your code here
        array_length = int(input())
        array = [int(x) for x in input().split()]

        flag, count, cursor = 1, 0, 0
        while flag:
            flag = 0
            for j in range(array_length - 1, cursor, -1):
                if array[j] < array[j - 1]:
                    array[j], array[j - 1] = array[j - 1], array[j]
                    flag = 1
                    count += 1
        cursor += 1
        print(" ".join(map(str, array)))
        print(str(count))


if __name__ == '__main__':
    solution = Solution()
    solution.bubble_sort()
### BUGGY CODE ###

from collections import deque
N = int(input())
X = str(input())
motosuji = int(X,2)
X = list(X)
motokosu = X.count("1")
only = float("inf")
if motokosu == 1:
  for i in range(N):
    if X[i] == "1":
      only = i
      break
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
pkosu = motokosu+1
mkosu = motokosu-1
P = deque([])
M = deque([])
ptemp = 1; mtemp = 1
for i in range(N):
  P.appendleft(ptemp%pkosu)
  ptemp = ptemp*2%pkosu
  if mkosu < 1:
    M.appendleft(0)
  else:
    M.appendleft(mtemp%mkosu)
    mtemp = mtemp*2%mkosu
#print(P,M,pkosu,mkosu)
for i in range(N): #i桁目を入れ替える
  if only == i:
    print(0)
    continue
  if X[i] == "0": #その桁が0なら1にする
    kosu = motokosu + 1
    suji = (motosuji + P[i])%kosu
  else: #その桁が1なら0にする
    kosu = motokosu - 1
    if kosu == 0:
      suji = -1
    else:
      suji = (motosuji - M[i])%kosu
    
  #print(suji,kosu)
  #if suji == 0:
  #  ans = 0
  if suji == -1:
    ans = 1
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
#print(2**17)
      
  

        

### FIXED CODE ###

from collections import deque
N = int(input())
X = str(input())
X = list(X)
#motokosu = X.count("1")
motokosu = 0
only = float("inf")
for i in range(N):
  if X[i] == "1":
    motokosu += 1
    only = i
if motokosu != 1:
  only = float("inf")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
pkosu = motokosu+1
mkosu = motokosu-1
P = deque([])
M = deque([])
ptemp = 1; mtemp = 1
for i in range(N):
  P.appendleft(ptemp%pkosu)
  ptemp = ptemp*2%pkosu
  if mkosu < 1:
    M.appendleft(0)
  else:
    M.appendleft(mtemp%mkosu)
    mtemp = mtemp*2%mkosu

pmotosuji = 0; mmotosuji = 0
for i in range(N):
  if X[i] == "1":
    pmotosuji = (pmotosuji+P[i])%pkosu
    if mkosu >= 1:
      mmotosuji = (mmotosuji+M[i])%mkosu
#print(P,M,pkosu,mkosu,pmotosuji,mmotosuji)

for i in range(N): #i桁目を入れ替える
  if only == i:
    print(0)
    continue
  if X[i] == "0": #その桁が0なら1にする
    kosu = motokosu + 1
    suji = (pmotosuji + P[i])%kosu
  else: #その桁が1なら0にする
    kosu = motokosu - 1
    if kosu == 0:
      suji = -1
    else:
      suji = (mmotosuji - M[i])%kosu
    
  #print(suji,kosu)
  #if suji == 0:
  #  ans = 0
  if suji == -1:
    ans = 1
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
#print(2**17)
#print(motokosu)
### BUGGY CODE ###

def t(n, a):
    return ' '.join([str(a.index(i) + 1) for i in range(1, n + 1)])


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    print(t(n, a))


### FIXED CODE ###

def t(a):
    return " ".join([str(j + 1) for i, j in sorted([(j, i) for i, j in enumerate(a)])])


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    print(t(a))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
S= list(input())
N = len(S)
cnt = 10**5

# dp(i,j) 最初jにいた子供がi回の移動後にいるマス
# dp(1,j) = j-1 or j+1
# dp(2,j) = dp(1, dp(1,j))
# dp(2,j) = dp(1, dp(1,j))

# dp(10^5, j) 1 <= j <= Nをもとめる

dp = [[0] * N for i in range(cnt + 1)]

for j in range(N):
    dp[0][j] = j
for i in range(cnt):
    for j in range(N):
        if S[dp[i][j]] == 'L':
            dp[i+1][j] = dp[i][j] - 1
        else:
            dp[i+1][j] = dp[i][j] + 1
# print(dp)
ans = [0] * N
for j in range(N):
    # print(dp[cnt][j])
    ans[dp[cnt][j]] += 1
print(' '.join([str(n) for n in ans]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
S= list(input())

isR = True
cnt_tmp = 0
cntList = []
for s in S:
    if s == 'R':
        if isR:
            cnt_tmp += 1
        else:
            cntList.append(cnt_tmp)
            isR = True
            cnt_tmp = 1
    else:
        if isR:
            cntList.append(cnt_tmp)
            isR = False
            cnt_tmp = 1
        else:
            cnt_tmp += 1

cntList.append(cnt_tmp)

ans = []

for i,cnt in enumerate(cntList):
    if i % 2 == 0:
        # R
        ans += [0] * (cnt - 1)
        q, mod = divmod(cnt, 2)
        ans += [q+mod, q]
    else:
        #L
        q, mod = divmod(cnt, 2)
        ans[len(ans)-2] += q
        ans[len(ans)-1] += (q+mod)
        ans += [0] * (cnt - 1)

print(' '.join([str(n) for n in ans]))
### BUGGY CODE ###

import collections

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

even_num=[v[i] for i in range(0,n,2)]
odd_num=[v[i] for i in range(1,n,2)]
#print(even_num)
#print(odd_num)

count_even=[(el, even_num.count(el)) for el in set(even_num)]
count_odd=[(el, odd_num.count(el)) for el in set(odd_num)]

count_even=sorted(count_even, key=lambda val:val[1], reverse=True)
count_odd=sorted(count_odd, key=lambda val:val[1], reverse=True)

#print(count_even)
#print(count_odd)
count_even.append((0,0))
count_odd.append((0,0))

if count_even[0][0]!=count_odd[0][0]:
    print(n-count_even[0][1]-count_odd[0][1])
else:
    odd_even=count_odd[0][1]+count_even[1][1]
    even_odd=count_even[0][1]+count_odd[1][1]
    if odd_even>even_odd:
        print(n-odd_num)
    else:
        print(n-even_odd)




### FIXED CODE ###

import collections

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

even_num=[v[i] for i in range(0,n,2)]
odd_num=[v[i] for i in range(1,n,2)]

count_even=collections.Counter(even_num).most_common()
count_odd=collections.Counter(odd_num).most_common()

#count_even.append((0,0))
#count_odd.append((0,0))

if count_even[0][0] != count_odd[0][0]:
    print(n-count_even[0][1]-count_odd[0][1])
elif len(count_even)==1 and len(count_odd)==1:
    print(n//2)
elif len(count_even)==1:
    print(n-count_odd[1][1])
elif len(count_odd)==1:
    print(n-count_even[1][1])
else:
    odd_even=count_odd[0][1]+count_even[1][1]
    even_odd=count_even[0][1]+count_odd[1][1]
    if odd_even>even_odd:
        print(n-odd_even)
    else:
        print(n-even_odd)
### BUGGY CODE ###

n = input()
n = int(n)
y = input()
list = y.split(' ')

for i in range(n):
    i = i + 1
    i = str(i)
    count = list.count(i)
    print(count)

### FIXED CODE ###

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

for i in a:
    nums[i-1] += 1

print("\n".join(map(str, nums)))
### BUGGY CODE ###

import math
n=int(input())
z=0
ans=0
for N in range(1,n+1):
    ans=0
    z=0
    for x in range(1,100):
        if x**2+x+x>=N:
            break
        for y in range(1,100):
            if x**2+y**2+x*y+x+y>=N:
                break
            #if (x+y)**2+4*N-4*(x**2+y**2)-4*x*y>=0:
            z=((-x-y)+math.sqrt((x+y)**2+4*N-4*(x**2+y**2)-4*x*y))/2
                #print(x,y,z)
            if z>=1 and z%1==0:
                ans+=1
                    #print(x,y,z)
    print(ans)

### FIXED CODE ###

n=int(input())
z=0
N=[0]*10000
ans=0
ko=0
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            ko=x**2+y**2+z**2+x*y+y*z+z*x
            if ko<=n:
                N[ko-1]+=1
            else:
                break
for i in range(n):
    print(N[i])
### BUGGY CODE ###

N = int(raw_input())
A = [map(int, raw_input().split(' ')) for n in xrange(N)]

answer = 0
for i in xrange(N):
  Ai = A[i]
  for j in xrange(i):
    Aj = A[j]
    Aij = Ai[j]
    no_other_route = 1
    for k in xrange(N):
      L = Ai[k] + Aj[k]
      if Aij >= L:
        if Aij > L:
          print -1
          exit()
        if k == i or k == j: continue
        no_other_route = 0
    answer += Aij * no_other_route

print answer

### FIXED CODE ###

N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  A[n][n] = 1000000001

answer = 0
for i in range(N):
  Ai = A[i]
  for j in range(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer
### BUGGY CODE ###

k=int(input())
queue=[i for i in range(1,10)]
for _ in range(k-1):
    x=queue.pop(0)
    if x%10 != 0:
        queue.append(10*x+x%10-1)
    queue.append(10*x+x%10)
    if x%10 != 9:
        queue.append(10*x+x%10+1)
print(queue[0])


### FIXED CODE ###

k=int(input())
queue=[i for i in range(1,10)]
if k <10:
    print(k)
else:
    l=0
    while l+9 < k:
        x=queue.pop(0)
        if x%10 != 0:
            queue.append(10*x+x%10-1)
            l+=1
        if l+9==k:
            break
        queue.append(10*x+x%10)
        l+=1
        if l+9==k:
            break
        if x%10 != 9:
            queue.append(10*x+x%10+1)
            l+=1
    print(queue[-1])
### BUGGY CODE ###

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

ans = []
count = 0
for i in range(N):
    for j in range(i, N):
        if (j == N - 1):
            ans.append(count)
            count = 0
            break
        if (H[j] < H[j + 1]):
            ans.append(count)
            count = 0
            break
        else:
            count += 1

print(max(ans))


### FIXED CODE ###

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

ans = []
count = 0
for j in range(N):
    if (j == N - 1):
        ans.append(count)
        count = 0
        break
    if (H[j] < H[j + 1]):
        ans.append(count)
        count = 0
        continue
    elif (H[j] >= H[j + 1]):
        count += 1

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

a,b,n=map(int,input().split())
x_kouho=[]
count=1
while count<=n//b:
  x_kouho.append(b*count-1)
  count+=1
if not x_kouho:
  x_kouho.append(n)

res=0
for i in range(0,len(x_kouho)):
  keep=x_kouho[i]
  kept=(a*keep)//b-a*(keep//b)
  if kept>res:
    res=kept
print(res)

### FIXED CODE ###

a,b,n=map(int,input().split())
x_kouho=[]
count=1
if b==1:
  res=0
else:
  while count<=n//b:
    x_kouho.append(b*count-1)
    count+=1
  if not x_kouho:
    x_kouho.append(n)

  res=0
  for i in range(0,len(x_kouho)):
    keep=x_kouho[i]
    kept=(a*keep)//b-a*(keep//b)
    if kept>res:
      res=kept
print(res)
### BUGGY CODE ###

import numpy as np
N=int(input())
for n in range(1,N+1):
  if n<6:
    print(0)
  else:
    la=np.arange(2,(n)**0.5)
    l=la*la
    c=0
    for x in range(len(l)):
      if l[x]*3>2*n:
        break
      else:
        for y in range(x,len(l)):
          if l[x]+2*l[y]>2*n:
            break
          else:
            for z in range(y,len(l)):
              if l[x]+l[y]+l[z]>2*n:
                break
              else:
                
                if l[x]+l[y]+l[z]==2*n:
                  
                  if (x+y+z)%2==0 and x+y+2>z:
                      if l[x]==l[y] and l[y]==l[z]:
                        c+=1
                      elif l[x]==l[y] or l[y]==l[z]:
                        c+=3
                      else:
                        c+=6
                   
    print(c)
    

### FIXED CODE ###

n=int(input())
dp=[0]*(10**5)
for x in range(1,10**2):
  for y in range(1,10**2):
    for z in range(1,10**2):
      dp[x**2+y**2+z**2+x*y+y*z+z*x]+=1
for i in range(n):
  print(dp[i+1])
### BUGGY CODE ###

H, W = map(int, input().split())
A = [None]*H
for i in range(H):
    A[i] = list(map(int, input().split()))
B = [None]*H
for i in range(H):
    B[i] = list(map(int, input().split()))

# C: A-Bの絶対値を持つ
C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

ans = 10**12

def DFS(v, route):# vは現在地
    global ans
    if v == (H-1,W-1):# goal
        res = cal_diff(route+[C[H-1][W-1]])
        # print(res)
        ans = min(ans, res)
    else:
        c = C[v[0]][v[1]]
        if v[0] < H-1:
            DFS((v[0]+1,v[1]), route+[c])
        if v[1] < W-1:
            DFS((v[0],v[1]+1), route+[c])

def cal_diff(route):
    res = 0
    route.sort(reverse=True)
    for r in route:
        if abs(res+r) <= abs(res-r):
            res += r
        else:
            res -= r
    return abs(res)

DFS((0,0),[])
print(abs(ans))

### FIXED CODE ###

H, W = map(int, input().split())
A = [None]*H
for i in range(H):
    A[i] = list(map(int, input().split()))
B = [None]*H
for i in range(H):
    B[i] = list(map(int, input().split()))

# C: A-Bの絶対値を持つ
C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

K = 80*(H+W-1)//2 + 1# 80*(H+W-1)の半分を超えるのは無駄
dp = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]# 答えから80*(H+W-1)を引く
dp[0][0][C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(K+1):
            if i and dp[i-1][j][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1
            if j and dp[i][j-1][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1

for k in range(K+1):
    res = dp[H-1][W-1][k]
    if res:
        print(k)
        break
### BUGGY CODE ###

N=int(input())
for i in range(1,N+1):
  count=0
  k=i//5+1
  for x in range(k):
    if(x==0):
      continue
    for y in range(k):
      if(y==0):
        continue
      for z in range(k):
        if(z==0):
          continue
        if((x+y)**2+(y+z)**2+(z+x)**2)//2==i:
          #print(x,y,z)
          #print(i)
          count+=1
  print(count)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
  for j in range(1,105):
    for k in range(1,105):
      v = i*i+j*j+k*k+i*j+j*k+k*i;
      if v<10050:
        ans[v]+=1
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

from bisect import insort_left
from sys import stdin

input = stdin.readline
n = int(input())

d = {}
m = 1
for i in range(n):
    s = input().rstrip()
    d.setdefault(s, 0)
    d[s] += 1
    if m < d[s]:
        m = d[s]

l = []
for i, j in d.items():
    if j == m:
        insort_left(l, i)
        
print("\n".join(l))


### FIXED CODE ###

from collections import Counter

n = int(input())

l = [input() for i in range(n)]

c = Counter(l)

ml = c.most_common()
mc = ml[0][1]

ml.sort()

for i in ml:
    if i[1] == mc:
        print(i[0])
### BUGGY CODE ###

N = int(input())
As = [int(x) for x in input().split()]
S = sum(As)

ans = None
for i in range(1,N):
    subs = sum(As[:i])
    temp = abs(2 * subs - S)
    if ans is None or temp < ans:
        ans = temp
print(ans)


### FIXED CODE ###

N = int(input())
As = [int(x) for x in input().split()]
S = sum(As)

ans = None
subsum = 0
for i in range(1,N):
    subsum += As[i-1]
    temp = abs(2 * subsum - S)
    if ans is None or temp < ans:
        ans = temp
print(ans)
### BUGGY CODE ###

N = int(input())
li = list(map(int,input().split()))
sum = 1
for i in range(N):
    sum = sum*li[i]
if sum > 10**18:
    print(-1)
else:
    print(sum)


### FIXED CODE ###

N = int(input())
li = list(map(int,input().split()))
if 0 in li:
    print(0)
else:
    sum = 1
    for i in range(N):
        sum = sum*li[i]
        if sum > 10**18:
            sum = -1
            break
    print(sum)
### BUGGY CODE ###

import sys
from math import factorial
input = sys.stdin.readline
N, M, K = map(int, input().split())
if M == 1:
    print(1 if K == N - 1 else 0)
else:
    res = 0
    for k in range(K + 1):
        # k個の○とN-k-1個の|を並べる順列
        punc = factorial(k + (N - k - 1)) // (factorial(k)
                                              * factorial(N - k - 1))
        color = M * ((M - 1)**(N - k - 1))
        res += punc * color
    print((res) % 998244353)

### FIXED CODE ###

import sys
from math import factorial
input = sys.stdin.readline
N, M, K = map(int, input().split())
MOD = 998244353
inv = [1] * N
FAC = factorial(N - 1) % MOD
if M == 1:
    print(1 if K == N - 1 else 0)
else:
    res = 0
    for i in range(1, N):
        inv[i] = (inv[i - 1] * pow(i, MOD - 2, MOD)) % MOD
    for k in range(K + 1):
        # k個の○とN-k-1個の|を並べる順列
        # punc = (N-1)!/k!/(N-k-1)!
        # punc = factorial(
        #     k + (N - k - 1)) // factorial(k) // factorial(N - k - 1)
        punc = FAC
        # punc *= pow(factorial(k), MOD - 2, MOD)
        punc *= inv[k]
        punc = punc % MOD
        # punc *= pow(factorial(N - k - 1), MOD - 2, MOD)
        punc *= inv[N - k - 1]
        punc = punc % MOD
        color = M * pow(M - 1, N - k - 1, MOD)
        res += ((punc % MOD) * color) % MOD
        res = res % MOD
    print(res % MOD)
### BUGGY CODE ###

H=int(input())
num=0
X=H
while True:
  X=H//2
  num+=1
  if X==0:
    break
print(2**num -1)


### FIXED CODE ###

H=int(input())
num=0
X=H
while True:
  X=X//2
  num+=1
  if X==0:
    break
print(2**num -1)
### BUGGY CODE ###

N=int(input())
S=list(input())
flag=1
count=0
for i in range(1000):
  numS=''
  flag=1
  if i<10:
    numS='00'+str(i)
  elif i<100:
    numS='0'+str(i)
  else:
    numS=str(i)
  for j in range(N):
    if numS[0]==S[j]:
      for k in range(j+1,N):
        if numS[1]==S[k]:
          if numS[2] in S[k+1:N]:
            count+=1
            flag=0
            break
        elif k==N and flag==1:
          flag=0
    if flag==0:
      break

print(count)

### FIXED CODE ###

N = int(input())
S = input()
s1 = set()
s2 = set()
s3 = set()

for i in S:
  for j in s2:
    s3.add(j+i)
  for k in s1:
    s2.add(k+i)
  s1.add(i)
print(len(s3))
### BUGGY CODE ###

from collections import defaultdict,deque
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(a-1,c-1)].add((a-1,-1))
  G0[(b-1,c-1)].add((b-1,-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    visited[(a,c)]=True
    for i in G0[(a,c)]:
      if not visited[i]:
        stack.appendleft((i[0],i[1],m))
    for i in G1[(a,c)]:
      if not visited[i]:
        stack.append((i[0],i[1],m+1))
  return -1

print(BFS(0))

      
    

### FIXED CODE ###

from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))
### BUGGY CODE ###

import math

s = input()
i = int(input())

isR = False
for _ in range(i):
    q = input().split(" ")

    if q[0] == "1":
        isR = not isR
    else:
        if isR:
            if q[1] == "1":
                s += q[2]
            else:
                s = q[2] + s
        else:
            if q[1] == "1":
                s = q[2] + s
            else:
                s += q[2]

if isR:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

import math

s = input()
i = int(input())

isR = False
head = []
tail = []

for _ in range(i):
    q = input().split(" ")

    if q[0] == "1":
        isR = not isR
    else:
        if isR:
            if q[1] == "1":
                tail.append(q[2])
            else:
                head.append(q[2])
        else:
            if q[1] == "1":
                head.append(q[2])
            else:
                tail.append(q[2])

ans = "".join(head[::-1]) + s + "".join(tail)

if isR:
    print(ans[::-1])
else:
    print(ans)