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

n = int(input())
l = list(map(int,input().split()))
l.sort()
cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if l[k]-l[j] < l[i] < l[k]+l[j]:
                cnt += 1
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
cnt = 0
for i in range(n-1, 1, -1):
    for j in range(i-1, 0, -1):
        plus = l[i]+l[j]
        minus = l[i]-l[j]
        bir = min(j, bisect.bisect(l, plus))
        bil = bisect.bisect(l, minus)
        if bir > bil:
            cnt += bir-bil
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for _ in range(m):
        a,b=map(lambda x:int(x)-1,input().split())
        A[a][b]=1
    # Warshall-Floyd
    B=[a[:] for a in A] # deep copy
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        B[i][j]=min(B[i][j],B[i][k]+B[k][j])
    # output
    length=INF
    index=-1
    for i in range(n):
        if(length>B[i][i]):
            length=B[i][i]
            index=i
    if(length==INF):
        print(-1)
        return
    # path restroration
    u=v=index
    path=[]
    while(B[u][v]!=A[u][v]):
        for w in range(n):
            if(B[u][v]==A[u][w]+B[w][v]):
                u=w
                path.append(w)
                break
    path.append(v)
    print(len(path))
    for v in path: print(v+1)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)

    # bfs
    def bfs(sv):
        prev=[-1]*n
        flag=False
        from collections import deque
        Q=deque([sv])
        while(Q):
            v=Q.popleft()
            for nv in E[v]:
                if(nv==sv):
                    flag=True
                    break
                elif(prev[nv]==-1):
                    prev[nv]=v
                    Q.append(nv)
            if(flag): break
        if(not flag):
            return [0]*(n+1)
        else:
            loop=[]
            while(v!=-1):
                loop.append(v)
                v=prev[v]
            loop.reverse()
            return loop

    # calculate
    ans=[0]*(n+1)
    for i in range(n):
        loop=bfs(i)
        if(len(loop)<len(ans)):
            ans=loop
    if(len(ans)==n+1):
        print(-1)
    else:
        print(len(ans))
        for v in ans: print(v+1)
resolve()
### BUGGY CODE ###

n,k=map(int,input().split())
li=[[0,0] for i in range(n)]
for i in range(n):
    li[i][0],li[i][1]=map(int,input().split())



def find_num_neta(choice,li):
    k=[]
    for i in choice:
        k.append(li[i][0])
    return len(set(k))
#-----------------------------------------

li.sort(reverse=True,key=lambda x:x[1])
s2=min(find_num_neta(list(range(n)),li),k)
s1=find_num_neta(list(range(k)),li)

#-----------------------------------------
li.sort(key=lambda x:x[0])
best_list=[]
not_best_list=[]


m=-1
for i in li:
    if m==i[0]:
        not_best_list.append(i)
    else:
        best_list.append(i)
        m=i[0]
        
not_best_list.sort(reverse=True,key=lambda x:x[1])
best_list.sort(reverse=True,key=lambda x:x[1])



 
 
score=-1
for i in range(s1,s2+1):
    oishisa=0
    for j in range(i):
        oishisa+=best_list[j][1]
    for j in range(k-i):
        oishisa+=not_best_list[j][1]
    
    new_score=i**2+oishisa
    
    if score<new_score:
        score=new_score
        
    
print(score)


### FIXED CODE ###

n,k=map(int,input().split())
li=[[0,0] for i in range(n)]
for i in range(n):
    li[i][0],li[i][1]=map(int,input().split())



def find_num_neta(choice,li):
    k=[]
    for i in choice:
        k.append(li[i][0])
    return len(set(k))
#-----------------------------------------

li.sort(reverse=True,key=lambda x:x[1])
s2=min(find_num_neta(list(range(n)),li),k)
s1=find_num_neta(list(range(k)),li)
oishisa=sum([li[i][1] for i in range(k)])
score=oishisa+s1**2

#-----------------------------------------
li.sort(key=lambda x:x[0])
best_list=[]
not_best_list=[]


