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

from sys import setrecursionlimit

setrecursionlimit(3 * 10 ** 5)

class Node:
  def __init__(self, id):
    self.id = id
    self.children = []
    self.block_id_set = set()

  def add_child(self, node):
    self.children.append(node)

  def add_block(self, id):
    self.block_id_set.add(id)


def main():
  n, m, k = map(int, input().split(' '))
  nodes = tuple([Node(i) for i in range(n)])
  for _ in range(m):
    a, b = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[a].add_child(nodes[b])
    nodes[b].add_child(nodes[a])

  for _ in range(k):
    c, d = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[c].add_block(d)
    nodes[d].add_block(c)

  total_done_set = set()

  def dfs(node, done_set):
    if node.id in done_set: return 0

    total_done_set.add(node.id)
    done_set.add(node.id)

    size = 1
    for child in node.children:
      size += dfs(child, done_set)

    return size


  ans_list = [-1] * n

  def dfs2(node, connected_ids, total_len):
    ans_list[node.id] = total_len - len(list(filter(
      lambda block_id: block_id in connected_ids,
      node.block_id_set
    ))) - 1

    except_num = 0
    for child in node.children:
      if child.id not in node.block_id_set:
        except_num += 1

      if ans_list[child.id] == -1:
        dfs2(child, connected_ids, total_len)

    ans_list[node.id] -= except_num


  for base_node in nodes:
    if base_node.id not in total_done_set:
      done_set = set()
      dfs(base_node, done_set)
      dfs2(base_node, done_set, len(done_set))

  print(*ans_list, sep=" ")


main()


### FIXED CODE ###

from sys import setrecursionlimit

setrecursionlimit(3 * 10 ** 5)

def main():
  n, m, k = map(int, input().split(' '))
  nodes = tuple([([], set()) for i in range(n)])
  for _ in range(m):
    a, b = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[a][0].append(b)
    nodes[b][0].append(a)

  for _ in range(k):
    c, d = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[c][1].add(d)
    nodes[d][1].add(c)

  total_done_set = set()

  def dfs(node_id, done_set):
    if node_id in done_set: return 0

    total_done_set.add(node_id)
    done_set.add(node_id)

    size = 1
    for child_id in nodes[node_id][0]:
      size += dfs(child_id, done_set)

    return size


  ans_list = [-1] * n

  def dfs2(node_id, connected_ids, total_len):
    children, block_id_set = nodes[node_id]
    ans_list[node_id] = total_len - len(list(filter(
      lambda block_id: block_id in connected_ids, block_id_set
    ))) - 1

    except_num = 0
    for child_id in children:
      if child_id not in block_id_set:
        except_num += 1

      if ans_list[child_id] == -1:
        dfs2(child_id, connected_ids, total_len)

    ans_list[node_id] -= except_num


  for i in range(n):
    if i not in total_done_set:
      done_set = set()
      dfs(i, done_set)
      dfs2(i, done_set, len(done_set))

  print(*ans_list, sep=" ")


main()
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    lrds = ((map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))
        g[r].append((l, -d))

    while None in x:
        inone = x.index(None)
        stack = [inone]
        x[inone] = 0
        while len(stack) > 0:
            v = stack.pop()
            for u, d in g[v]:
                if not x[u]:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    lrds = ((map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))
        g[r].append((l, -d))

    for i in range(n):
        if x[i] is not None:
            continue
        stack = [i]
        x[i] = 0
        while len(stack):
            v = stack.pop()
            for u, d in g[v]:
                if x[u] is None:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

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

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

flag = 1
for i in range(len(h)-1):
    for j in range(i+1,len(h)):
        if(h[i]-h[j]>=2):
            print("No")
            flag=0
            break
    if(flag==0):
        break
            
if(flag==1):
    print("Yes")

### FIXED CODE ###

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

flag = 1
temp = h[0]
for i in range(len(h)-1):
    if(temp<h[i]):
        temp = h[i]
    if(temp-h[i+1]>=2):
        print("No")
        flag=0
        break
            
