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

import sys
import  math
from heapq import *
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
A=nl()
A.sort(reverse=True)

mod=10**9+7
keta=[0]*60

for i in range(N):
    for j in range(60):    
        keta[j]+=((A[i]>>j)&1)

ans=0
for i in range(len(A)):
    keta_max=0
    for j in range(60):
        if(1<=(A[i]//(2**j))):
            keta_max=j+1
    for j in range(keta_max):
            if((A[i]>>j)&1):
                keta[j]-=1
                ans+=(2**j)*(len(A)-i-1-keta[j])
            else:
                ans+=(2**j)*keta[j]
            ans%=mod


print(ans%mod)

### FIXED CODE ###

import sys
import  math
from heapq import *
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
A=nl()
A.sort(reverse=True)

mod=10**9+7
keta=[0]*60

for i in range(N):
    for j in range(60):    
        keta[j]+=((A[i]>>j)&1)

ans=0

mod_div2=[0]*60
mod_div2[0]=1
for i in range(1,60):
    mod_div2[i]=(2*mod_div2[i-1])%mod
    
for i in range(len(A)):
    keta_max=0
    for j in range(60):
        if((A[i]>>j)&1):
            keta_max=j+1
    for j in range(keta_max):
            if((A[i]>>j)&1):
                keta[j]-=1
                ans+=mod_div2[j]*(len(A)-i-1-keta[j])
            else:
                ans+=mod_div2[j]*keta[j]
            ans%=mod


print(ans%mod)
### BUGGY CODE ###

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

ans = 1
for i in range(1, m//n +1):
  if m%(i) == 0:
    ans = i

print(ans)    

### FIXED CODE ###

from math import sqrt

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

ans = 1
for i in range(1, int(sqrt(m)+1)):
  if m % i == 0:
    if n * i <= m:
      ans = max(ans,i)
    if n * (m//i) <= m:
      ans = max(ans, m//i)
                           
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, L: "List[int]"):
    L = np.array(sorted(L))
    ct = 0
    for a in range(len(L)-2):
        for b in range(a+1, len(L)-1):
            ct+=(np.logical_and((L[b] < L[b:]),(L[b:] < L[a]+L[b]))).sum() 
            
    print(ct)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# import numpy as np
import bisect

def solve(N: int, L: "List[int]"):
    L = sorted(L)
    ct = 0
    for a in range(len(L)-2):
        a_ = L[a]
        for b in range(a+1, len(L)-1):
            b_in = bisect.bisect_left(L,a_+L[b]) - b -1
            if b_in > 0:
                ct+=b_in

            # print("L :{} a+Lb :{}  b_in:{}".format(L[b+1:],a_+L[b],ct))
        # ct += sum([bisect.bisect_left(L[b+1:],a_+L[b]) for b in range(a+1, len(L)-1)])
    print(ct)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, L)

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

import numpy as np

h, w, d = map(int, input().strip().split(" "))
a = np.array([[int(i) for i in input().strip().split(" ")] for _ in range(h)])
q = int(input().strip())
lr = [input().strip().split(" ") for _ in range(q)]
rs = []
cs = []
for i in range(h * w):
    r, c = np.where(a == i + 1)
    rs.append(r[0])
    cs.append(c[0])
rs_d = [rs[i::d] for i in range(d)]
cs_d = [cs[i::d] for i in range(d)]
costs = [
    np.cumsum(
        np.abs(np.array(_rs[1:]) - np.array(_rs[:-1])) +
        np.abs(np.array(_cs[1:]) - np.array(_cs[:-1]))) for _rs, _cs in zip(rs_d, cs_d)
]
for l, r in lr:
    l = int(l) - 1
    r = int(r) - 1
    if l == r:
        print(0)
    elif l < d:
        print(costs[r % d][r // d - 1])
    else:
        print(costs[r % d][r // d - 1] - costs[l % d][l // d - 1])


### FIXED CODE ###

import numpy as np

h, w, d = map(int, input().strip().split(" "))
a = [[int(i) for i in input().strip().split(" ")] for _ in range(h)]
q = int(input().strip())
lr = [input().strip().split(" ") for _ in range(q)]
rs = [None for _ in range(h * w)]
cs = [None for _ in range(h * w)]
for _r, _a in enumerate(a):
    for _c, __a in enumerate(_a):
        rs[__a - 1] = _r
        cs[__a - 1] = _c
rs_d = [rs[i::d] for i in range(d)]
cs_d = [cs[i::d] for i in range(d)]
costs = [
    np.cumsum(
        np.abs(np.array(_rs[1:]) - np.array(_rs[:-1])) +
        np.abs(np.array(_cs[1:]) - np.array(_cs[:-1]))) for _rs, _cs in zip(rs_d, cs_d)
]
for l, r in lr:
    l = int(l) - 1
    r = int(r) - 1
    if l == r:
        print(0)
    elif l < d:
        print(costs[r % d][r // d - 1])
    else:
        print(costs[r % d][r // d - 1] - costs[l % d][l // d - 1])
### BUGGY CODE ###

N,M=map(int,input().split())
l,r=[],[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:l.append([a,b])
    if b==N:r.append([a,b])
for i in l:
    for j in r:
        if i[1]==j[0]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

### FIXED CODE ###

N,M=map(int,input().split())
l,r=[0]*N,[0]*N
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        l[b-1]=1
    if b==N:
        r[a-1]=1
for i in range(N):
    if l[i]+r[i]==2:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

N = int(input())
S = [sorted(input()) for i in range(N)]

a = ["a" for i in range(N) for j in range(N-i-1) if S[i] == S[i+j+1]]
print(len(a))


### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
existed = {}
c = 0
for i in range(n):
  sorted_s = ''.join(sorted(s[i]))

  if sorted_s in existed:
    c += existed[sorted_s]
    existed[sorted_s] += 1
  else:
    existed[sorted_s] = 1
print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
import fractions
from functools import reduce

def gcd(*numbers):
    return abs(reduce(fractions.gcd, numbers))
ans = 0
for i in range(N):
    temp = A[:i] + A[i+1:]
    ans = max(ans, gcd(*temp))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
import fractions
from functools import reduce

def gcd(*numbers):
    return abs(reduce(fractions.gcd, numbers))

L = [A[0]]
R = [A[-1]]
A_R = A[::-1]
for i in range(1, N):
    L.append(fractions.gcd(L[-1], A[i]))
    R.append(fractions.gcd(R[-1], A_R[i]))
R = R[::-1]
ans = R[1]
R.append(0)
for i in range(N - 1):
    ans = max(ans, fractions.gcd(L[i],R[i+2]))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
N = input()
P = list(map(int, input().split(" ")))
count = 0
for i in range(len(P)):
    for j in range(i):
        if P[j] < P[i]:
            break
    else:
        count += 1
print(count)

### FIXED CODE ###

#!/usr/bin/env python3
N = input()
P = list(map(int, input().split(" ")))
count = 0
minimum = P[0]
for i in range(len(P)):
    if P[i] <= minimum:
        count += 1
        minimum = P[i]
print(count)
### BUGGY CODE ###

n = int(input())


def calc(c):
    g = 0
    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                if (x * x) + (y * y) + (z * z) + x * y + y * z + x * z == c:
                    g += 1
    return g


for i in range(n):
    print(calc(i))

### FIXED CODE ###

n = int(input())
a = [0] * (n + 1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            c = x * x + y * y + z * z + x * y + y * z + z * x
            if c <= n:
                a[c] +=1
            else:
                break
for i in a[1:]:
    print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    H,W=map(int,input().split())
    grid=[[_ for _ in input()] for _ in range(H)]
    ans=0
    for h in range(H):
        for w in range(W):
            if grid[h][w]=='.':
                cnt=1
                i=1
                while True:
                    if h+i<H and grid[h+i][w]=='.':
                        cnt+=1
                        i+=1
                    else:
                        break
                i=1
                while True:
                    if w+i<W and grid[h][w+i]=='.':
                        cnt+=1
                        i+=1
                    else:
                        break
                i=1
                while True:
                    if h-i>=0 and grid[h-i][w]=='.':
                        cnt+=1
                        i+=1
                    else:
                        break
                i=1
                while True:
                    if w-i >=0 and grid[h][w-i]=='.':
                        cnt+=1
                        i+=1
                    else:
                        break
                ans=max(ans,cnt)
    print(ans)



resolve()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    H, W = map(int, input().split())
    grid = [[_ for _ in input()] for _ in range(H)]

    l = [[0] * W for _ in range(H)]
    r = [[0] * W for _ in range(H)]
    u = [[0] * W for _ in range(H)]
    d = [[0] * W for _ in range(H)]

    for h in range(H):
        cur = 0
        for w in range(W):
            if grid[h][w] == '#':
                cur = 0
            else:
                cur += 1
            l[h][w] = cur

    for h in range(H):
        cur = 0
        for w in reversed(range(W)):
            if grid[h][w] == '#':
                cur = 0
            else:
                cur += 1
            r[h][w] = cur

    for w in range(W):
        cur = 0
        for h in range(H):
            if grid[h][w] == '#':
                cur = 0
            else:
                cur += 1
            u[h][w] = cur

    for w in range(W):
        cur = 0
        for h in reversed(range(H)):
            if grid[h][w] == '#':
                cur = 0
            else:
                cur += 1
            d[h][w] = cur

    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, r[h][w] + l[h][w] + u[h][w] + d[h][w] - 3)
    print(ans)


resolve()
### BUGGY CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

N=int(input())
tlist=list(map(int,input().split()))
vlist=list(map(int,input().split()))

def const(l,r,v,t):
  if t<l:
    return v+(l-t)
  elif r<t:
    return v+(t-r)
  else:
    return v
  
const_list=[(0,0,0)]
tsum=0
for i in range(N):
  l=tsum
  r=tsum+tlist[i]
  v=vlist[i]
  const_list.append((l,r,v))
  tsum+=tlist[i]
const_list.append((tsum,tsum,0))
#print(const_list)

sdic={}
t=0
while(t<=tsum):
  s=10**9
  for con in const_list:
    l,r,v=con
    s=min(s,const(l,r,v,t))  
  sdic[t]=s
  t+=0.5

answer=0
t=0
while(t<tsum):
  answer+=(sdic[t]+sdic[t+0.5])*0.5/2
  t+=0.5
  
print(answer)

### FIXED CODE ###

N=int(input())
tlist=list(map(int,input().split()))
vlist=list(map(int,input().split()))

def const(l,r,v,t):
  if t<l:
    return v+(l-t)
  elif r<t:
    return v+(t-r)
  else:
    return v
  
const_list=[(0,0,0)]
tsum=0
for i in range(N):
  l=tsum
  r=tsum+tlist[i]
  v=vlist[i]
  const_list.append((l,r,v))
  tsum+=tlist[i]
const_list.append((tsum,tsum,0))
#print(const_list)

answer=0
t=0
while(t<tsum):
  s1=s2=10**9
  for con in const_list:
    l,r,v=con
    s1=min(s1,const(l,r,v,t))
    s2=min(s2,const(l,r,v,t+0.5))
  #print(s1,s2)
    
  answer+=(s1+s2)*0.5/2
  t+=0.5
  
print(answer)
### BUGGY CODE ###

n=int(input())
hyou=[list(map(int,input().split())) for i in range(n-1)]

for i in range(n-1):
  syoki=hyou[i][0]+hyou[i][1]
  for j in range(i+1,n-1):
    temp=hyou[j][1]
    while temp<syoki:
      temp+=hyou[j][2]
    syoki=temp+hyou[j][0]
  print(syoki)
print(0)

### FIXED CODE ###

import math
n=int(input())
hyou=[list(map(int,input().split())) for i in range(n-1)]

for i in range(n-1):
  syoki=hyou[i][0]+hyou[i][1]
  for j in range(i+1,n-1):
    temp=hyou[j][1]
    if temp<syoki:
      syoki=temp+math.ceil((syoki-temp)/hyou[j][2])*hyou[j][2]+hyou[j][0]
    else:
      syoki=temp+hyou[j][0]
  print(syoki)
print(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(list(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase.append(a)
Abase=Abase*N
A=list(itertools.combinations(Abase,N))
A2=[sorted(x) for x in A]
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
A2=get_unique_list(A2)
ans=0
for i in A2:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(tuple(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase=Abase+[a]
A=set(itertools.combinations_with_replacement(Abase,N))
ans=0
for i in A:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)
### BUGGY CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N=int(input())
strings=[str(sorted(input())) for a in range(N)]
strings.sort()
sums=0
sorteds=strings
for st in list(set(sorteds)):
    n=sorteds.count(st)
    if n!=1:
       sums=sums+combinations_count(n,2)

print(sums)



### FIXED CODE ###

import math
import collections
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N=int(input())
strings=[str(sorted(input())) for a in range(N)]
c=collections.Counter(strings)
tp=c.most_common()
sums=0
for thing in tp:
    if thing[1]!=1:
        sums=sums+combinations_count(thing[1],2)
    else:break

print(sums)
### BUGGY CODE ###

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

k = 1
s = 0
count = 0


for i in range(n):
    if k in a:
        s = a.index(k)
        a = a[s:]
        k += 1
        count += 1
    else:
        break

if 1 in m:
    print(n-(k-1))
else:
    print(-1)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
 
j=1
for i in range(N):
    if j==A[i]:
        j+=1
 
if j==1:
  print(-1)
else:
  print(N-j+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from functools import lru_cache
MOD = 10 ** 9 + 7

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

@lru_cache(maxsize = None)
def dfs(v,color,p = -1):
    if color == 0:
        ans = 1
        for e in G[v]:
            if e == p:
                continue
            ans *= dfs(e,0,v) + dfs(e,1,v)
            ans %= MOD
        return ans
    else:
        ans = 1
        for e in G[v]:
            if e == p:
                continue
            ans *= dfs(e,0,v)
            ans %= MOD
        return ans

ans = (dfs(0,0) + dfs(0,1))%MOD
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7

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

dp = [[-1] * 2 for _ in range(N)]
def dfs(v,color,p = -1):
    if dp[v][color] != -1:
        return dp[v][color]
    if color == 0:
        ans = 1
        for e in G[v]:
            if e == p:
                continue
            ans *= dfs(e,0,v) + dfs(e,1,v)
            ans %= MOD
        dp[v][color] = ans
        return ans
    else:
        ans = 1
        for e in G[v]:
            if e == p:
                continue
            ans *= dfs(e,0,v)
            ans %= MOD
        dp[v][color] = ans
        return ans

ans = (dfs(0,0) + dfs(0,1))%MOD
print(ans)
### BUGGY CODE ###

N=int(input())
number=list(map(int,input().split()))
MOD = 1000000007
sum=0
for i in range(N-1):
    for j in range(i+1,N):
        sum+=number[i]*number[j]
print(sum%MOD)

### FIXED CODE ###

N=int(input())
number=list(map(int,input().split()))
MOD = 10**9+7
sum=sum(number)
s=sum%MOD
ans=0
for i in number:
    s-=i
    s%=MOD
    ans+=s*i
    ans%=MOD
print(ans)
### BUGGY CODE ###


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


x = 0

for i in range(len(L)):
    for j in range(i+1, len(L)):
        for k in range(j+1, len(L)):
            if (L[i] < L[j] + L[k]) and\
               (L[j] < L[k] + L[i]) and\
               (L[k] < L[i] + L[j]):
                   x += 1
        
print(x)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
l = sorted(l)

cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        up = l[j] + l[i]
        #l[k] = up となるようなkのうち最小のものを見つけろ
        k = bisect.bisect_left(l, up)
        cnt += k - j - 1
print(cnt)
### BUGGY CODE ###

from collections import Counter
from itertools import combinations

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

s = []
counter = Counter()
for c in S:
    if counter[c] > 3:
        continue
    s.append(c)

passwords = set()
for password in combinations(s, r=3):
    passwords.add(''.join(password))

print(len(passwords))


### FIXED CODE ###

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

count = 0
for i in range(1000):
    password = '{:03}'.format(i)
    s = S
    for j in range(3):
        index = s.find(password[j])
        if index == -1:
            break
        s = s[index + 1:]
    else:
        count += 1

print(count)
### BUGGY CODE ###

from collections import *
h,w=map(int,input().split())
a=[input() for _ in range(h)]
b=[[h*w]*w for _ in range(h)]
b[0][0]=1
d=deque([[0,0]])
while d:
    y,x=d.pop()
    for i,j in([1,0],[-1,0],[0,1],[0,-1]):
        t,u=y+i,x+j
        if 0<=t<h and 0<=u<w:
            if a[t][u]=="." and b[t][u]>b[y][x]:
                d.append([t,u])
                b[t][u]=b[y][x]+1
c=sum([i.count(".") for i in a])
print(max(-1,c-b[-1][-1]))

### FIXED CODE ###

from collections import *
h,w=map(int,input().split())
a=[input() for _ in range(h)]
b=[[h*w]*w for _ in range(h)]
b[0][0]=1
d=deque([[0,0]])
while d:
    y,x=d.pop()
    if y<h-1:
        if a[y+1][x]=="." and b[y+1][x]>b[y][x]+1:
            d.append([y+1,x])
            b[y+1][x]=b[y][x]+1
    if x<w-1:
        if a[y][x+1]=="." and b[y][x+1]>b[y][x]+1:
            d.append([y,x+1])
            b[y][x+1]=b[y][x]+1
    if y>0:
        if a[y-1][x]=="." and b[y-1][x]>b[y][x]+1:
            d.append([y-1,x])
            b[y-1][x]=b[y][x]+1
    if x>0:
        if a[y][x-1]=="." and b[y][x-1]>b[y][x]+1:
            d.append([y,x-1])
            b[y][x-1]=b[y][x]+1
c=sum([i.count(".") for i in a])
print(max(-1,c-b[-1][-1]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def prob_d(s, q):
    ans = s
    for i in range(q):
        ans = ope(ans)
    print(ans)

def reverse(s):
    return s[::-1]

def add_head(s, c):
    return c + s

def add_tail(s, c):
    return s + c

def ope(s):
    op = input().split()
    if len(op) == 1 and op[0] == '1':
        s = reverse(s)
    elif len(op) == 3 and op[0] == '2':
        if op[1] == "1":
            s = add_head(s, op[2])
        elif op[1] == "2":
            s = add_tail(s, op[2])
        else:
            pass
    else:
        pass
    return s

if __name__ == '__main__':
    s = input()
    q = int(input())
    prob_d(s, q)


### FIXED CODE ###

# -*- coding: utf-8 -*-

from collections import deque as dq

mode = True

def prob_d(s, q):
    ans = dq(s)
    for i in range(q):
        ans = ope(ans)
    if not mode:
        ans = ''.join(list(ans)[::-1])
    else:
        ans = ''.join(ans)
    print(ans)

def ope(s):
    global mode
    op = input().split()
    if len(op) == 1 and op[0] == '1':
        mode = not mode 
    elif len(op) == 3 and op[0] == '2':
        if op[1] == "1":
            if mode:
                s.appendleft(op[2])
            else:
                s.append(op[2])
        elif op[1] == "2":
            if mode:
                s.append(op[2])
            else:
                s.appendleft(op[2])
        else:
            pass
    else:
        pass
    return s

if __name__ == '__main__':
    s = input()
    q = int(input())
    prob_d(s, q)
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))

r = []
l = []

for i,j in enumerate(a):
    r.append(i+j)
    l.append(i-j)
    
ans = 0
for i in l:
    ans += r.count(i)
    
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))

r = []
l = []

for i,j in enumerate(a):
    r.append(i+j)
    l.append(i-j)
    
ans = 0
#Counterで{'要素':'個数'}の連想配列(辞書型)をつくり、そこから取り出す
b = Counter(r)
for i in l:
    ans += b.get(i,0)
    
print(ans)