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

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat.append((h, w, 0))
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    if dp[nH][nW] == ".":
        mat.append((nH, nW, cnt+1))
        dp[nH][nW] = "#"

while len(mat):
    h, w, cnt = mat.popleft()

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

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

N=int(input())
A=list(map(int,input().split()))
#print(N,A)
for i in range(N):
  print(A.index(i+1)+1,end="")
  if i!=N-1:
  	print(" ",end="")
print("")

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
#A=int(input().split())
#print(A)
B=[ 0 for _ in range(N)]
#print(B)
ans=""
for i in range(N):
  B[A[i]-1]=i+1
#  ans+=str(A.index(i+1)+1)
#  if i!=N-1:

for i in range(N):
  ans+=str(B[i])
  if i!=N-1:
    ans+=" "
#print(B)
print(ans)
### BUGGY CODE ###

import itertools
def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    ff = False
    r = n if r is None else r
    for indices in itertools.product(range(n), repeat=r):
        if len(set(indices)) == r:
            p = tuple(pool[i] for i in indices)
            for i in range(0, n):
                if i == 0:
                    ff = checkXOR(p[n-1],p[i],p[i+1])
                elif i == n-1:
                    ff = checkXOR(p[i-1],p[i],p[0])
                else:
                    ff = checkXOR(p[i-1],p[i],p[i+1])
                if ff:
                    break
        if ff:
            break
    return ff

def checkXOR(a, b, c):
    if bin(b) == bin(a ^ c):
        return False
    else:
        return True
    
n = int(input())
a = list(map(int, input().split()))
ff = permutations(a)
    
if ff:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

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

for i in range(n):
  aa = aa ^ a[i]

if aa == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

s=str(input())
t=str(input())
Ns=len(s)
Nt=len(t)
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
for i in range(1,Ns+1):
    for j in range(1,Nt+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]
print(dp[Ns][Nt])

### FIXED CODE ###

S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(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]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
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:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

class UnionFind(object):
  def __init__(self,n):
    *self.par,=range(n+1)
    self.rank=[0]*(n+1)

  def find(self,x):
    if self.par[x]==x:
      return x
    else:
      self.par[x]=self.find(self.par[x])
      return self.par[x]

  def union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if self.rank[x]<self.rank[y]:
      self.par[x]=y
    else:
      self.par[y]=x
      if self.rank[x]==self.rank[y]:
        self.rank[x]+=1

n=int(input())
x=[[0,0] for _ in range(n)]
y=[[0,0] for _ in range(n)]

for i in range(n):
  x[i][0],y[i][0]=map(int,input().split())
  x[i][1],y[i][1]=i+1,i+1

dx,dy=[],[]
x,y=sorted(x),sorted(y)
for i in range(n-1):
  dx.extend([(abs(x[i][0]-x[i+1][0]),x[i][1],x[i+1][1])])
  dy.extend([(abs(y[i][0]-y[i+1][0]),y[i][1],y[i+1][1])])

target=sorted(dx+dy)
tree=UnionFind(n)
cnt,cost,i=0,0,0

while cnt<n-1:
  c,a,b=target[i]
  if tree.find(a)!=tree.find(b):
    cost+=c
    tree.union(a,b)
    cnt+=1
  i+=1

print(cost)


### FIXED CODE ###

class UnionFind(object):
  def __init__(self,n):
    *self.par,=range(n+1)
    self.rank=[0]*(n+1)

  def find(self,x):
    if self.par[x]==x:
      return x
    else:
      self.par[x]=self.find(self.par[x])
      return self.par[x]

  def union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if self.rank[x]<self.rank[y]:
      self.par[x]=y
    else:
      self.par[y]=x
      if self.rank[x]==self.rank[y]:
        self.rank[x]+=1

n=int(input())
x=[[0,0] for _ in range(n)]
y=[[0,0] for _ in range(n)]

for i in range(n):
  x[i][0],y[i][0]=map(int,input().split())
  x[i][1],y[i][1]=i+1,i+1