if(flag==1):
    print("Yes")
### BUGGY CODE ###

n = int(input())
l, s = list(""), list("")
for i in range(n):
    l.append(input())
s = list(set(l))
max = 0
a = list("")
for i in range(len(s)):
    if l.count(s[i]) > max:
        max = l.count(s[i])
        a.clear()
        a.append(s[i])
    elif l.count(s[i]) == max:
        a.append(s[i])
a.sort()
for i in range(len(a)):
    print(a[i])

### FIXED CODE ###

from collections import Counter

n = int(input())
l = list("")
for i in range(n):
    l.append(input())
c = Counter(l)
c = c.most_common()
max = c[0][1]
a = list("")
for i in range(len(c)):
    if c[i][1] == max:
        a.append(c[i][0])
    else:
        break
a.sort()
for i in range(len(a)):
    print(a[i])
### BUGGY CODE ###

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

FRIEND = [[0]*n for _ in range(n)]
BLOCK = [[0]*n for _ in range(n)]

for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    FRIEND[a][b] = FRIEND[b][a] = 1

for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    BLOCK[a][b] = BLOCK[b][a] = 1



def make_dfs():
    visited = [0] * n

    def inner(v):
        visited[v] = 1
        for v2 in range(n):
            if not FRIEND[v][v2]:
                continue
            if visited[v2]:
                continue
            inner(v2)
        return visited
    return inner


ans = [-1]*n

for i in range(n):
    friends = FRIEND[i]

    dfs = make_dfs()
    possibly_friends = dfs(i)
    blocks = BLOCK[i]

    for f, pf, b in zip(friends, possibly_friends, blocks):
        if pf and (not f) and (not b):
            ans[i] += 1

print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        self.c = None

    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)

ab = []
for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    ab.append((a, b))
    uf.union(a, b)

cd = [list(map(lambda x: int(x)-1, input().split())) for _ in range(k)]
ans = [uf.count_member(i)-1 for i in range(n)]

for a, b in ab:
    if uf.find(a) == uf.find(b):
        ans[a] -= 1
        ans[b] -= 1

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

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

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

# check
for i in range(K):
    if A >= 1:
         A -= 1
    elif B >= 1:
         B -= 1
    else:
        continue

print(A, B)

### FIXED CODE ###

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

# check
if A + B > K >= A:
    K -= A
    A = 0
    B -= K
elif A + B <= K:
    A, B = 0, 0
else:
    A -= K

print(A, B)
### BUGGY CODE ###

s=input()
q=int(input())
ql=[]

for _ in range(q):
    ql.append(list(map(str,input().split())))
flg=True #正順
for qi in ql:
    # qi=list(map(str,input().split()))
    if qi[0]=="1":
        flg=not flg
    else:
        f,c=qi[1],qi[2]
        if f=="1":
            if flg:
                s=c+s
            else:
                s=s+c
        else:
            if not flg:
                s=c+s
            else:
                s=s+c
                

if flg:
    s=s
else:
    s=s[::-1]
    
print(s)




### FIXED CODE ###

s=input()
q=int(input())
l=""
r=""
flg=True

for i in range(q):
    p=list(map(str,input().split()))
    if p[0]=="1":
        flg=not flg
    else:
        z,f,c=p
        if f=="1":
            if flg:
                l=c+l
            else:
                r=r+c
        else:
            if not flg:
                l=c+l
            else:
                r=r+c
s=l+s+r

if flg:
    ans=s
else:
    ans=s[::-1]
print(ans)
### BUGGY CODE ###

N = int(input())

A = []
for i in range(N):
    A.append(int(input()))

import copy

for i in range(N):
    _tmp = copy.copy(A)
    _tmp.pop(i)
    print(max(_tmp))

### FIXED CODE ###

N = int(input())

A = []
for i in range(N):
    A.append(int(input()))

_A = sorted(A)

list_max = _A[N-1]
list_second_max = _A[N-2]

import copy

for i in range(N):
    if A[i] != list_max:
        print(list_max)
    else:
        print(list_second_max)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
