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

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

L = [0] * N
R = [0] * N
for m in range(M):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    
    for n in range(N):
        L[n] *= 2
        R[n] *= 2
        if n <= l:
            L[n] += 1   
        if n >= r:
            R[n] += 1


for _ in range(Q):
    p, q = map(int, input().split())
    
    print (bin(L[p - 1] & R[q - 1]).count("1"))

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def main():
    N, M, Q = read_values()
    S = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
    
    for _ in range(M):
        l, r = read_values()
        S[l][r] += 1

    for l in range(N):
        for r in range(N):
            S[l + 1][r + 1] += S[l + 1][r] + S[l][r + 1] - S[l][r] 

    res = [0] * Q
    for i in range(Q):
        p, q = read_values()
        res[i] = str(S[q][q] - S[p - 1][q] - S[q][p - 1] + S[p - 1][p - 1])
    print("\n".join(res))


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

N = int(input())

A = [int(i) for i in input().split()]

B = []

for j in range(1, N+1):
    temp = 0
    for i in A:
        if i == j:
            temp += 1
    print(temp)      


### FIXED CODE ###

import collections

N = int(input())

A = [int(i) for i in input().split()]

c = collections.Counter(A)

for i in range(1, N+1):
    print(c[i])
### BUGGY CODE ###

c,g=map(int,input().split())

import numpy as np

cd=np.array([1]*c)

for i in range(g):
	cd2=np.array([0]*c)
	st,ed=map(int,input().split())
	cd2[st-1:ed]=[1]*(ed-st+1) 
	cd=cd*cd2
    
print(sum(cd)) 

### FIXED CODE ###

c,g=map(int,input().split())

st=[]
en=[]

for i in range(g):
	s,e=map(int,input().split())
	st.append(s) 
	en.append(e)

res=min(en)-max(st)+1
print(max(res,0))
### BUGGY CODE ###

N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N
def solve_knapsack(capacity):
    # basic checks
    n = len(profits)
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, n):
        weights[i],profits[i] = map(int,input().split())
        for c in range(capacity, weights[i]-1, -1):
            tmp = profits[i] + dp[c - weights[i]]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

inp = input()
inp = inp.split()
N = int(inp[0])
M = int(inp[1])
BigM = N+2

E = []
for m in range(M):
    abinp = input()
    abinp = abinp.split()
    a = int(abinp[0])
    b = int(abinp[1])
    E.append(set([a,b]))

output = [0] + [0] + [BigM]*(N-1)
prev_cnt = 0
now = [1]

while len(now) > 0:
    n = now.pop(0)
    prev_cnt += 1
    for e in E:
        if n in e:
            next = list(e - set([n]))[0]
            if output[next] == BigM:
                output[next] = n
                now.append(int(next))

if prev_cnt == N:
    print("Yes")
    for n in range(2,N+1):
        print(output[n])
else:
    print("No")




### FIXED CODE ###

inp = input()
inp = inp.split()
N = int(inp[0])
M = int(inp[1])
BigM = N+2

E = []
for m in range(M):
    abinp = input()
    abinp = abinp.split()
    a = int(abinp[0])
    b = int(abinp[1])
    E.append([a,b])

# program
Edict = [[] for n in range(N+1)]
for e in E:
    Edict[e[0]].append(e[1])
    Edict[e[1]].append(e[0])

output = [0] + [0] + [BigM]*(N-1)
prev = [0 for n in range(N+1)]
prev_cnt = 0
now = [1]

prev[1] = 1
while len(now) > 0:
    n = now.pop(0)
    prev_cnt += 1
    for next in Edict[n]:
        if prev[next] == 0:
            output[next] = n
            now.append(next)
            prev[next] = 1

if prev_cnt == N:
    print("Yes")
    for n in range(2,N+1):
        print(output[n])
else:
    print("No")
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

sum_ = 0

for i in range(N):
    for j in range(i+1, N):
        sum_ += A[i] ^ A[j]

print(sum_ % (10**9 + 7))


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

# level_count = dict()
# for a in A:
#     bin_a = bin(a)
#     for i in range(len(bin_a[2:])):
#         if int(bin_a[-i-1]) == 1:
#             try:
#                 level_count[i] += 1
#             except:
#                 level_count[i] = 1
# 
# sum_ = 0
# for level, count in level_count.items():
#     sum_ += 2**level * count * (N - count)
# print(sum_ % (10**9 + 7))

