Harryxun/stf_run huggingface dataset:
# ABC144d


def main():
    import sys
    import math
    import numpy as np
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    a, b, x = map(int, input().split())
    if x > a*b*b/2:
        print(np.rad2deg(np.arctan(2*(a*a*b-x)/(a*a*a))))
        # print(math.degrees(math.atan(2*(a*a*b-x)/(a*a*a))))
        exit(0)
    # print(math.degrees(math.atan(a*b*b/2/x)))
    print(np.rad2deg(np.arctan(a*b*b/2/x)))


if __name__ == '__main__':
    main()

### FIXED CODE ###

# ABC144d


def main():
    import sys
    import math
    import numpy as np
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    a, b, x = map(int, input().split())
    if x > a*a*b/2:
        print(np.rad2deg(np.arctan(2*(a*a*b-x)/(a*a*a))))
        # print(math.degrees(math.atan(2*(a*a*b-x)/(a*a*a))))
        exit(0)
    # print(math.degrees(math.atan(a*b*b/2/x)))
    print(np.rad2deg(np.arctan(a*b*b/2/x)))


if __name__ == '__main__':
    main()
nums = input().split()
x = int(nums[3])
 x ** 3

### FIXED CODE ###

x = int(input())
print(x ** 3)
S = int(input())
W = int(input())

if S <= W:
  print('unsafe')
else:
  print('safe')


### FIXED CODE ###

S,W=(int(x) for x in input().split())

if S <= W:
  print('unsafe')
else:
  print('safe')
s=input()
a=s[1::2]
b=[::2]
if "L" not in b and "R" not in a:print("Yes")
else:print("No")

### FIXED CODE ###

s=input()
a=s[1::2]
b=s[::2]
if ("L" not in b) and ("R" not in a):print("Yes")
else:print("No")
from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(n):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visit = [0] * (n + 1)
ans = 0


def dfs(now, depth):
    global ans
    if visit[now]:
        pass
    if depth == n:
        ans += 1

    visit[now] = 1
    if graph[now]:
        for i in graph[now]:
            if visit[i] == 0:
                dfs(i, depth + 1)
    visit[now] = 0


dfs(1, 1)
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visit = [0] * (n + 1)


def dfs(now, depth):
    if visit[now]:
        return 0
    if depth == n:
        return 1

    count = 0
    visit[now] = 1
    if graph[now]:
        for i in graph[now]:
            count += dfs(i, depth + 1)
    visit[now] = 0

    return count


ans = dfs(1, 1)
print(ans)
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
import numpy as np

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

x = []
y = []
for i, (ex, ey) in enumerate(xy):
    x.append([ex, i])
    y.append([ey, i])

x.sort()
y.sort()

u = []
v = []
c = []


def f(li):
    for (e1, i1), (e2, i2) in zip(li, li[1:]):
        dist = e2 - e1
        u.append(i1)
        v.append(i2)
        c.append(dist)


f(x)
f(y)

graph = csr_matrix((c, (u, v)))
mst = minimum_spanning_tree(graph).astype(np.int64)
ans = mst.sum()
print(ans)


### FIXED CODE ###

from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
from operator import itemgetter

n = int(input())
xy = [list(map(int, input().split())) + [i] for i in range(n)]

edge = set()
for key in (itemgetter(0), itemgetter(1)):
    xy.sort(key=key)
    for (x1, y1, i1), (x2, y2, i2) in zip(xy, xy[1:]):
        d = min(abs(x1 - x2), abs(y1 - y2))
        edge.add((i1, i2, d))

u, v, c = zip(*edge)

graph = csr_matrix((c, (u, v)), shape=(n, n), dtype=int)
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)
n = int(input())
number = list(map(int, input().split()))
seki = 0
seki2 = -1
for i in numebr:
  seki = seki*i
 if seki > 10 ** 18:
  print(seki2)
 else:
  print(seki)

### FIXED CODE ###

n = int(input())
number = list(map(int, input().split()))
seki = 1
if 0 in number:
  seki = 0
else:
  for i in number:
    seki = seki*i
    if seki > 10 ** 18:
      seki = -1
      break
    else:
      continue
print(seki)
import math

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