N, Q = map(int, input().split(' '))

tree = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
memo = [0] * (N)
for i in range(Q):
    p, x = map(int, input().split(' '))
    p -= 1
    memo[p] += x


def dfs(v, par):
    for i in tree[v]:
        if i == par:
            continue
        memo[i] += memo[v]
        dfs(i, v)


dfs(0, -1)

print(*memo)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

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

memo = [0] * n

for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    memo[p] += x

def dfs(v, par):
    for nv in g[v]:
        if nv == par:
            continue
        memo[nv] += memo[v]
        dfs(nv, v)

dfs(0, -1)

print(*memo)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
H = LIST()
I = []

if N == 1:
  print(0)
  exit()

for i in range(N):
  c = 0
  j = 0
  while j < N-i-1 and H[i+j] >= H[i+j+1] :
    c += 1
    j += 1
    
  I.append(c)
  
    
print(int(max(I)))
    

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
H = LIST()
I = []

if N == 1:
  print(0)
  exit()
  
i = 0
 
while i < N :
  c = 0
  j = 0
  while j < N-i-1 and H[i+j] >= H[i+j+1] :
    c += 1
    j += 1
    
  I.append(c)
  i += c+1
  
print(int(max(I)))
### BUGGY CODE ###

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = [0]*(n+1)
d = [0]*(m+1)
for i in range(n):
    c[i+1] = a[i]+c[i]
for i in range(m):
    d[i+1] = b[i]+d[i]
ans = 0
for i in range(n+1)[::-1]:
    for j in range(m+1)[::-1]:
        if c[i] + d[j] <= k:
            ans = max(ans,i+j)
            break
print(ans)

### FIXED CODE ###

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = [0]*(n+1)
d = [0]*(m+1)
for i in range(n):
    c[i+1] = a[i]+c[i]
for i in range(m):
    d[i+1] = b[i]+d[i]
for i in range(m+1)[::-1]:
    if d[i] <= k:
        x = i
        break
ans = x
for i in range(1,n+1):
    while c[i] + d[x] > k:
        if x >= 1:
            x -= 1
        else:
            break
    if c[i] + d[x] <= k:
        ans = max(ans,i+x)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from bisect import bisect
inpl = lambda: list(map(int, input().split()))

N = int(input())
X = inpl()
L = int(input())
Q = int(input())
R = {}

for i in range(N):
    R[(0, i)] = bisect(X, X[i]+L) - 1

for k in range(17):
    for i in range(N):
        R[(k+1, i)] = R[(k, R[(k, i)])]


def reach(a, d):
    O = format(d, "b").zfill(18)[::-1]
    for k in range(17, -1, -1):
        if O[k] == "1":
            a = R[(k, a)]
    return a


def bisearch(a, b):
    a, b = a-1, b-1
    if b < a:
        a, b = b, a
    OK = 2**17
    NG = 0

    while abs(OK - NG) > 1:
        mid = (OK+NG)//2
        if reach(a, mid) >= b:
            OK = mid
        else:
            NG = mid
    return OK

print(*[bisearch(*inpl()) for _ in range(Q)], sep="\n")

### FIXED CODE ###

from bisect import bisect
inpl = lambda: list(map(int, input().split()))

N = int(input())
X = inpl()
L = int(input())
Q = int(input())
R = [[0]*(N) for k in range(17)]

for i in range(N):
    R[0][i] = bisect(X, X[i]+L) - 1

for k in range(16):
    for i in range(N):
        R[k+1][i] = R[k][R[k][i]]


def reach(a, d):
    O = format(d, "b").zfill(17)[::-1]
    for k in range(16, -1, -1):
        if O[k] == "1":
            a = R[k][a]
    return a


def bisearch(a, b):
    a, b = a-1, b-1
    if b < a:
        a, b = b, a
    OK = b-a
    NG = 0

    while abs(OK - NG) > 1:
        mid = (OK+NG)//2
        if reach(a, mid) >= b:
            OK = mid
        else:
            NG = mid
    return OK