import numpy as np

A = np.array(A)
sum_ = 0
for i in range(len(bin(np.max(A))) - 2):
    count = np.count_nonzero(A & 1)
    sum_ += 2**i * count * (N - count)
    A >>= 1
print(sum_ % (10**9 + 7))
### BUGGY CODE ###

K = int(input())
ans = 0


def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b
    else:
        return gcd(a, b % a)


for c in range(1, K+1):
    for b in range(1, K+1):
        for a in range(1, K+1):
            ans += gcd(gcd(a, b), c)
print(ans)


### FIXED CODE ###

K = int(input())
ans = 0


def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b
    else:
        return gcd(a, b % a)


for c in range(1, K+1):
    for b in range(1, K+1):
        for a in range(1, K+1):
            ans += gcd(gcd(a, b), c)
print(ans)
### BUGGY CODE ###

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

prime = [2]
for i in range(3, 10**5):
  flag = True
  for j in prime:
    if i % j == 0:
      flag = False
      break
  if flag:
    prime.append(i)

a_dict = dict()
b_dict = dict()

for i in prime:
  if a < i and b < i:
    break
  while a % i == 0:
    a /= i
    a_dict[i] = a_dict.get(i, 0) + 1
  while b % i == 0:
    b /= i
    b_dict[i] = b_dict.get(i, 0) + 1

ab = 1
for i in prime:
  ad = a_dict.get(i, 0)
  bd = b_dict.get(i, 0)
  n = ad if ad > bd else bd
  ab = ab * (i**n)
  
print(ab)

### FIXED CODE ###

import math
a, b = map(int, input().split())

prime = [2]
for i in range(3, 10**5, 2):
  flag = True
  for j in prime:
    if j > math.sqrt(i):
      break
    if i % j == 0:
      flag = False
      break
  if flag:
    prime.append(i)

a_dict = dict()
b_dict = dict()
used = set()

for i in prime:
  if a < i and b < i:
    break
  while a % i == 0:
    a /= i
    a_dict[i] = a_dict.get(i, 0) + 1
    used.add(i)
  while b % i == 0:
    b /= i
    b_dict[i] = b_dict.get(i, 0) + 1
    used.add(i)

ab = 1
for i in used:
  ad = a_dict.get(i, 0)
  bd = b_dict.get(i, 0)
  n = ad if ad > bd else bd
  ab = ab * (i**n)
  
print(ab)
### BUGGY CODE ###

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

mod = 10 ** 9 + 7
ans = 0

for k in range(n):
    A[k] = A[k] % mod

for j in range(n):
    for i in range(j):
        tmp = A[i]*A[j] % mod
        ans = (ans+tmp) % mod
print(ans)

### FIXED CODE ###

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

mod = 10 ** 9 + 7

summ = 0
quadsum = 0

for k in range(n):
    summ = (summ + A[k]) % mod
    quadsum = (quadsum + A[k]*A[k])%mod

ans = (summ*summ)%mod - quadsum
if ans % 2 == 1:
    ans += mod
ans = (ans/2)%mod
print(int(ans))
### BUGGY CODE ###

import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q=int(input())
arr=[list(map(int,input().split())) for _ in range(q)]
color=[0]*(n+1)
for i in range(q):
  v,d,c=arr[i]
  tmp=0
  tq=collections.deque()
  tq.append((v,0,c))
  checked=[0]*(n+1)
  checked[v]=1
  color[v]=c
  while 1:
    if len(tq)==0:
      break
    tv,td,tc=tq.popleft()
    if td>=d:
      break
    for u in g[tv]:
      if checked[u]==0:
        checked[u]=1
        color[u]=tc
        tq.append((u,td+1,tc))
for i in range(1,n+1):
  print(color[i])

### FIXED CODE ###

def dfs(i,v,d,c):
  if dp[v][d]==-1:
    dp[v][d]=i
    if d>0:
      dfs(i,v,d-1,c)
      for u in g[v]:
        dfs(i,u,d-1,c)
  
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q=int(input())
arr=[]
for i in range(q):
  v,d,c=map(int,input().split())
  arr.append((i,v,d,c))
dp=[[-1]*11 for _ in range(n+1)]
for i,v,d,c in arr[::-1]:
  dfs(i,v,d,c)
ans=[]
for i in range(1,n+1):
  if dp[i][0]==-1:
    ans.append(0)
  else:
    ans.append(arr[dp[i][0]][3])