m=-1
for i in li:
    if m==i[0]:
        not_best_list.append(i)
    else:
        best_list.append(i)
        m=i[0]
        
not_best_list.sort(reverse=True,key=lambda x:x[1])
best_list.sort(reverse=True,key=lambda x:x[1])



 
 
for i in range(s1+1,s2+1):
    oishisa=oishisa+best_list[i-1][1]-not_best_list[k-i][1]
    
    new_score=i**2+oishisa
    
    if score<new_score:
        score=new_score
        
    
print(score)
### BUGGY CODE ###

n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * n
r = [n] * n
for _ in range(q):
  m,q = list(map(int, input().split()))
  if m == 1:
    pos = r[q-1]
    c[:pos] = [min(q, v) for v in c[:pos]] 
    r[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos - 2)
  else:
    pos = c[q-1]
    r[:pos] = [min(q, v) for v in r[:pos]]
    c[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos-2)
print(count)

### FIXED CODE ###

import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * (n + 1)
r = [n] * (n + 1)
mc = n
mr = n
for _ in range(q):
    m,q = list(map(int, input().split()))
    if m == 1:
        if q <= mc:
            count -= mr -2
            for p in range(q+1, mc):
                c[p] = mr
            c[q] = 0
            mc = q
        else:
            count -= c[q] - 2
    else:
        if q <= mr:
            count -= mc -2
            for p in range(q+1, mr):
                r[p] = mc
            r[q] = 0
            mr = q
        else:
            count -= r[q] - 2
print(count)
### BUGGY CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

def resolve():

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


    dp=[1]*(N+1)
    for i in A:
        dp[i]=0

    for i in range(2,N+1):
        if i not in A:
            dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)

    print(dp[N])

resolve()

### FIXED CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

def resolve():

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


    dp=[1]*(N+1)
    for i in A:
        dp[i]=0

    for i in range(2,N+1):
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)*dp[i]

    print(dp[N])

resolve()
### BUGGY CODE ###