dx,dy=[],[]
x,y=sorted(x),sorted(y)
for i in range(n-1):
  dx.extend([(abs(x[i][0]-x[i+1][0]),x[i][1],x[i+1][1])])
  dy.extend([(abs(y[i][0]-y[i+1][0]),y[i][1],y[i+1][1])])

target=sorted(dx+dy)
tree=UnionFind(n)
cnt,cost,i=0,0,0

while cnt<n-1:
  c,a,b=target[i]
  if tree.find(a)!=tree.find(b):
    cost+=c
    tree.union(a,b)
    cnt+=1
  i+=1

print(cost)
### BUGGY CODE ###

from collections import defaultdict

MOD = 10 ** 9 + 7

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

def factorize(n):
    res = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            n //= d
            res.append(d)
        d += 1
    if n > 1:
        res.append(n)
    return res

factors = []
for val in a:
    d = defaultdict(int)
    for factor in factorize(val):
        d[factor] += 1
    factors.append(d)
lcm = defaultdict(int)
for d in factors:
    for num, cnt in d.items():
        lcm[num] = max(lcm[num], cnt)

ret = 0
for i, d in enumerate(factors):
    val = 1
    for num, cnt in lcm.items():
        val *= pow(num, cnt - d[num], MOD)
        val %= MOD
    ret += val
    ret %= MOD
print(ret)

### FIXED CODE ###

from functools import reduce

MOD = 10 ** 9 + 7

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

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

def lcmArr(a):
    return reduce(getLcm, a)

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

lcm = lcmArr(a)
lcm %= MOD
ret = 0
for val in a:
    ret += lcm * pow(val, MOD - 2, MOD)
    ret %= MOD
print(ret)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
tmp=1
for i in range(k):
    tmp*=a[i]
for i in range(n-k):
    tmp1=tmp//a[i]*a[i+k]
    if tmp1>tmp:
        print("Yes")
        tmp=tmp1
    else:
        print("No")
        tmp=tmp1

### FIXED CODE ###

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

for i in range(n-k):
    tmp=a[i]
    tmp1=a[i+k]
    if tmp1>tmp:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N=int(input())
S=input()
dic={}
for i in range(N-2):
    if len(dic)==1000:
        break
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            tmp=S[i]+S[j]+S[k]
            dic[tmp]=1
print(len(dic))

### FIXED CODE ###

import sys
import copy
input = sys.stdin.readline

N=int(input())

S=input()


T=[[0] * 10 for _ in range(30000)]
for i in range(N):
    if i!=0:
        T[i]=copy.deepcopy(T[i-1])
    T[i][int(S[i])]+=1
#print(T)

dic={}
flag=[False]*10
for i in range(N-2):
    if flag[int(S[i])]==True:
        continue
    flag[int(S[i])]=True
    for j in range(i+1,N-1):
        tmp2=copy.deepcopy(T[N-1])
        tmp3=copy.deepcopy(T[j])
        tmp4=""
        for k in range(10):
            if tmp2[k]-tmp3[k]!=0:
                tmp4=S[i]+S[j]+str(k)
                #print(tmp4)
                if tmp4 in dic:
                    pass
                else:    
                    dic[tmp4]=1
           
print(len(dic))
#print(dic)
### BUGGY CODE ###

a,b,x=list(map(int, input().split()))

count=0
           
for i in range(a, b+1):
           if i%x==0:
            count+=1
           
        
print(count)

### FIXED CODE ###

def f(n, y):
    if n>=0: 
        return n//x + 1
    elif n==-1:
        return 0

a,b,x=list(map(int, input().split()))

count=f(b, x)-f(a-1,x)
        
print(count)
### BUGGY CODE ###

N=int(input())
S = input()
l, r = 0, N

def t(n):
  for i in range(0, N-n):
    s = S[i:i+n]
    if s in S[i+n:]:
      return True
  return False

while l+1<r:
  m = (l+r)//2
  if t(m):
    l=m
  else:
    r=m

print(l)

### FIXED CODE ###

import random
import string
N = int(input())
S = input()
l, r = 0, N

def pow_mod(a, b, m):
  ab = 1
  for _ in range(b):
    ab = (ab * a) % m
  return ab

def c2n(c):
  return ord(c) - 97