print(*[bisearch(*inpl()) for _ in range(Q)], sep="\n")
### BUGGY CODE ###

import sys
#input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}
for a in A :
    D[a] += 1

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

def f(c1, c2, c3) :
    res = N
    if (c1 > 0) :
        res += dp[c1-1][c2][c3] * c1
    if (c2 > 0) :
        res += dp[c1+1][c2-1][c3] * c2
    if (c3 > 0) :
        res += dp[c1][c2+1][c3-1] * c3
    
    res /= (c1 + c2 + c3)
    dp[c1][c2][c3] = res

for k in range(D[3]+1) :
    for j in range(D[2]+D[3]+1 - k) :
        for i in range(D[1]+D[2]+D[3]+1 - (j+k)) :
            if i+j+k == 0 :
                continue
            f(i, j, k)

ans = dp[D[1]][D[2]][D[3]]

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}
for a in A :
    D[a] += 1

one = D[1]
two = D[2]
three = D[3]

dp = [[[0.0]*(N+1) for j in range(N+1)] for i in range(N+1)]

def f(c1, c2, c3) :
    res = N
    if (c1 > 0) :
        res += dp[c1-1][c2][c3] * c1
    if (c2 > 0) :
        res += dp[c1+1][c2-1][c3] * c2
    if (c3 > 0) :
        res += dp[c1][c2+1][c3-1] * c3
    
    dp[c1][c2][c3] = res/(c1 + c2 + c3)

for k in range(three+1) :
    for j in range(two+three+1 - k) :
        for i in range(one+two+three+1 - (j+k)) :
            if i+j+k == 0 :
                continue
            f(i, j, k)

print(dp[one][two][three])
### BUGGY CODE ###

import itertools
N, M, Q = map(int, input().split())
m = list()
res = -100
for i in range(Q):
    n = list(map(int, input().split()))
    m.append(n)
l = [x for x in range(1, M + 1)]
p = itertools.combinations_with_replacement(l, N)
for p in p:
    total = 0
    for i in range(Q):
        num = 0
        a = m[i][0]
        b = m[i][1]
        A = p[a - 1]
        B = p[b - 1]
        C = B - A
        if m[i][2] == C:
            num = num + m[i][3]
            total = total + num
    if res < total:
        res = total
print(res)


### FIXED CODE ###

import math
import itertools

N, M, Q = map(int, input().split())
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q
for i in range(Q):
    a[i], b[i], c[i], d[i] = map(int, input().split())
Al = [0]*M
for i in range(M):
    Al[i] = i + 1
All = list(itertools.combinations_with_replacement(Al, N))

ans = 0

for A in All:
    wa = 0
    for i in range(Q):
        kari = A[b[i]-1] - A[a[i] - 1]
        if kari == c[i]:
            wa = wa + d[i]
    if ans < wa:
        ans = wa
print(ans)
### BUGGY CODE ###

def f(n,m):
     a = list(map(int,input().split()))
     min_a = min(a)
     for i in range(m):
          b,c = map(int,input().split())
          if c>min_a:
               a += [c]*b
     a.sort(reverse=True)
     print(sum(a[:n]))

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

### FIXED CODE ###

def f(n,m):
     a = list(map(int,input().split()))
     min_a = min(a)
     a = [(1,i) for i in a]
     b_c = [tuple(map(int,input().split())) for i in range(m)]
     a += b_c
     a.sort(key=lambda x:x[1])
     ans = 0
     while True:
          if n>a[-1][0]:
               ans += a[-1][0]*a[-1][1]
               n -= a[-1][0]
               a.pop()
          else:
               ans += a[-1][1]*n
               break
     print(ans)

n,m = map(int,input().split())
f(n,m)
### BUGGY CODE ###

from  heapq import heappush, heappop, heapify

n,m,s,t=map(int,raw_input().split())

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#print nl

v=2


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while len(Q)>0:
		u=heappop(Q)
		for v,yen,snuuk in nl[u]:
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+snuuk

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

