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

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n
# O(n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

jun = []

def chil_pop(l,p):
    jun.append(l)
    for i in b[l]:
        if i == p:
            continue
        chil_pop(i,l)
    b[l] = p

chil_pop(0,-1)

for i in range(q):
    p,x = mi()
    ans[p-1] += x

for i in jun[1:]:
    ans[i] += ans[b[i]]

ans_str = ''
for i in range(n):
    # print(ans[i],end=' ')
    ans_str = ans_str + str(ans[i]) + ' '
print(ans_str)


### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

# jun = []
# O(2n)
# def chil_pop(l,p):
#     jun.append(l)
#     for i in b[l]:
#         if i == p:
#             continue
#         chil_pop(i,l)
#     b[l] = p

# chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x


count = 0
q = [(0,-1)]
while q:
    c,p = q.pop()
    for i in b[c]:
        if i == p:
            continue
        ans[i] += ans[c]
        q.append((i,c))
    
    

# for i in jun[1:]:
#     ans[i] += ans[b[i]]

# ans_str = ''
# for i in range(n):
#     print(ans[i],end=' ')
#     # ans_str = ans_str + str(ans[i]) + ' '
print(*ans)
### BUGGY CODE ###

Figures = []
N = int(input())
for _ in range(N):
  x = int(input())
  if x in Figures:
    Figures.remove(x)
  else:
    Figures.append(x)
print(len(Figures))

### FIXED CODE ###

dic = {}
N = int(input())
for _ in range(N):
  x = int(input())
  if x in dic:
    dic[x] += 1
  else:
    dic[x] = 1
counter = 0
for i in dic.keys():
  if dic[i] %2 == 1:
    counter +=1
print(counter)
### BUGGY CODE ###

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

mod = 10**9+7

def dfs(x,y):
    if not(0<=x<H) or not(0<=y<W):
        return
    if  maze[x][y]=="#":
        return
    
    if x==H-1 and y==W-1:
        return
        
    dh = [1,0]
    dw = [0,1]
    
    for i,j in zip(dh,dw):
        if (0<=x+i<H) and (0<=y+j<W):
            if maze[x+i][y+j]!="#":
                dp[x+i][y+j] += 1
                dp[x+i][y+j] %= mod
        dfs(x+i,y+j)

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

dp = [[0]*W for _ in range(H)]
dp[0][0]=1

dfs(0,0)
print(dp[H-1][W-1])

### FIXED CODE ###

mod = 10**9+7
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
dp = [[0]*W for _ in range(H)]
dp[0][0]=1

for i in range(H):
    for j in range(W):
        if i+1<H and maze[i+1][j]==".":
            dp[i+1][j] += dp[i][j]%mod
        if j+1<W and maze[i][j+1]==".":
            dp[i][j+1] += dp[i][j]%mod
            
print(dp[H-1][W-1]%mod)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    ans=a.count(i)
    print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=[0]*n
for i in range(0,n-1):
    cnt[a[i]-1]+=1
for i in range(0,n):
    print(cnt[i])
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def add(self, i, x=1):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    # Return sum for [l, r)
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N = int(readline())
    S = readline().strip()
    Q = int(readline())

    S = list(S)
    base = ord('a')

    tree = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        tree[ord(c) - base].add(i)

    ans = []
    for _ in range(Q):
        n, a, b = readline().split()
        if n == '1':
            i = int(a) - 1
            if S[i] != b:
                tree[ord(S[i]) - base].add(i, -1)
                tree[ord(b) - base].add(i, 1)
                S[i] = b
        else:
            l, r = int(a) - 1, int(b)
            tmp = 0
            for i in range(26):
                if tree[i].get_sum_range(l, r) > 0:
                    tmp += 1
            ans.append(tmp)

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def add(self, i, x=1):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    # Return sum for [l, r)
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N = int(readline())
    S = readline().strip()
    Q = int(readline())

    S = list(S)

    tree = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        tree[ord(c) - ord('a')].add(i)

    ans = []
    for _ in range(Q):
        A = readline().split()
        if A[0] == '1':
            i, c = int(A[1]) - 1, A[2]
            if S[i] != c:
                tree[ord(S[i]) - ord('a')].add(i, -1)
                tree[ord(A[2]) - ord('a')].add(i, 1)
                S[i] = c
        else:
            l, r = int(A[1]) - 1, int(A[2]) - 1
            tmp = 0
            for i in range(26):
                if tree[i].get_sum_range(l, r + 1) > 0:
                    tmp += 1
            ans.append(tmp)

    print('\n'.join(map(str, ans)))
    return


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

n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))
s = []
f = []