for i in range(n):
  print(ans[i])
### BUGGY CODE ###

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

a=[]
#b=[]
for i in range(n):
    a.append([0]*(n))
    #b.append([0]*(n))

#import numpy as np
#b=np.array(b)
#print(a)
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    #a[(r-1):n,0:l]+=1
    for j in range(r-1,n):
        for k in range(l):
            a[j][k]+=1
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[r-1][l-1]+=1

for l in range(n):
    for r in range(l,n):
        temp=a[r][l]
        for i in range(r,n):
            for j in range(0,l+1):
                b[i][j]+=temp
        #b[r:n,0:l+1]+=temp
'''
#print(a)
#print(b)

for i in range(q):
    P,Q=map(int,input().split())
    print(a[(Q-1)][(P-1)])

### FIXED CODE ###

from itertools import accumulate
from operator import add, mul
n,m,q=map(int,input().split())

a=[]
b=[]
for i in range(n):
    a.append([0]*(n))
    b.append([0]*(n))

#import numpy as np
#b=np.array(b)
#print(a)
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    #a[(r-1):n,0:l]+=1
    for j in range(r-1,n):
        for k in range(l):
            a[j][k]+=1
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[l-1][r-1]+=1

#print(a)

for i in range(n):
    a[i]=list(accumulate(a[i]))

#print(a)

for i in range(n):
    for j in range(n-i-1):
        a[n-i-j-2][n-i-1]+=a[n-i-j-1][n-i-1]
        #print(a)

#print(a)

'''
for l in range(n):
    for r in range(l,n):
        temp=a[r][l]
        for i in range(r,n):
            for j in range(0,l+1):
                b[i][j]+=temp
        #b[r:n,0:l+1]+=temp
'''
#print(a)
#print(b)

for i in range(q):
    P,Q=map(int,input().split())
    print(a[(P-1)][(Q-1)])
'''
for i in range(que):
    p,q=MI()
    if p==1:
        ans=lis[q-1][q-1]
    else:
        ans=lis[q-1][q-1]-lis[p-2][q-1]
    print(ans)