print(int(math.factorial(N)/math.factorial(N-2)/math.factorial(2)+math.factorial(M)/math.factorial(M-2)/math.factorial(2)))


### FIXED CODE ###

import math

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

if (N==0 or N==1) and (M==0 or M==1):
  print(0)
elif (N==0 or N==1) and (M!=0 and M!=1):
  print(int(math.factorial(M)/math.factorial(M-2)/math.factorial(2)))
elif (M==0 or M==1) and (N!=0 and N!=1):
  print(int(math.factorial(N)/math.factorial(N-2)/math.factorial(2)))
else:
  print(int(math.factorial(N)/math.factorial(N-2)/math.factorial(2)+math.factorial(M)/math.factorial(M-2)/math.factorial(2)))
import itertools
import sys
import numpy as np
from collections import Counter
import bisect

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = Counter()
for i, x in enumerate(left):
    indices[x] += 1


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = indices.get(i, 0)
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return res * len(set(itertools.permutations(h))) % M


print(solve())


### FIXED CODE ###

import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(sys.stdin.readline())
left = list(map(int, sys.stdin.read().split()))
counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    if sum(h) != N:
        return 0
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())
number=list(map(int,input().split()))
likes=[]
result=0
for i in range(number[0]):
    for j in range(number[1]):
        rawdata=list(map(int,input().split()))
        for k in range(rawdata[0]):
            likes.append(rawdata[k+1])
for i in range(number[1]):
    if likes.count(i+1):
        result+=1
print(result)

### FIXED CODE ###

number=list(map(int,input().split()))
likes=[]
result=0
for i in range(number[0]):
    rawdata=list(map(int,input().split()))
    for k in range(rawdata[0]):
        likes.append(rawdata[k+1])
for i in range(number[1]):
    if likes.count(i+1)==number[0]:
        result+=1
print(result)
K, S = map(int, input().split())


ans = 0

for x in range(K+1):
    for y in range(K+1):
        if 0 <= S-x-y <=k:
            ans = ans + 1
print(ans)


### FIXED CODE ###

K, S = map(int, input().split())
ans = 0
for x in range(min(K,S)+1):
	for y in range(min(K,S)+1):
		if 0 <= S - x - y <= K:
			ans += 1
print(ans)
S=input()
T=input()
a=len(S)
b=len(T)
m=a-b
A=[]
for i in range(m):
    cnt=b
    for j in range(b):
        if S[i+j]==T[j]:
            cnt-=1
    A.append(cnt)
print(min(A))

### FIXED CODE ###

S=input()
T=input()
a=len(S)
b=len(T)
m=a-b
ans=b
if m!=0:
    for i in range(m):
        cnt=b
        for j in range(b):
            if S[i+j]==T[j]:
                cnt-=1
        ans=min(cnt,ans)
else:
    cnt=b
    for i in range(a):
        if S[i]==T[i]:
            cnt-=1
    ans=min(cnt,ans)
print(ans)
s=input()
for i in range(len(s)/2-1,0,-1):
  if s[0:i]==s[i:i+i]:
    print(i)
    exit(0)

### FIXED CODE ###