z = 0
c = 1
m = 0
for a in range(k-1,k):
    z = 0
    c = 1
    while z < k:
        c = c * arr[a-z]
        z += 1

    s.append(c)
    
lastkm1 = c//arr[m]

for i in range(k,n):
    m += 1
    c = lastkm1*arr[i]
    s.append(lastkm1*arr[i])
    lastkm1 = c//arr[m]

l = len(s)
for i in range(1,l):
    if s[i]>s[i-1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for i in range(n-k):
    if (arr[i]<arr[i+k]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

class query:
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d
    def isEternal(self):
        if self.a < self.b:
            return "No"
        if self.a % self.b > self.c:
            return "No"
        if self.d < self.b:
            return "No"
        d = self.b - self.c
        if d <= 0:
            return "Yes"
        if self.b % d == 0 and self.d % d == 0:
            return "Yes"
        s = self.a % self.b
        db = self.d % self.b
        if db == 0:
            return "Yes"
        for i in range(self.b - 1):
            s += db
            if s >= self.b:
                return "Yes"
            if s > self.c:
                return "No"
        return "Yes"

if __name__ == "__main__":
    t = int(input())
    querys = [query(*[int(s) for s in input().split()]) for _ in range(t)]
    for q in querys:
        print(q.isEternal())


### FIXED CODE ###

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

class query:
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d
    def isEternal(self):
        if self.a < self.b:
            return "No"
        if self.d < self.b:
            return "No"
        if self.b <= self.c:
            return "Yes"
        g = gcd(self.d, self.b)
        if self.b - g + self.a % g > self.c:
            return "No"
        return "Yes"

if __name__ == "__main__":
    t = int(input())
    querys = [query(*[int(s) for s in input().split()]) for _ in range(t)]
    for q in querys:
        print(q.isEternal())
### BUGGY CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0
cnt = 1

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    cnt += 1
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid
    if cnt >= 21:
        print(s[1000])
print(high,1111)
sys.stdout.flush()
s = input()
exit()

### FIXED CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0
cnt = 1

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    cnt += 1
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid

print(high)
sys.stdout.flush()
s = input()
if s[0] == "V":
    exit()
else:
    print(low)
    sys.stdout.flush()
    s = input()
    exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

l = {}

for a in A:
    if a in l.keys():
        l[a] += 1
    else:
        l[a] = 1

# def make_divisors(n):
#     lower_divisors, upper_divisors = [], []
#     i = 1
#     while i * i <= n:
#         if n % i == 0:
#             lower_divisors.append(i)
#             if i != n // i:
#                 upper_divisors.append(n // i)
#         i += 1
#     return lower_divisors + upper_divisors[::-1]

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n // i)
        i += 1
    table = list(set(table))
    return table

ans = 0
for a in A:
    flag = True
    # da = make_divisors(a)
    da = divisor(a)
    for d in da:
        if d != a:
            if d in l.keys():
                flag = False
                break
        elif l[d] >= 2:
            flag = False
            break
    if flag:
        ans += 1

print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline

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

l = [0]*1000001

A.sort()

for a in A:
    if l[a] == 0:
        l[a] = 1
        tmp = 2
        while tmp*a <= 1000000:
            l[tmp*a] = 2
            tmp+=1
    elif l[a] == 1:
        l[a] = 2

ans = 0
for a in A:
    if l[a] != 2:
        ans += 1

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

n = int(input())
ans = n
for a in range(1, n + 1):
    if n % a == 0:
        b = n // a
        tmp = max(len(str(a)), len(str(b)))
        ans = min(ans, tmp)
        if a > b:
            break
print(ans)

### FIXED CODE ###

n = int(input())
ans = n
for a in range(int(n ** (0.5)), 0, -1):
    if n % a == 0:
        b = n // a
        tmp = max(len(str(a)), len(str(b)))
        ans = min(ans, tmp)
print(ans)
### BUGGY CODE ###

def resolve():
	s = input()
	ans = 0
	for i in range(0, len(s)):
		for j in range(3, len(s)):
			if i + j < len(s):
				if not int(s[i:i + j + 1]) % 2019:
					ans += 1
	print(ans)
resolve()

### FIXED CODE ###

def resolve():
    s = input()
    s = s[::-1]
    c = [0]*2019
    # why?
    c[0] = 1
    r = 0
    d = 1
    for i in s:
        num = int(i) * d % 2019 + r
        num %= 2019
        c[num] += 1
        r = num
        d *= 10
        d %= 2019
    ans = 0
    for i in c:
        ans += i*(i-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9+7
    # Aの中でd桁目が0,1であるものの個数を求める(p,qとする)
    # 全部のd桁目についてループして、ans+=(2**d)*(p*q)
    ans = 0
    for d in range(60):
        p,q = 0,0
        for i in range(N):
            if A[i]%2==0: p+=1
            else: q+=1
            A[i] //= 2
        ans += ((2**d)*p*q)%MOD
        ans %= MOD
    print(ans)

main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9+7
    # Aの中でd桁目が0,1であるものの個数を求める(p,qとする)
    # 全部のd桁目についてループして、ans+=(2**d)*(p*q)
    ans = 0
    for d in range(60):
        p,q = 0,0
        for i in range(N):
            if A[i]%2==0: p+=1
            else: q+=1
            A[i] //= 2
        ans += ((2**d)*p*q)%MOD
        ans %= MOD
    print(ans)

main()
### BUGGY CODE ###

from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("#")

dr = np.array([[0, 1], [0, -1], [1, 0], [-1, 0]])


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        dr_i = dr + [x, y]
        for nx, ny in dr_i:
            if nx < 0 or h - 1 < nx or ny < 0 or w - 1 < ny:
                continue      
          
            if mass[nx][ny] == wall or visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = depth[x][y] + 1

    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))


### FIXED CODE ###

import numpy as np
from collections import deque
h, w = map(int, input().split())
r = [list(input()) for i in range(h)]


def dist(s, t):
    if r[s][t] == "#":
        return 0
    else:
        visited = np.zeros((h, w))
        visited[s][t] += 1
        distance = np.zeros((h, w))
        q = deque([[s, t]])
        while len(q) > 0:
            i, j = q.popleft()
            d = distance[i][j] + 1
            if j != w-1:
                if r[i][j+1] == "." and not visited[i][j+1]:
                    q.append([i, j + 1])
                    visited[i][j+1] += 1
                    distance[i][j+1] += d
            if j != 0:
                if r[i][j-1] == "." and not visited[i][j-1]:
                    q.append([i, j - 1])
                    visited[i][j - 1] += 1
                    distance[i][j - 1] += d
            if i != 0:
                if r[i-1][j] == "." and not visited[i-1][j]:
                    q.append([i - 1, j])
                    visited[i-1][j] += 1
                    distance[i-1][j] += d
            if i != h-1:
                if r[i+1][j] == "." and not visited[i+1][j]:
                    q.append([i + 1, j])
                    visited[i+1][j] += 1
                    distance[i+1][j] += d
        return np.max(distance)


ans = 0
for s in range(h):
    for t in range(w):
        ans = max(ans, dist(s, t))

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

def warshall_floyd(n, d):
    for i in range(n):
        di = d[i]
        for j in range(n):
            dj = d[j]
            for k in range(n):
                t = dj[i] + di[k]
                if t < dj[k]:
                    dj[k] = t


INF = float('inf')

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

N = H * W
d = [[INF] * N for _ in range(N)]
for k in range(N):
    d[k][k] = 0

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        if y - 1 >= 0 and S[y - 1][x] != '#':
            d[y * W + x][(y - 1) * W + x] = 1
        if y + 1 < H and S[y + 1][x] != '#':
            d[y * W + x][(y + 1) * W + x] = 1
        if x - 1 >= 0 and S[y][x - 1] != '#':
            d[y * W + x][y * W + x - 1] = 1
        if x + 1 < W and S[y][x + 1] != '#':
            d[y * W + x][y * W + x + 1] = 1

warshall_floyd(N, d)

result = 0 
for i in range(N):
    for j in range(N):
        if d[i][j] != INF and d[i][j] > result:
            result = d[i][j]

print(result)


### FIXED CODE ###

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


def f(i, j):
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '#' and t[y - 1][x] == -1:
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '#' and t[y + 1][x] == -1:
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '#' and t[y][x - 1] == -1:
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '#' and t[y][x + 1] == -1:
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


result = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            result = max(result, f(i, j))
print(result)
### BUGGY CODE ###

import math
def counter(A):
    cnt = 0
    for i,ai in enumerate(A):
        cnt += sum(a < ai for a in A[i+1:])
    return cnt

N,K = map(int,input().split())
A = list(map(int,input().split()))

one_a = counter(A)
two_a = counter(A*2)

if A == sorted(A,reverse=True):
    ans = one_a * sum(range(1,K+1))
elif A == sorted(A):
    ans = two_a * sum(range(1,K)) 
else:
    ans = ((two_a-one_a*2) * sum(range(1,K)) ) + (K*one_a)
print(ans%((10**9)+7))  

### FIXED CODE ###

import math
def counter_one(A):
    cnt = 0
    for i,ai in enumerate(A):
        cnt += sum(a < ai for a in A[i+1:])
    return cnt
def counter_two(A):
    cnt = 0
    for i,ai in enumerate(A):
        cnt += sum(a < ai for a in A)
    return cnt
  

N,K = map(int,input().split())
A = list(map(int,input().split()))

one_a = counter_one(A)
two_a = counter_two(A)

ans = (one_a*K)+((two_a)*(K*(K-1)//2))
print(int(ans%((10**9)+7)))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(4100000)

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

already_reach = [-1]*(N+1)
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split(' '))
    graph[u].append(v)
S,T = map(int,input().split(' '))

def search(S_list,current_count=0):
    for s in S_list:
        already_reach[s] = current_count
    #print(already_reach)
    next_list = []
    for s in S_list:
        for i1 in graph[s]:
            for i2 in graph[i1]:
                for i3 in graph[i2]:
                    if already_reach[i3] == -1: #はじめての到達
                        next_list.append(i3)
    if len(next_list) > 0:
        search(next_list,current_count+1)
search([S])
print(already_reach[T])


### FIXED CODE ###

import sys

sys.setrecursionlimit(4100000)

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

already_reach = [-1]*(N+1)
already_reach_1st = [-1]*(N+1)
already_reach_2nd = [-1]*(N+1)
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split(' '))
    graph[u].append(v)
S,T = map(int,input().split(' '))

next_list = []
def search(S_list,current_count=0):
    next_list = []
    for s in S_list:
        for i1 in graph[s]:
            #print(already_reach_1st)
            if already_reach_1st[i1] != -1:
                continue
            already_reach_1st[i1] = 0
            for i2 in graph[i1]:
                #print(already_reach_2nd)
                if already_reach_2nd[i2] != -1:
                    continue
                already_reach_2nd[i2] = 0
                for i3 in graph[i2]:
                    if already_reach[i3] == -1: #はじめての到達
                        already_reach[i3] = current_count+1
                        next_list.append(i3)
    if len(next_list) > 0:
        search(next_list,current_count+1)
search([S])
print(already_reach[T])
### BUGGY CODE ###

import math

k = int(input())
count = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            x = math.gcd(a,b)
            count += math.gcd(x,c)
print(count)

### FIXED CODE ###

import math

k = int(input())
count = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        x = math.gcd(a,b)
        for c in range(1, k+1):
            count += math.gcd(x,c)
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M=map(int,input().split())
list1=list(map(int,input().split()))
list2=list(set(list1))
listBC=[[list2[i],list1.count(list2[i])] for i in range(len(list2))]
listC=[list2[i] for i in range(len(list2))]
for _ in range(M):
  B,C=map(int,input().split())
  listBC+=[[C,B]]
  listC+=[C]
listBC.sort(reverse=True)
i=-1
SUM=0
ans=0
while SUM<N:
  i+=1
  ans+=listBC[i][0]*listBC[i][1]
  SUM+=listBC[i][1]
ans-=listBC[i][0]*(SUM-N)  
print(ans)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
### BUGGY CODE ###

def resolve():
    s = input()
    query = int(input())
    for i in range(query):
        q = input()
        if q[0]=='2':
            _,f,c = q.split()
            if f == '1':
                s = c + s
            else:
                s = s + c
        else:
            s = s[::-1]
    print(s)
resolve()

### FIXED CODE ###

def resolve():
    s = input()
    query = int(input())
    r = 0
    left = ''
    for i in range(query):
        q = input()
        if q[0]=='2':
            _,f,c = q.split()
            if (int(f)+r)%2 == 0:
                s += c
            else:
                left += c
        else:
            r = (r+1)%2
    print(left[::-1]+s if r==0 else s[::-1]+left)
resolve()
### BUGGY CODE ###

s = input()[::-1]
s += "0"
n = len(s)

dp = [[1001001001]*2 for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for j in range(2):
        x = int(s[i]) + j

        if x < 10:
            dp[i+1][0] = min(dp[i][j] + x,dp[i+1][0])
        if x > 0:
            dp[i+1][1] = min(dp[i][j] + (10 - x),dp[i+1][1])


print(dp[n][0])

### FIXED CODE ###

s = input()[::-1]
s += "0"
n = len(s)

dp = [[1001001001]*2 for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for j in range(2):
        x = int(s[i]) + j

        if x < 10:
            dp[i+1][0] = min(dp[i][j] + x,dp[i+1][0])
        if x > 0:
            dp[i+1][1] = min(dp[i][j] + (10 - x),dp[i+1][1])


print(dp[n][0])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
mod=10**9+7
dp=[0]*(n+2)
dp[n]=1
for i in range(n-1,-1,-1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i+1]%mod+dp[i+2]%mod)%mod
print(dp[0])


### FIXED CODE ###

n,m=map(int,input().split())
a=set(int(input()) for _ in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
        dp[i]=0
print(dp[n])