def hash(s, B, H):
  sh = 0
  for c in s:
    sh = (sh * B + c2n(c)) % H
  return sh

def t(n):
  B, H = 10 ** 8 + 7, 2 ** 64

  if n*2 > N:
    return False
  s, t = S[:n], S[n:n*2]
  sh, th = hash(s, B, H), hash(t, B, H)
  if sh == th:
    return True
  ss = set([sh])
  Bn = pow_mod(B, n, H)
  for i in range(0, N-2*n):
    sh = (sh * B - c2n(S[i]) * Bn + c2n(S[i+n])) % H
    th = (th * B - c2n(S[i+n]) * Bn + c2n(S[i+2*n])) % H
    ss.add(sh)
    if th in ss:
      return True
  return False

while l+1<r:
  m = (l+r)//2
  if t(m):
    l=m
  else:
    r=m

print(l)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
se = 1
for n in range(N):
  if A[n] == 0:
    se = 0
    break
  se *= A[n]
if se >  10**18:
  print("-1")
else:
  print(se)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
se = 1
c = True
for n in range(N):
  se *= A[n]
  if se >  10**18:
    c = False
    break
for n in range(N):
  if A[n] == 0:
    se = 0
    c = True
if c:
  print(se)
else:
  print("-1")
### BUGGY CODE ###

def furoshiki(i, w_limit):
    global treasures
    if not i or not w_limit:
        return (0, 0)

    v, w = treasures[i - 1]
    not_stole = furoshiki(i - 1, w_limit)
    if w_limit < w:
        return not_stole
    stole_v_total, stole_w_total = furoshiki(i - 1, w_limit - w)
    stole_v_total += v
    stole_w_total -= w
    return max(not_stole, (stole_v_total, stole_w_total))


case = 1
while True:
    w = int(input())
    if not w:
        break
    n = int(input())
    treasures = [None] * n
    for i in range(n):
        treasures[i] = tuple(map(int, input().split(',')))

    total_v, total_w = furoshiki(n, w)
    print('Case {}:'.format(case))
    print(total_v)
    print(-total_w)
    case += 1

### FIXED CODE ###

case = 1
while True:
    w_limit = int(input())
    if not w_limit:
        break
    n = int(input())
    treasures = [tuple(map(int, input().split(','))) for _ in range(n)]

    furoshiki = [0] * (w_limit + 1)
    for v, w in treasures:
        for j in range(w_limit, w - 1, -1):
            furoshiki[j] = max(furoshiki[j], furoshiki[j - w] + v)

    max_v = max_v_w = 0
    for w in range(w_limit + 1):
        if furoshiki[w] > max_v:
            max_v = furoshiki[w]
            max_v_w = w

    print('Case {}:'.format(case))
    print(max_v)
    print(max_v_w)
    case += 1
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
l = []
for i in range(n):
    if s[i] not in l:
        l.append(s[i])
print(len(l))

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
ss = set(s)
print(len(ss))
### BUGGY CODE ###

def main():   
    n = int(input())
    a = [input() for _ in range(n)]

    a_dict = {i:0 for i in set(a)}
    a_list = list(set(a))

    for i in a_list:
        a_dict[i] = a.count(i)

    ans = []
    max_value = max(a_dict.values())
    for key, value in a_dict.items():
        if value == max_value:
            ans.append(key)

    ans.sort()
    for i in ans:
        print(i)
main()

### FIXED CODE ###

n = int(input())

# 入力データ受取り時に、辞書に追加していくやり方
s_dict = {}
for i in range(n):
    s = input()    
    if s not in s_dict:
        s_dict[s] = 1
    s_dict[s] += 1

max_value = max(s_dict.values())
ans = []
for key, value in s_dict.items():
    if value == max_value:
        ans.append(key)

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

H,N=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

dp=[[0]*(H+1) for _ in range(N+1)]
dp[0]=[float("inf")]*(H+1)
dp[0][0]=0

for i in range(1,N+1):
  for j in range(1,H+1):
    if j-AB[i-1][0]>=0:
      dp[i][j]=min(dp[i][j-AB[i-1][0]]+AB[i-1][1],dp[i-1][j])
    else:
      dp[i][j]=min(AB[i-1][1],dp[i-1][j])
      