'''
### BUGGY CODE ###

def search_index(x, sorted_ls):
    '''
    ソート済み配列からxの入る位置を返す and sorted_lsにxを挿入。
    xの入る位置が複数ある場合は一番左のindexを返す。
    '''
    n = len(sorted_ls)
    l = 0
    r = n
    while l != r:
        a = (r + l)//2
        if x <= sorted_ls[a]:
            r = a
        else:
            l = a + 1
    sorted_ls.insert(l, x)
    return l


N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 


res = 0
for i in range(N - 1, 0, - 1):
    j = search_index(P_id[i], A)
    l1 = A[j - 1]
    r1 = A[j + 1]
    if l1 != - 1:
        l2 = A[j - 2]
    else:
        l2 = l1
    if r1 != N:
        r2 = A[j + 2]
    else:
        r2 = r1
    
    if l1 == - 1:
        res += i*(A[j] + 1)*(r2 - r1)
    elif r1 == N:
        res += i*(l1 - l2)*(N - A[j])
    else:
        res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
print(res)

### FIXED CODE ###

import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)
### BUGGY CODE ###

def main():
    _, m = map(int, input().split())
    l = []
    w = a = 0
    D = {}
    for _ in range(m):
        n, j = input().split()
        if n not in D:
            D[n] = 0
        if n not in l:
            if j == "WA":
                D[n] += 1
            else:
                a += 1
                l += [n]
                w += D[n]
    print(a, w)

if __name__ == "__main__":
    main()

### FIXED CODE ###

d = [0]*10**5

a = set()
w = 0

for t in open(0):
    p, s = t.split()
    p = int(p)
    if "AC" == s and p not in a:
        w += d[p]
        a.add(p)
    if "WA" == s:
        d[p] += 1

print(len(a), w)
### BUGGY CODE ###

import heapq

n, m = map(int,input().split())
joblist = []
for i in range(n):
    a,b = map(int,input().split())
    joblist.append([a,b])
joblist.sort(key=lambda x :x[0])
kouho = []
 
ans =0
 
for i in range(1,m+1):
    count=0
    if joblist:
        for j,job in enumerate(joblist):
            if job[0]==i:
                
                heapq.heappush(kouho,(-1*job[1]))
                
                
            if job[0]!=i:
                if count:
                    for _ in range(count-1):
                        joblist.pop(0)
        if kouho:
            ans += -1*heapq.heappop(kouho)
 
print(ans)

### FIXED CODE ###

import heapq

n, m = map(int,input().split())
joblist = {}
for i in range(n):
    a,b = map(int,input().split())
    if a in joblist:
        joblist[a].append(-1*b)
    else:
        joblist[a] = [-1*b]

kouho = []
 
ans =0
 
for i in range(1,m+1):
    if i in joblist:
        for j in joblist[i]:
            heapq.heappush(kouho,j)
    if kouho:
        ans += heapq.heappop(kouho)
 
print(-1*ans)
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0

for i in range(1000):
    p100 = i // 100
    ki = i % 100
    p10  = ki // 10
    ki = ki % 10
    p1   = ki // 1
    flag1, flag2, flag3 = False, False, False
    for j in range(n):
        if (not flag1) and int(s[j]) == p100:
            flag1 = True
            continue
        if (not flag2) and flag1 and int(s[j]) == p10:
            flag2 = True
            continue
        if (not flag3) and flag1 and flag2 and int(s[j]) == p1:
            flag3 = True
            break
    if flag1 and flag2 and flag3:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
S = input()
ct = 0

for i in range(10):
    if str(i) in S:
        p = S.index(str(i))
        Si = S[p+1 :]
        for j in range(10):
            if str(j) in Si:
                q = Si.index(str(j))
                Sj = Si[q+1 :]
                for k in range(10):
                    if str(k) in Sj:
                        ct += 1
print(ct)
### BUGGY CODE ###

n=int(input())

sum=0
for i in range(len(str(n))):
    sum+=int(list(str(n))[i])

if sum%9==0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n=int(input())

sum=0
s=list(str(n))
for i in range(len(str(n))):
    sum+=int(s[i])

if sum%9==0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from functools import reduce
import collections 
import fractions
import math
import copy

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input().rstrip())
    A = list(int(_) for _ in input().split())
    ans = 0
    
    for i in range(N):
        A_tmp = copy.copy(A)
        A_tmp.pop(i)
        div_num = A_tmp[0]
        for j in range(1,N-1):
            div_num = fractions.gcd(div_num,A_tmp[j])
        ans = max(div_num,ans)

    print(ans)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

from functools import reduce
import collections 
import fractions
import math
import copy

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input().rstrip())
    A = list(int(_) for _ in input().split())
    ans = 0
    R = [0]*N
    R[0] = A[0]
    L = [0]*N
    L[N-1] = A[N-1]
    for i in range(1,N):
        R[i] = fractions.gcd(R[i-1],A[i])
    for i in range(N-1,0,-1):
        L[i-1] = fractions.gcd(L[i],A[i-1])        
    X = []
    for i in range(N):
        if i == 0:
            X.append(L[1])
        elif i == N-1:
            X.append(R[N-2])
        else:
            X.append(fractions.gcd(R[i-1],L[i+1]))
    print(max(X))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from bisect import bisect_left
H, W = map(int, input().split())
s = [input() for i in range(H)]

def length(index, block_idx, full_length):
    if len(block_idx) == 0:
        return full_length
    idx = bisect_left(block_idx, index)
    if idx == len(block_idx):
        return full_length - index
    return block_idx[idx] - index

rows = []

for i in range(H):
    row = [0 for k in range(W)]
    block_idx = []
    for k in range(len(s[i])):
        if s[i][k] == "#":
            block_idx.append(k)

    for j in range(W):
        if j == 0:
            if s[i][0] == "#":
                continue
            else:
                l = length(0, block_idx, W)
                row[j] = l
        else:
            if s[i][j] == "#":
                continue
            else:
                if s[i][j-1] != "#":
                    row[j] = row[j-1]
                else:
                    l = length(j, block_idx, W)
                    row[j] = l
    rows.append(row)

columns = []

for i in range(W):
    column = [0 for k in range(H)]

    _s = ""
    block_idx = []
    for k in range(H):
        _s += s[k][i]
        if s[k][i] == "#":
            block_idx.append(k)

    for j in range(H):
        if j == 0:
            if _s[0] == "#":
                continue
            else:
                l = length(0, block_idx, H)
                column[j] = l
        else:
            if _s[j] == "#":
                continue
            else:
                if _s[j - 1] != "#":
                    column[j] = column[j-1]
                else:
                    l = length(j, block_idx, H)
                    column[j] = l
    columns.append(column)

res = []
max_score = 0
for i in range(H):
    for j in range(W):
        r = rows[i][j]
        c = columns[j][i]
        score = r + c - 1
        if max_score < score:
            max_score = score
print(max_score)


### FIXED CODE ###


H, W = map(int, input().split())
s = [input() for i in range(H)]

l = [[0 for i in range(W)] for j in range(H)]
r = [[0 for i in range(W)] for j in range(H)]
d = [[0 for i in range(W)] for j in range(H)]
u = [[0 for i in range(W)] for j in range(H)]

# Up-Light
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            l[i][j] = 0
            u[i][j] = 0
            continue

        if j == 0:
            l[i][j] = 1
        else:
            l[i][j] = l[i][j-1] + 1

        if i == 0:
            u[i][j] = 1
        else:
            u[i][j] = u[i-1][j] + 1

# Right-Down
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if s[i][j] == "#":
            r[i][j] = 0
            d[i][j] = 0
            continue

        if j == W-1:
            r[i][j] = 1
        else:
            r[i][j] = r[i][j+1] + 1

        if i == H-1:
            d[i][j] = 1
        else:
            d[i][j] = d[i+1][j] + 1

max_score = 0
for i in range(H):
    for j in range(W):
        score = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        if score > max_score:
            max_score = score
print(max_score)
### BUGGY CODE ###

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

sum = 0
for i in range(n):
    for j in range(i + 1, n):
        sum += numbers[i] * numbers[j]
        sum %= (1000000000 + 7)
print(sum)

### FIXED CODE ###

n = int(input())
numbers = list(map(int, input().split()))
result = 0
sum_of_numbers = sum(numbers)
for i in range(n - 1):
    sum_of_numbers -= numbers[i]
    result += numbers[i] * sum_of_numbers
    result %= 1000000007
print(result)
### BUGGY CODE ###

X = input()
X = list(X)
prev = ""
for i in range(len(X) - 1):
    if X[i] + X[i + 1] == "ST":
        a = X.pop(i + 1)
        b = X.pop(i)
        X = [b,a]+X

for i in range(0, len(X)):
    if X[len(X) - (i+1)] == "T":
        print(i * 2)
        break

### FIXED CODE ###

X = input()
Y = []
for i in X:
    Y.append(i)
    if len(Y) > 1:
        if Y[-2] + Y[-1] == "ST":
            Y.pop()
            Y.pop()
print(len(Y))
### BUGGY CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
data = list(stdin.readline().rstrip().split()[0])

count = 0

c_list = [["R", "G", "B"], ["R", "B", "G"], ["G", "R", "B"], ["G", "B", "R"], ["B", "R", "G"], ["B", "G", "R"]]

for temp_list in c_list:
    for i in range(n):
        if data[i] != temp_list[0]:
            continue
        else:
            for j in range(i+1, n):
                if data[j] != temp_list[1]:
                    continue
                else:
                    for k in range(j+1, n):
                        if data[k] == temp_list[2]:
                            if (k - j) != (j - i):
                                count += 1
                                
print(count)

### FIXED CODE ###

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

R_cnt, G_cnt, B_cnt = 0, 0, 0

for i in range(len(S)):
    if S[i] == "R":
        R_cnt += 1
    elif S[i] == "G":
        G_cnt += 1
    else:
        B_cnt += 1

All = R_cnt * G_cnt * B_cnt

for i in range(N-2):
    for j in range(i+1, N-1):
        k = 2 * j - i
        if k >= N:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            All -= 1

print(All)
### BUGGY CODE ###

#ABC066C
n=int(input())
a=list(map(int, input().split()))
front=[]
back=[]
flg=n%2
for i in range(n//2):
    front.insert(0, a[2*i-flg+1])
    back.append(a[2*i+flg])
if flg==1:
    front.insert(0, a[n-1])
print(' '.join(map(str, front+back)))

### FIXED CODE ###

#ABC066C
n=int(input())
a=list(map(int, input().split()))
flg=n%2
half=n//2
front=[0]*(half+flg)
back=[0]*(half)
for i in range(half):
    front[half+flg-1-i]=a[2*i-flg+1]
    back[i]=a[2*i+flg]
if flg==1:
    front[0]=a[n-1]
print(' '.join(map(str, front+back)))