s=input()
n=len(s)
for i in range(n//2,0,-1):
  if i*2==n:
    continue
  if s[0:i]==s[i:i+i]:
    print(i+i)
    break
1n = input()
_list = input().split(" ")
_list = [int(x) for x in _list]
even = [x for x in _list if x % 2==0]
answer = []
for x in even:
    if x % 3 == 0 or x % 5 == 0:
        answer.append(True)
if len(even) ==len(answer):
    print("APPROVED")
else:
    print("DENIED")

### FIXED CODE ###

n = input()
_list = input().split(" ")
_list = [int(x) for x in _list]
even = [x for x in _list if x % 2==0]
answer = []
for x in even:
    if x % 3 == 0 or x % 5 == 0:
        answer.append(True)
if len(even) ==len(answer):
    print("APPROVED")
else:
    print("DENIED")
inp=list(map(int,input().strip().split()))[:2]
n,r=inp[0],inp[1]
count=0
while(n > 0):
  n=n//k
  count+=1
return count

### FIXED CODE ###

inp=list(map(int,input().strip().split()))[:2]
n,r=inp[0],inp[1]
count=0
while(n > 0):
    n=n//r
    count+=1
print(count)
from math import fractions  
a,b=map(int,input().split())  
print(a*b//fractions.gcd(a,b))


### FIXED CODE ###

import fractions  
a,b=map(int,input().split())  
print(a*b//fractions.gcd(a,b))
def main():
    n = map(int, input().split())

    train = n * a
    taxi = b

    print(min(train,taxi))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, a, b = map(int, input().split())
 
    train = n * a
    taxi = b
 
    print(min(train,taxi))
 
if __name__ == '__main__':
    main()
S=input()
ans=0
for i in range(len(S)):
    cnt=0
    while True:
        if S[i] in ["A","C","G","T"] and i<len(S):
            cnt+=1
            i+=1
        else:
            if cnt>ans:
                ans=cnt
            break
print(ans)

### FIXED CODE ###

S=input()
ans=0
for i in range(len(S)):
    cnt=0
    while True:
        if  i>=len(S):
            break
        elif S[i] not in ["A","C","G","T"]:
            break
        else:
            cnt+=1
            i+=1    
    if cnt>ans:
        ans=cnt
print(ans)
l = list(map(int,input().split()))

count = 0

for x in range(l[0] + 1):
    for y in range(l[0] + 1):
        for z in range(l[0] + 1):
            if x + y + z == l[1]:
                count += 1
                print(x,y,z)

print(count)



### FIXED CODE ###


a,b,c = input().split(",")
print(a + " " + b + " " + c)
r,c,R,C=map(int,input().split())
m=10**9+7
max_n=2*10**6
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%m
    inv[n]=m-inv[m%n]*(m//n)%m
    ifac[n]=(ifac[n-1]*inv[n])%m
def comb(n,k):
    if n<k or n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%m
def f(r,c):
    return sum([comb(i+1+c,c) for i in range(r+1)])%m
print((f(R,C)-f(R,c-1)-f(r-1,C)+f(r-1,c-1))%m)

### FIXED CODE ###

r,c,R,C=map(int,input().split())
m=10**9+7
max_n=2*10**6+1
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%m
    inv[n]=m-inv[m%n]*(m//n)%m
    ifac[n]=(ifac[n-1]*inv[n])%m
def comb(n,k):
    if n<k or n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%m
def f(r,c):
    return sum([comb(i+1+c,c) for i in range(r+1)])%m
print((f(R,C)-f(R,c-1)-f(r-1,C)+f(r-1,c-1))%m)
N = int(input())
h = list(map(int, input().split()))
c = []
tmp = 0
for x in range(len(h)-1, -1, -1):
  if len(h) == 1:
    c.append(h[0])
  elif h[x] <= h[x-1]:
    tmp += 1
  else:
    c.append(tmp)
    tmp = 0
print(max(c))


### FIXED CODE ###

N = int(input())
h = list(map(int, input().split()))
c = []
tmp = 0
for x in reversed(range(len(h))):
  if len(h) == 1:
    c.append(0)
  elif h[x] <= h[x-1]:
    tmp += 1
  else:
    c.append(tmp)
    tmp = 0
if len(c) == 0:
  c.append(tmp-1)
print(sorted(c)[-1])
N, P = map(int, input().split())
P_prime = []
while P % 2 == 0:
    P_prime.append(2)
    P //= 2
odd = 3
while odd * odd <= P:
    if P % odd == 0:
        P_prime.append(odd)
        P //= odd
    else:
        odd += 2
if P != 1:
    P_prime.append(P)
edge = [0]
for i in range(len(P_prime) - 1):
    if P_prime[i] != P_prime[i + 1]:
        edge.append(i)
edge.append(len(P_prime) - 1)
ans = 1
for i in range(len(edge) - 1):
    ans *= pow(P_prime[edge[i + 1]], (edge[i + 1] - edge[i]) // N)
print(ans)


### FIXED CODE ###

import collections as cl

N, P = map(int, input().split())
if P == 1:
    print(1)
    exit()
P_prime = []
while P % 2 == 0:
    P_prime.append(2)
    P //= 2
odd = 3
while odd * odd <= P:
    if P % odd == 0:
        P_prime.append(odd)
        P //= odd
    else:
        odd += 2
if P != 1:
    P_prime.append(P)

ans = 1
dic_P = cl.Counter(P_prime)
for prime, num in dic_P.items():
    ans *= pow(prime, num // N)
print(ans)
S = input()
if 0 <= S and S <= 86400:
   a = S / 3600
   b = S % 3600
   c = b / 60
   d = b % 60
else:
   print Error
printn "%d:%d:%d" %(a,c,d) 
 

 

### FIXED CODE ###

S = input()
if S >= 0 and S <= 86400:
   a = S // 3600
   b = S % 3600
   c = b // 60
   d = b % 60
   print "%d:%d:%d" % (a, c, d)
a, b, n = map(int, input().split())
max_int = 0
if a != b:
    if n < b:
        max_int = int((a*n)/b) -a * int(n/b)
    else:
        #for i in range(n, n-max(int(b/a), int(a/b), int(a%b), int(b%a))-1, -1):
        for i in range(i, n):
            tmp = int((a*i)/b) -a * int(i/b)

            #print(i)
            #print(tmp)
            if max_int < tmp:
                max_int = tmp

print(max_int)

### FIXED CODE ###

a, b, n = map(int, input().split())
i = min(b-1, n)
print(int((a*i)/b) -a * int(i/b))
import math

n = int(input())
li = list(map(int,input().split()))
ans = li[0]

for i in range(1,n):
    ans = math.gcd(ans,li[i])

print(ans)
    


### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = li[0]

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

for i in range(1,n):
    ans = gcd(ans,li[i])

print(ans)
import itertools
from sys import stdin
H,W = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for _ in range(N):
    data.append(list(input()))

flag = False
for j in (itertools.product([0,1],repeat=(H+W-2))):
    route_flag = True
    right = 0
    down  = 0
    for k in j:
        if k == 1:
            right += 1
        else:
            down += 1
        if data[down][right] == ".":
            route_flag = False
    if foute_flag:
        flag = True
    
if data[0][0] == ".":
    flag = False

if flag:
    print("Possible")
else:
    print("Impossible")

### FIXED CODE ###

import itertools
from sys import stdin
H,W = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for _ in range(H):
    data.append(list(input()))

right = 0
down  = 0
for i in data:
    for j in range(0,W-1):
        if i[j] == "#" and i[j+1] == "#":
            right += 1

data_t = []
for i in range(W):
    row = []
    for vector in data:
        row.append(vector[i])
    data_t.append(row)

for i in data_t:
    for j in range(0,H-1):
        if i[j] == "#" and i[j+1] == "#":
            down += 1

if down == H-1 and right == W-1:
    print("Possible")
else:
    print("Impossible")
a, b = map(int, input().split())

if a < 1 or a > 9:
    return -1

if b < 1 or b > 9:
    return -1

return a * b


### FIXED CODE ###

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

if a < 1 or a > 9:
    print(-1)
elif b < 1 or b > 9:
    print(-1)
else:
    print(a * b)
N, M = input().split()
N = int(N)
M = int(M)
A = list(map(int, input().split()))


def discount(x, y):
    return int(x / (2 ** y))

A.sort()

for i in range(M):
    if i == 0:
        res = sum(A) - A[N-1] + discount(A[N-1], M)
    else:
        _res = sum(A)
        for j in range(i+1):
            _res -= A[N-1-j]
            _res += discount(A[N-1-j], M-1-j)
        res = min(res, _res)

print(res)


### FIXED CODE ###

import heapq

N, M = list(map(int, input().split()))
A = list(map(lambda x: -int(x), input().split()))

heapq.heapify(A)

for i in range(M):
    _ = -heapq.heappop(A)
    _ = int(_ / 2)
    heapq.heappush(A, -_)

print(-sum(A))
N,M,X=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]


cmin=12*10**5+1
for bit in range(2**N):
    A=[0]*M
    c=0
    for j in range(N):
        if (bit>>j)&1:
            c+=l[j][0]
            A=[x+y for (x,y) in zip(A, l[j][1:])]
    if min(A) >= X:
        cmin=min(cmin,c)

if cmin!=12*10**5+1:
    print(cmin)
else:
    print(-1)

### FIXED CODE ###

N,M,X=map(int,input().split())
l=[list(map(int,input().split())) for i in range(N)]


cmin=12*10**5+1
for bit in range(2**N):
    A=[0]*M
    c=0
    for j in range(N):
        if (bit>>j)&1:
            c+=l[j][0]
            A=[x+y for (x,y) in zip(A, l[j][1:])]
    if min(A) >= X:
        cmin=min(cmin,c)

if cmin!=12*10**5+1:
    print(cmin)
else:
    print(-1)
N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
if a<K:
    ans=0
else:
    if a>K:
        ans+=combi(a-1,K)*(9**K)
    if K==1:ans+=int(n[0])
    elif K==2:ans+=(int(n[0])-1)*(a-1)*9+(a-2)*9+int(n[1])
    else:ans+=(int(n[0])-1)*81*(combi(a-1,2))+combi(a-2,2)*81+9*(a-2)*(int(n[1])-1)+int(n[2])+(a-3)*9

print(ans)

### FIXED CODE ###

N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    if p<q : return 0
    else: return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
def mi(i):
    if i==0:
        return 0
    else:
        return i-1
def zero(i):
    if int(n[i])==0:
        return 0
    else:
        return 1
if a<K:
    ans=0
else:
    if a>K:
        ans+=combi(a-1,K)*(9**K)
    if K==1:ans+=int(n[0])
    elif K==2:
        x=0
        i=1
        b=0
        bs=0
        while True:
            if (int(n[i])!=0) and (x==0):
                b=int(n[i])
                bs=a-i
                x+=1
            if (x==1) or (i==len(n)-1):
                break
            i+=1
        ans+=mi(int(n[0]))*(a-1)*9+mi(bs)*9+b
    elif a==3 : ans+=mi(int(n[0]))*81*(combi(a-1,2))+9*mi(int(n[1]))+int(n[2])
    else:
        x=0
        i=1
        b=0
        bs=0
        c=0
        cs=0
        while True:
            if (int(n[i])!=0) and (x==0):
                b=int(n[i])
                bs=a-i
                x+=1
            elif (int(n[i])!=0) and (x==1):
                c=int(n[i])
                cs=a-i
                x+=1
            if (x==2) or (i==len(n)-1):
                break
            i+=1
        ans+=mi(int(n[0]))*81*(combi(a-1,2))+combi(bs-1,2)*81+9*(a-2)*mi(b)+c+mi(cs)*9

print(ans)
N = int(input())
 
t = [int(input().split()) for i in range(N)]
 
M = int(input())
 

for k in range(M):
   a = list(map(int, input().split()))      
 
cal = sum(t)
 
for j in range(M):
    print(cal - t[a[j][0] - 1] + a[j][1])

### FIXED CODE ###

N = int(input())
 
t = list(map(int, input().split()))
 
M = int(input())
 
cal = sum(t)
 
for j in range(M):
    p, x = map(int, input().split())
    print(cal - t[p - 1] + x)
import math
from decimal import Decimal
a,b,x = list(map(int,input().split()))
A = a**2
if A*b/2 <= x:
  c = Decimal(x/A)
  d = (b-c)*2
  print(90-(math.degrees(math.atan(Decimal(a/d)))))
else:
  s = Decimal(x/a)
  d = Decimal(s*2/b)
  print(90-(math.degrees(math.atan(Decimal(d/b)))))

### FIXED CODE ###

import math
from decimal import Decimal
a,b,x = list(map(int,input().split()))
A = a**2
if A*b == x:
  print(0)
elif A*b/2 <= x:
  c = Decimal(x/A)
  d = (b-c)*2
  print(90-(math.degrees(math.atan(Decimal(a/d)))))
else:
  s = Decimal(x/a)
  d = Decimal(s*2/b)
  print(90-(math.degrees(math.atan(Decimal(d/b)))))
import numpy as np
n,s=map(int,input().split())
t=np.zeros(s+1)
m=10**9+7
a=list(map(int,input().split()))
ans=0
for i in range(n):
    t[a[i]:]+=t[:-a[i]]
    t[a[i]]+=i+1
    ans+=t[-1]
    ans%=m
print(int(ans))

### FIXED CODE ###

n,s=map(int,input().split())
t=[0]*(s+1)
m=998244353
a=list(map(int,input().split()))
ans=0
for i in range(n):
    d=t.copy()
    if a[i]<=s:
        for j in range(a[i],s+1):
            t[j]+=d[j-a[i]]
        t[a[i]]+=i+1
    ans+=t[-1]
    ans%=m
print(int(ans))
list = []
x = 0
y = 0
n = int(input())
for i in range(n):
    a,b = map(int,input().split())
    list.append(a)
    list.append(b)
for _ in range(n):
    if list[x] == list[x+1]:
        n = n - 1
        if not list[x+1] == list[-1]:
            if list[x+2] == list[x+3]:
                n = n - 1
                if not list[x+3] == list[-1]:
                    if list[x+4] == list[x+5]:
                         n = n - 1
                         y = 1
    x = x + 2
if y == 0:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

n = input()
a = 's'
b = 'es'
if n[-1] == 's':
    n = n + b
else:
    n = n + a
print(n)
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort(reverse=True)
ans=0
a=[]
k=0
left = 0
right = len(x) - 1
for i in range(m):
    x[0]=x[0]//2
    while left <= right:
        mid = (left + right) // 2
        if  x[mid] >= x[0]>=x[mid+1]:
            x.insert(mid+1,x[0])
            x.remove(x[0])
            break               
        elif x[mid] > x[0]:
            right = mid - 1
        else:
            left = mid + 1
for j in range(n):
    ans+=x[j]
print(ans)

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
x=list(map(int,input().split()))
for k in range(n):
    x[k]-=2*x[k]
heapq.heapify(x)
ans=0
for i in range(m):
    maxvalue=heapq.heappop(x)*(-1)
    heapq.heappush(x,(maxvalue//2)*(-1))
ans=-1*sum(x)
print(ans)
NM = input().split()
N = int(NM[0])
M = int(NM[1])

sc = []
flg = False
for i in range(M):
  scc = input().split()
  sc.append([int(scc[0]), int(scc[1])])
  if int(scc[0]) == 1 and int(scc[1]) == 0:
    flg = True
else:
  string = ["0"]*N
  sc.sort(key=lambda x: x[0])
  s = []
  for i in range(M):
    if flg:
      break
    if i != M-1:
      if s and sc[i][0] == s[0][0]:
        s.append(sc[i])
      elif not s:
        s.append(sc[i])
      else:
        tmp = s[0][1]
        string[int(s[0][0])-1] = str(tmp)
        for sss in s:
          if sss[1] != tmp:
            flg = True
        s = []
        s.append(sc[i])
    else:
      if sc[i][0] == s[0][0]:
        s.append(sc[i])
        tmp = s[0][1]
        string[int(s[0][0])-1] = str(tmp)
        for sss in s:
          if sss[1] != tmp:
            flg = True
      else:
        tmp = s[0][1]
        string[int(s[0][0])-1] = str(tmp)
        for sss in s:
          if sss[1] != tmp:
            flg = True
        string[int(sc[i][0])-1] = str(sc[i][1])


if flg:
  print(-1)
else:
  string = "".join(string)
  if string == "0"*N:
    print('-1')
  else:
    print("".join(string))

### FIXED CODE ###

NM = input().split()
N = int(NM[0])
M = int(NM[1])

from collections import defaultdict
sc = defaultdict(lambda: -1)
flg = False
for i in range(M):
  scc = input().split()
  if sc[scc[0]] == -1:
    sc[scc[0]] = scc[1]
  else:
    if scc[0] == "1" and scc[1] == 0 and N != 1:
      flg = True
      break
    elif sc[scc[0]] != scc[1]:
      flg = True
      break
if not flg:
  if N == 1:
    string = ["0"]
    for key, value in sc.items():
      string[int(key)-1] = value
    string = "".join(string)
    print(string)
  else:
    string = ["0"]*N
    string[0] = "1"
    for key, value in sc.items():
      string[int(key)-1] = value
    string = "".join(string)
    if string == "0"*N:
      print(-1)
    else:
      print(string)

else:
  print("-1")