print(dp[N][H])

### FIXED CODE ###

H,N=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

dp=[[0]*(H+1) for _ in range(N+1)]
dp[0]=[float("inf")]*(H+1)
dp[0][0]=0

for i in range(1,N+1):
  for j in range(1,H+1):
    if j-AB[i-1][0]>=0:
      dp[i][j]=min(dp[i][j-AB[i-1][0]]+AB[i-1][1],dp[i-1][j])
    else:
      dp[i][j]=min(AB[i-1][1],dp[i-1][j])
      
print(dp[N][H])
### BUGGY CODE ###

A,B,C,K = map(int,input().split())


num_list = []

for a in range(A):
    num_list.append(1)

for b in range(B):
    num_list.append(0)

for c in range(C):
    num_list.append(-1)

ans_list = num_list[0:K]

ans = sum(ans_list)

print(ans)

### FIXED CODE ###

A,B,C,K = map(float,input().split())
 
a = min(A, K)
if K-A>=0:
    b = min(abs(K-A), B)
else:
    b = 0
    c = 0

if K-A-B>=0:
    c = min(abs(K-A-B), C)
else:
    c = 0

ans = 1*a + 0*b - 1*c

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

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
m_idx = A.index(max(A))

for _ in range(M):
    A[A.index(max(A))] //= 2

print(sum(A))

### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline
N, M = map(int, input().split())

A = []
for x in input().split():
    heapq.heappush(A, int(x) * (-1))