from collections import deque
from copy import deepcopy
N, M, K = map(int, input().split())
SNS = [[0 for _ in range(N+1)] for __ in range(N+1)]
Follow = [deque() for __ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  SNS[a][b] = 1
  SNS[b][a] = 1
  Follow[a].append(b)
  Follow[b].append(a)
for _ in range(K):
  a, b = map(int, input().split())
  SNS[a][b] = -1
  SNS[b][a] = -1
Chains = []
seen = [False]*(N+1)
i = 1
while i <= N:
  if not seen[i]:
    seen[i] = True
    chain = deque()
    q = deque(deepcopy(Follow[i]))
    memo = [False]*(N+1)
    while q:
      j = q.pop()
      if not memo[j]:
        memo[j] = True
        seen[j] = True
        chain.append(j)
        for k in Follow[j]:
          q.append(k)
    Chains.append(deepcopy(chain))
  i += 1
ans = [0] * (N+1)
for chain in Chains:
  l = len(chain)
  for hito in chain:
    n = 0
    for aite in chain:
      n += 0 if SNS[hito][aite] == 0 else 1
    ans[hito] = l - n -1
s = ""
i = 1
while i <= N:
  s += "%d "%ans[i]
  i += 1
print(s)

### FIXED CODE ###

from collections import deque
from copy import deepcopy

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M, K = map(int, input().split())
UF = UnionFind(N+1)
direct_connect = [0]*(N+1)
for _ in range(M):
  a, b = map(int, input().split())
  UF.union(a, b)
  direct_connect[a] += 1
  direct_connect[b] += 1
for _ in range(K):
  a, b = map(int, input().split())
  if UF.same(a, b):
    direct_connect[a] += 1
    direct_connect[b] += 1
ans = ""
for i in range(1, N+1):
  ans += "%d "%(UF.size(i)-direct_connect[i]-1)
print(ans)
### BUGGY CODE ###

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

lst = [0] * N
skips = [int(input()) for _ in range(M)]
for x in range(N):
    if x in skips:
        lst[x] = 0
    elif x in [0, 1]:
        lst[x] = 1
    else:
        lst[x] = lst[x - 1] + lst[x - 2]

if N == 1:
    print(lst[-1] % 1000000007)
else:
    print((lst[-1] + lst[-2]) % 1000000007)


### FIXED CODE ###

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

lst = [0] * N
pre1 = 0
pre2 = 0
skips = set([int(input()) for _ in range(M)])
for x in range(N):
    if x in skips:
        lst[x] = 0
    elif x in [0, 1]:
        lst[x] = 1
    else:
        lst[x] = (lst[x - 1] + lst[x - 2]) % 1000000007

if N == 1:
    print(lst[-1])
else:
    print((lst[-1] + lst[-2]) % 1000000007)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
result=10000000000
total=0
for i in range(n-1):
    total +=a[i]
    if abs(sum(a)-2*total)<result:
        result=abs(sum(a)-2*total)
print(result)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
result=10000000000
total=0
suma=sum(a)
for i in range(n-1):
    total +=a[i]
    sa = abs(suma - 2*total)
    if sa <result:
        result=sa
print(result)
### BUGGY CODE ###

N, X, Y = map(int, input().split())

l = [0 for _ in range(N)]
line = []

for i in range(1, N+1):
    for j in range(1, N+1):
        if i < j:
            l[min(abs(i-j), abs(X-i)+1+abs(Y-j), abs(X-j)+1+abs(Y-i))] += 1

for k in range(1, N):
    print(l[k])


### FIXED CODE ###

N, X, Y = map(int, input().split())

l = [0 for _ in range(N)]
line = []

for i in range(1, N+1):
    for j in range(1, N+1):
        if i < j:
            l[min(abs(i-j), abs(X-i)+1+abs(Y-j), abs(X-j)+1+abs(Y-i))] += 1

for k in range(1, N):
    print(l[k])
### BUGGY CODE ###

import sys

N, M = map(int, input().split())
li = [list(map(int, input().split())) for n in range(M)]

a = []
b = []

for i in li:
  if i[1] == N:
    b.append(i[0])

  if i[0] == 1:
    a.append(i[1])
    
if len(a) == 0 or len(b) == 0:
  print("IMPOSSIBLE")
  sys.exit()
    
for i in a:
  if i in b:
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")

### FIXED CODE ###

import sys
from collections import defaultdict
d = defaultdict(int)

N, M = map(int, input().split())
li = [list(map(int, input().split())) for n in range(M)]

for i in li:
  if i[1] == N:
    d[i[0]] += 1

for i in li:
  if i[0] == 1 and d[i[1]] != 0:
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")
### BUGGY CODE ###

N, M = map(int, input().split())
p = []
S = []

for i in range(M) :
  tmp = input().split()
  p.append(int(tmp[0]))
  S.append(tmp[1])

s = set(p)
dict = {}
for i in s :
  dict[i] = 0
# print(dict)
w_cnt = 0
a_cnt = 0
skip = []
for i in range(M) :
  if p[i] not in skip :
    if S[i] == 'WA' :
      dict[p[i]] += 1
      continue
    elif S[i] == 'AC' :
      a_cnt += 1
      w_cnt += dict[p[i]]
      skip.append(p[i])
      continue
  else :
    continue
  # print(a_cnt, w_cnt)

print(a_cnt, w_cnt)

### FIXED CODE ###

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

p = [0]*(n+1)
q = [False]*(n+1)

for _ in range(m) :
  v,s = input().split()
  v = int(v)
  if q[v] : continue
  if s[0] == 'A' : q[v] = True
  else : p[v] += 1

print(sum(q), sum(p[i] for i in range(n+1) if q[i]))
### BUGGY CODE ###

N,M = (int(x) for x in input().split())
cor = 0
mis = 0
numList = []
misList = {}

for _ in range(M):

    num,ans = input().split()

    if num not in numList:
        if num not in misList.keys():
            misList[num] = 0
            
        if ans == 'AC':
            cor += 1
            numList.append(num)
            mis += misList[num]
        else:
            misList[num] += 1

print(cor,mis)





### FIXED CODE ###

N,M = (int(x) for x in input().split())
cor = 0
mis = 0
numList = [0] * N
misList = [0] * N

for _ in range(M):
    num,ans = input().split()

    if ans == 'WA':
        misList[int(num)-1] += 1
    else:
        if numList[int(num)-1] == 0:
            mis += misList[int(num)-1]
            cor += 1
            numList[int(num)-1] = 1

print(cor,mis)
### BUGGY CODE ###

N, A, B = map(int, input().split())
round_count = 0

med = N / 2 + 0.5
maxAB = 10 ** 18

for i in range(maxAB):
    if abs(A - B) % 2 == 0:
        if A > B:
            A = A - 1
            B = B + 1

            if A < 1:
                A = 1
            elif B > N:
                B = N
        else:
            A = A + 1
            B = B - 1

            if A > N:
                A = N
            elif B < 1:
                B = 1
    else:
        Max = max([A, B])
        Min = min([A, B])
        medAB = (Max + Min) / 2
        if medAB > med:
            A = A + 1
            B = B + 1

            if A > N:
                A = N
            elif B > N:
                B = N
        else:
            A = A - 1
            B = B - 1

            if A < 1:
                A = 1
            elif B < 1:
                B = 1

    round_count = round_count + 1

    if A == B:
        break

print(round_count)

### FIXED CODE ###

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

med = N / 2 + 0.5
Sub = B - A

if (Sub) % 2 == 0:
    round_count = Sub // 2
else:
    round_count = min(A - 1, N - B) + 1 + (Sub - 1) // 2
            
print(round_count)
### BUGGY CODE ###

n=int(input())
p=1
for i in range(1,n+1):
  p*=i
print(p%(10**9 + 7))

### FIXED CODE ###

import math
print(math.factorial(int(input()))%(10**9 + 7))
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
n = len(s)
cs = [0] * (n + 1)
for i, x in enumerate(s):
    cs[i + 1] = cs[i] + int(x)
ans = 0
for i in range(n):
    for j in range(i + 3, n + 1):
        if (cs[j] - cs[i]) % 3 != 0:
            continue
        if int(s[i:j]) % 2019 == 0:
            ans += 1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
s = input()[::-1]
n = len(s)
cs = [0] * (n + 1)
ten = 1
for i in range(n):
    cs[i + 1] = int(s[i]) * ten % 2019
    ten = ten * 10 % 2019
for i in range(n):
    cs[i + 1] = (cs[i + 1] + cs[i]) % 2019
cnt = [0] * 2019
for i, x in enumerate(cs):
    cnt[x] += 1
ans = sum(x * (x - 1) // 2 for x in cnt)
print(ans)
### BUGGY CODE ###

def is_needed(i):
    dp = [False] * k
    dp[0] = True
    for j, w in enumerate(aa):
        if i == j:
            continue
        for l in range(k - 1, w - 1, -1):
            if dp[l - w]:
                dp[l] = True
    return any(dp[k - aa[i]:])


n, k = map(int, input().split())
aa = sorted(map(int, input().split()))

l, h = 0, n - 1
while l <= h:
    c = (l + h) // 2
    if is_needed(c):
        h = c - 1
    else:
        l = c + 1
print(l)


### FIXED CODE ###

import bisect


def solve(k, aaa):
    aaa = aaa[:bisect.bisect_left(aaa, k)]

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    ans = len(aaa)
    for i, a in reversed(list(enumerate(aaa))):
        if curr_max + a >= k:
            ans = i
        f = True
        for j in range(min(curr_max, k - a - 1), -1, -1):
            if dp[j]:
                dp[j + a] = True
                if f:
                    curr_max = max(curr_max, j + a)
                    f = False
    return ans


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

print(solve(k, aaa))
### BUGGY CODE ###

def prime(n):
    seq = list(range(2, n+1))
    while len(seq) > 0:
        prime = seq.pop(0)
        yield prime
        seq = [i for i in seq if not i % prime == 0]


while True:
	try:
		n=input()
		print len( list(prime(n)) )

	except EOFError:
		break


### FIXED CODE ###

import sys

N=999999
a=[ 1 for i in range(N+1)]
a[0]=0
a[1]=0
for i in range(2, N+1):
	for j in range(i*i,N+1,i):
		a[j]=0


b=[ 0 for i in range(N+1)]
t=0
for i in range(2,N+1):
	t+=a[i]
	b[i]=t


for line in sys.stdin:
	n=int(line)
	print b[n]
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
totals=[0]*n

for i in range(n-1,-1,-1):
    if totals[i]%2==a[i]:
        continue
    else:
        ans[i]+=1
        tmp=1
        while tmp*tmp<=i+1:
            if (i+1)%tmp==0:
                totals[tmp-1]+=1
                if tmp !=(i+1)//tmp:
                    totals[((i+1)//tmp)-1]+=1

            tmp+=1


cnt=ans.count(1)

print(cnt)
if cnt!=0:
    b=[]
    for j in range(n):
        if ans[j]==1:
            b.append(j+1)

    print(*b)
    

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
totals=[0]*n


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]


for i in range(n-1,-1,-1):
    if totals[i]%2==a[i]:
        continue
    else:
        ans[i]+=1
        arr=make_divisors(i+1)

        for num in arr:
            totals[num-1]+=1

cnt=ans.count(1)

print(cnt)
if cnt!=0:
    b=[]
    for j in range(n):
        if ans[j]!=0:
            b.append(j+1)

    print(*b)
### BUGGY CODE ###

n = int(input())
lst = list(map(int,input().split()))
mod = 10**9+7

bit_lst = []
for i in range(n):
    bit_lst.append(format(lst[i], '060b'))
    
ans = 0
for i in range(60):
    tmp = []
    for j in range(n):
        tmp.append(bit_lst[j][i])
    
    cnt_one = tmp.count('1')
    cnt_zero = n - cnt_one
    
    tmp = cnt_one * cnt_zero
    for j in range(59 - i):
        tmp = (tmp * 2) % mod
    ans += tmp
print(ans%mod)

### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array(list(map(int,input().split())))

mod = 10**9 + 7
ans = 0

for j in range(60):
    li = (a >> j) & 1
    i = np.count_nonzero(li)
    o = n - i
    ans += i*o*2**j
    ans %= mod

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

import sys
sys.setrecursionlimit(1000000)

n,m = map(int,input().split())
# 差が0だと通れない
tmp=10000000
a_list=[]
for i in range(m):
    a=int(input())
    a_list.append(a)
    if abs(tmp-a)==1:
        print(0)
        exit()
    tmp=a

cntmap={0:1}

def count(now,s,e):
    if now > e:
        return 0
    if now == e:
        return 1
    cnt=0
    cnt+=count(now+1,s,e)
    cnt+=count(now+2,s,e)
    return cnt


c_mod=1000000007
start=0
end=0
ans=1
for a in a_list:
    # 各部分の移動方法
    end=a-1
    if (end-start) in cntmap:
        ans=ans*cntmap[end-start]%c_mod
    else:
        res=count(start,start,end)
        cntmap[end-start]=res
        ans=ans*res%c_mod

    start=a+1
if end<n:
    end=n
    if (end-start) in cntmap:
        ans=ans*cntmap[end-start]%c_mod
    else:
        res=count(start,start,end)
        ans=ans*res%c_mod
print(ans)


### FIXED CODE ###

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

step=[0]*(n+1)
for _ in range(m):
    a=int(input())
    step[a-1]=-1

if step[0]!=-1:
    step[0]=1
if step[1]!=-1:
    step[1]=1
for i in range(n-1):
    if step[i]==-1:
        continue
    if step[i+1]!=-1:
        step[i+1]+=step[i]
    if step[i+2]!=-1:
        step[i+2]+=step[i]
print(step[n-1]%c_mod)
### BUGGY CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

A,B,N=map(int,input().split())
def main(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(int(A*x/B)-A*int(x/B))
st=1
ed=N
C=max(main(st),main(ed))
while ed-st>2:
    #print(ed,st)
    mid1=(st*2+ed)//3
    mid2=(st+ed*2)//3
    C0=main(st)
    C1=main(mid1)
    C2=main(mid2)
    C3=main(ed)
    C=max(C,C0,C1,C2,C3)
    if C0==C:
        ed=mid2
    elif C1==C:
        ed=mid2
    elif C2==C:
        st=mid1
    elif C3==C:
        st=mid1
if ed-st==2:
    C=max(main(st),main(st+1),main(ed),C)
print(C)


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

A,B,N=map(int,input().split())
def main2(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(int(A*x/B)-A*int(x/B))
def main(x):
    #print(x,int(A*x/B),A*int(x/B))
    return(A*x//B-A*(x//B))

if N>=B-1:
    Z=B-1
else:
    Z=N
print((main2(Z)))

#print(C)
### BUGGY CODE ###

N,M = map(int,input().split())
key_list = []
for i in range(M):
  a,b = map(int,input().split())
  bin_int = 0
  c = list(map(int,input().split()))
  for C in c:
    bin_int += 2 ** (C - 1)
  key_list.append([a, bin_int])

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

for i in range(M):
  dp_i = dp[i]
  dp_i1 = dp[i + 1]
  key = key_list[i]

  for j in range(n1):
    dp_key = dp_i[j]
    dp_i1[j] = min(dp_key, dp_i1[j])
    dp_i1[j | key[1]] = min(dp_key + key[0], dp_i1[j | key[1]])
  # print(dp)
ans = dp[M - 1][n1 - 1]
if ans == 120001:
  print(-1)
else:
  print(dp[M - 1][n1 - 1])

### FIXED CODE ###

N,M = map(int,input().split())
key_list = []
for i in range(M):
  a,b = map(int,input().split())
  bin_int = 0
  c = list(map(int,input().split()))
  for C in c:
    bin_int += 2 ** (C - 1)
  key_list.append([a, bin_int])

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

for i in range(M):
  dp_i = dp[i]
  dp_i1 = dp[i + 1]
  key = key_list[i]

  for j in range(n1):
    dp_key = dp_i[j]
    dp_i1[j] = min(dp_key, dp_i1[j])
    dp_i1[j | key[1]] = min(dp_key + key[0], dp_i1[j | key[1]])
  # print(dp)
ans = dp[M - 1][n1 - 1]
if ans == 120001:
  print(-1)
else:
  print(dp[M - 1][n1 - 1])
### BUGGY CODE ###

size = int(input())
ans = []
li = list(map(int,input().split()))
for i in range(1,size+1):
    ans.append(li.index(i)+1)
for i in ans:
    print(i,end =" ")

### FIXED CODE ###

size = int(input())
ans = []
li = list(map(int,input().split()))
a = list(enumerate(li))
list2 = sorted(a, key=lambda x:x[1])
for i,j in list2:
    print(i+1,end=" ")
### BUGGY CODE ###

n,m=map(int,input().split())
step=list(range(n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
enable=[i for i in step if not i in broken and not i == 0]
dp=[0]*(n+1)
dp[0]=1
if enable[0]==1:
    dp[1]=1
    enable.pop(0)
for i in enable:
    dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[n])

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = {i: 0 for i in range(N+1)}
mod = 10 ** 9 + 7
for _ in range(M):
    A[int(input())] = 1
 
dp = [0 for _ in range(N+1)]
dp[0] = 1
 
for i in range(N+1):
    if A.get(i+1) == 0:
        dp[i + 1] += dp[i]
    if A.get(i+2) == 0:
        dp[i + 2] += dp[i]
 
print(dp[N]%mod)