D=[]

for i in range(1,n+1):
	D.append( (d_y[i]+d_s[i], i ) ) 



D.sort(key=lambda x: x[0])


t=1
for x,N in D:
	for j in range(t,N+1):
		#print j,x
		print 10**15-x
		t+=1
		if t==n+1:
			quit()
	


### FIXED CODE ###

import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)
### BUGGY CODE ###

from functools import reduce

A,B= (int(i) for i in input().split()) 

a = [0]*len(format(B,"b"))
b=[]

for i in range(A, B+1):
	bi = format(i, "b")
	l = [int(x) for x in list(str(bi))]
	for g in range(1, len(l)+1):
		a[-g]+=l[-g]

for n in range(len(a)):
	if a[n]%2==1:
		b.append(1)
	else:
		b.append(0)

new_a = str(int(reduce(lambda x, y: x + y, [str(x) for x in b])))
print(int(new_a, 2))

### FIXED CODE ###

from functools import reduce

A,B= (int(i) for i in input().split()) 

def XOR(x):
	if x%2==1:
		if ((x+1)//2)%2==0:
			return 0
		else:
			return 1
	else:
		if (x//2)%2==0:
			return int(format(x,"b"))
		else:
			return int(format(x,"b"))+1

ans = int(str(XOR(A-1)), 2) ^ int(str(XOR(B)), 2)
print(ans)
### BUGGY CODE ###

MOD = (10 ** 9) + 7

S = input()
N = len(S)

nums = [1, 0, 0, 0]

for i in range(0, N):
    s = S[i]
    m = 3 if s == "?" else 1
    a = 1 if s == "A" or s == "?" else 0
    b = 1 if s == "B" or s == "?" else 0
    c = 1 if s == "C" or s == "?" else 0

    n0 = nums[0] * m
    n1 = nums[1] * m + nums[0] * a
    n2 = nums[2] * m + nums[1] * b
    n3 = nums[3] * m + nums[2] * c
    nums = [n0, n1, n2, n3]

print(nums[3] % MOD)


### FIXED CODE ###

import gc

MOD = (10 ** 9) + 7

S = input()
N = len(S)

dp = [[0] * (N + 1) for _ in range(4)]

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        dp[j][i] = dp[j][i] % MOD

print(dp[3][N] % MOD)
### BUGGY CODE ###

import math

K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans+=math.gcd(i,math.gcd(j,k)) 
print(ans)           



### FIXED CODE ###

import math

ans = 0
K = int(input())
dp = [[1] * 220 for i in range(220)] 
for i in range(1,K+1):
    for j in range(1,K+1):
        dp[i][j] = math.gcd(i,j)
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            a = dp[i][j]
            ans += dp[a][k]
print(ans)
### BUGGY CODE ###

import collections,copy
def LI(): return list(map(int,input().split()))
N,Q = LI()
ans = [0]*(N+1)
graph = [collections.deque() for _ in range(N+1)] #1_index
for _ in range(N-1):
    a,b = LI()
    graph[a].append(b)
    graph[b].append(a)
for _ in range(Q):
    p,x = LI()
    ans[p] += x
seen = [-1]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])


### FIXED CODE ###

import collections,copy,sys
def LI(): return list(map(int,sys.stdin.readline().split()))
N,Q = LI()
ans = [0]*(N+1)
graph = [collections.deque() for _ in range(N+1)] #1_index
for _ in range(N-1):
    a,b = LI()
    graph[a].append(b)
    graph[b].append(a)
for _ in range(Q):
    p,x = LI()
    ans[p] += x
seen = [-1]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])
### BUGGY CODE ###

s = input()
ori = len(s)
while "10" in s or "01" in s:
  s = s.replace("10","")
  s = s.replace("01","")
print(ori-len(s))

### FIXED CODE ###

S=input()
stack=[]
count=0
for s in S:
    if not stack:
        stack.append(s)
    elif stack[-1]!=s:
        stack.pop()
        count+=2
    else:
        stack.append(s)
print(count)