for _ in range(M):
    max_n = heapq.heappop(A) * (-1)
    heapq.heappush(A, (max_n // 2) * (-1))
    
print(sum(A) * (-1))
### BUGGY CODE ###

N, K = map(int, input().split())
S = []
for i in range(K):
    L, R = map(int, input().split())
    S += list(range(L, R+1))

dp = [0] * N
dp[0] = 1

S.sort()

for i in range(1, N):
    for s in S:
        if i - s < 0:break
        dp[i] = (dp[i] + dp[i - s]) % 998244353

print(dp[-1])


### FIXED CODE ###

mod = 998244353
N, K = map(int, input().split())

S = []
for i in range(K):
    L, R = map(int, input().split())
    S.append((L, R))

dp = [0] * (N+1)
dpsum = [0] * (N+1)
dp[1] = 1
dpsum[1] = 1

for i in range(2, N+1):
    for s in S:
        l = i - s[1]
        r = i - s[0]
        if r < 1:continue
        l = max(1, l)

        dp[i] += dpsum[r] - dpsum[l-1]
        dp[i] %= mod

    dpsum[i] = (dpsum[i-1] + dp[i]) % mod

print(dp[-1])
### BUGGY CODE ###

import itertools
import collections

H, W, N = map(int,input().split())
blacks = []
for i in range(N):
    blacks.append(tuple(map(int,input().split())))
square = [[0 for i in range(2,W)] for j in range(2,H)]
D = [(0,0), (-1,0), (-1,-1), (0,-1), (1,-1), (1,0), (1,1), (0,1), (-1,1)]

for b in blacks:
    for d in D:
        x = b[0] + d[0]
        y = b[1] + d[1]
        if 2<=x<=H-1 and 2<=y<=W-1: square[x-2][y-2] += 1
        else :continue

square_2d = list(itertools.chain.from_iterable(square))
for i in range(10):
    print(collections.Counter(square_2d)[i])



### FIXED CODE ###

from collections import Counter
import itertools

H, W, N = map(int,input().split())
blacks = []
for i in range(N):
    blacks.append(tuple(map(int,input().split())))

blacks_in_square = [(x+dx,y+dy) for x,y in blacks\
                    for dx in [-1,0,1] for dy in [-1,0,1]\
                    if 1 < x+dx < H and 1 < y+dy < W]

ans = [0] * 10
for x,y in Counter(Counter(blacks_in_square).values()).items():
    ans[x] = y
ans[0] = (H-2) * (W-2) - sum(ans)
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

from heapq import nsmallest


def add_list(s, t, new_lists, removals):
    l = t - s
    if l >= k:
        removals.extend(nsmallest(l - k + 1, aaa[s:t]))
        new_lists.append((s, t))


n, k, q = map(int, input().split())
aaa = list(map(int, input().split()))
srt = sorted(set(aaa))
lists = [(0, n)]
ans = float('inf')
for a in srt:
    new_lists = []
    removals = []
    for s, t in lists:
        for i, b in enumerate(aaa[s:t]):
            if a > b:
                add_list(s, s + i, new_lists, removals)
                s = s + i + 1
        add_list(s, t, new_lists, removals)
    if len(removals) < q:
        break
    ans = min(ans, nsmallest(q, removals)[-1] - a)
    lists = new_lists

print(ans)


### FIXED CODE ###

def add_list(buf, new_lists, removals):
    l = len(buf)
    if l >= k:
        sbf = sorted(buf)
        removals.extend(sbf[:l - k + 1])
        new_lists.append(buf)


n, k, q = map(int, input().split())
aaa = list(map(int, input().split()))
srt = sorted(aaa)
lists = [aaa]
ans = float('inf')
for a in srt:
    new_lists = []
    removals = []
    for lst in lists:
        buf = []
        for b in lst:
            if a > b:
                add_list(buf, new_lists, removals)
                buf = []
            else:
                buf.append(b)
        add_list(buf, new_lists, removals)
    if len(removals) < q:
        break
    removals.sort()
    ans = min(ans, removals[q - 1] - a)

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

from heapq import heapify, heappush, heappop, heapreplace
from collections import deque
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
D = deque([(0,0,0)])
F = set()
H = [0]
heapify(H)
k = 1
while D:
    p = D.popleft()
    if p in F:
        continue
    F.add(p)
    x, y, z = p
    d = A[x] + B[y] + C[z]
    if k < K:
        heappush(H, d)
        k += 1
    elif H[0] > d:
        continue
    else:
        heapreplace(H, d)
    if x < X - 1: D.append((x + 1, y, z))
    if y < Y - 1: D.append((x, y + 1, z))
    if z < Z - 1: D.append((x, y, z + 1))

print(*sorted(H, reverse=True), sep="\n")

### FIXED CODE ###

from heapq import heapify, heappush, heappop, heapreplace
import sys
input = sys.stdin.readline
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
D = [(-(A[0] + B[0] + C[0]), 0, 0, 0)]
heapify(D)
F = set()
for _ in range(K):
    p = heappop(D)
    d, x, y, z = p
    print(-d)
    if x < X - 1:
        p = (-(A[x + 1] + B[y] + C[z]), x + 1, y, z)
        if p not in F:
            heappush(D, p)
            F.add(p)
    if y < Y - 1:
        p = (-(A[x] + B[y + 1] + C[z]), x, y + 1, z)
        if p not in F:
            heappush(D, p)
            F.add(p)
    if z < Z - 1:
        p = (-(A[x] + B[y] + C[z + 1]), x, y, z + 1)
        if p not in F:
            heappush(D, p)
            F.add(p)
### BUGGY CODE ###

import sys
def solve():
	dss = [(".","."),(".","#"),("#","."),("#","#")]
	tmp_dss = []
	N = map(int,raw_input().split())
	for ds in dss:
		print "{0}\n{1}".format(*ds)
		sys.stdout.flush()
		if raw_input() == "T":
			tmp_dss.append(ds)
	ans = list(dss[0])
	dss = tmp_dss
	r_b = l_b = True
	while True:
		if r_b:
			for ds in dss:
				tmp = (ans[0] + ds[0],ans[1]+ds[1])
				print "{0}\n{1}".format(*tmp)
				sys.stdout.flush()
				res = raw_input()
				if res == "end": return
				if res == "T":
					ans = tmp
					break
			else:
				r_b = False
		if l_b:
			for ds in dss:
				tmp = (ds[0] + ans[0],ds[1] + ans[1])
				print "{0}\n{1}".format(*tmp)
				sys.stdout.flush()
				res = raw_input()
				if res == "end": return
				if res == "T":
					ans = tmp
					break
			else:
				l_b = False
solve()

### FIXED CODE ###

import sys
from collections import deque
def query(s1,s2):
	print "{0}\n{1}".format("".join(s1),"".join(s2))
	sys.stdout.flush()
	return raw_input()
def solve():
	dss = [(".","."),(".","#"),("#","."),("#","#")]
	tmp_dss = []
	N = map(int,raw_input().split())
	for ds in dss:
		res = query([ds[0]],[ds[1]])
		if res == "T": tmp_dss.append(ds)
	dss = tmp_dss
	s1 = deque(dss[0][0]); s2 = deque(dss[0][1]) 
	for _ in xrange(420):
		#right
		for ds1,ds2 in dss:
			s1.append(ds1); s2.append(ds2)
			res = query(s1,s2)
			if res == "end": return
			if res == "T": break
			s1.pop();s2.pop()
		else:
			break
	for _ in xrange(420):
		#left
		for ds1,ds2 in dss:
			s1.appendleft(ds1); s2.appendleft(ds2)
			res = query(s1,s2)
			if res == "end": return
			if res == "T": break
			s1.popleft();s2.popleft()
solve()
### BUGGY CODE ###

S = input()
lst = []
_sum = 0

for i in range(len(S)):
    _sum = (_sum + int(S[-1-i]) * 10**i % 2019) % 2019
    lst.append(_sum)
    
ans = lst.count(0)
for i in set(lst):
    c = lst.count(i)
    ans += c*(c-1)//2
    
print(ans)    



### FIXED CODE ###

from collections import Counter

S = [int(i) for i in input()]
S.reverse()
lst = []
_sum = 0

for i in range(len(S)):
    _sum = (_sum + S[i] * pow(10,i,2019)) % 2019
    lst.append(_sum)
    
C = Counter(lst)    
ans = C[0]

for i in C:
    ans += C[i]*(C[i]-1)//2
print(ans)
### BUGGY CODE ###

import numpy as np
h, w = map(int, input().split())
s = np.array([list(map(str, input().rstrip())) for _ in range(h)])

s = np.array([x == "." for x in s])

score_h = np.zeros([h, w], int)
score_w = np.zeros([w, h], int)

for i in range(h):
    tmp = 0
    for j in range(w):
        if not s[i, j]:
            tmp = 0
            continue
        else:
            tmp += 1
            score_h[i, j] = tmp

for i in range(h):
    for j in range(w - 1, 0, -1):
        if score_h[i, j] == 0 or score_h[i, j - 1] == 0:
            continue
        else:
            score_h[i, j - 1] = score_h[i, j]

s = s.T

for i in range(w):
    tmp = 0
    for j in range(h):
        if not s[i, j]:
            tmp = 0
            continue
        else:
            tmp += 1
            score_w[i, j] = tmp

for i in range(w):
    for j in range(h - 1, 0, -1):
        if score_w[i, j] == 0 or score_w[i, j - 1] == 0:
            continue
        else:
            score_w[i, j - 1] = score_w[i, j]

score_w = score_w.T

print((score_h + score_w - 1).max())

### FIXED CODE ###

import numpy as np
h, w = map(int, input().split())
arr = np.array([list(input()) for _ in range(h)]) == "."

l = np.zeros((h, w), dtype=int)
r = np.zeros((h, w), dtype=int)
u = np.zeros((h, w), dtype=int)
d = np.zeros((h, w), dtype=int)

for i in range(h):
    u[i] = (u[i - 1] + 1) * arr[i]
    d[- i - 1] = (d[- i] + 1) * arr[- i - 1]

for j in range(w):
    l[:, j] = (l[:, j-1] + 1) * arr[:, j]
    r[:, - j - 1] = (r[:, - j] + 1) * arr[:, - j - 1]

print(np.max(u + d + l + r) - 3)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
P = 10**9+7
for i in range(N-1):
    for j in range(i+1,N):
        ans += (A[i] ^ A[j])
        ans %= P
print(ans)

### FIXED CODE ###

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

ans = 0
P = 10**9+7
bit = [0 for i in range(70)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(70):
    ans += (2**i)*bit[i]*(N-bit[i])
    ans %= P

print(ans)