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

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

temp = [ [0 for _ in range(n)] for _ in range(n)]
tables = [ [0 for _ in range(n)] for _ in range(n)]

for _ in range(m):
    l, r = map(int, input().split())
    temp[l - 1][r - 1] += 1

pq = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

for i in range(n):
    hoge = 0
    for j in range(n):
        hoge += temp[i][j]
        tables[i][j] = hoge

for p, q in pq:
    ans = 0
    if p > 0:
        for i in range(p, q + 1):
            ans += tables[i][q] - tables[i][p - 1]
    else:
        for i in range(q + 1):
            ans += tables[i][q]
    print(ans)

### FIXED CODE ###

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

temp = [ [0 for _ in range(n)] for _ in range(n)]
tables = [ [0 for _ in range(n)] for _ in range(n)]

if n == 1:
    print('1')
    exit()

for _ in range(m):
    l, r = map(int, input().split())
    temp[l - 1][r - 1] += 1

pq = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

hoge = 0
for j in range(n):
    hoge += temp[0][j]
    tables[0][j] = hoge

for i in range(1, n):
    hoge = 0
    for j in range(n):
        hoge += temp[i][j]
        tables[i][j] = tables[i - 1][j] + hoge

for p, q in pq:
    if p == 0:
        print(tables[q][q])
    else:
        print(tables[q][q] - tables[p - 1][q] - tables[q][p - 1] + tables[p - 1][p - 1] )
### BUGGY CODE ###

H, W, M = map(int,input().split())
ARR = []

for i in range(M):
    ARR.append(list(map(int,input().split())))

def calculate(h, w, m, arr):
    points = set()



    rowSum = [0 for i in range(h)]
    columnSum = [0 for i in range(w)]

    for ar in arr:
        points.add((ar[0]-1, ar[1]-1))
        rowSum[ar[0]-1] += 1
        columnSum[ar[1]-1] += 1

    maxRowSum = max(rowSum)
    maxColumnSum = max(columnSum)


    a0 = []

    for i in range(len(rowSum)):
        if rowSum[i] == maxRowSum:
            a0.append(i)

    a1 = []
    for i in range(len(columnSum)):
        if columnSum[i] == maxColumnSum:
            a1.append(i)

    result = 0
    for hIndex in a0:
        for wIndex in a1:
            if (hIndex,wIndex) in points:
                result = max(result, maxRowSum + maxColumnSum - 1)
            else:
                result = max(result, maxRowSum + maxColumnSum)

    print(result)


calculate(H, W, M, ARR)


### FIXED CODE ###

H, W, M = map(int,input().split())
ARR = []

for i in range(M):
    ARR.append(list(map(int,input().split())))

def calculate(h, w, m, arr):
    points = set()



    rowSum = [0 for i in range(h)]
    columnSum = [0 for i in range(w)]

    for ar in arr:
        points.add((ar[0]-1, ar[1]-1))
        rowSum[ar[0]-1] += 1
        columnSum[ar[1]-1] += 1

    maxRowSum = max(rowSum)
    maxColumnSum = max(columnSum)


    a0 = []

    for i in range(len(rowSum)):
        if rowSum[i] == maxRowSum:
            a0.append(i)

    a1 = []
    for i in range(len(columnSum)):
        if columnSum[i] == maxColumnSum:
            a1.append(i)

    result = 0
    for hIndex in a0:
        for wIndex in a1:

            if (hIndex,wIndex) in points:
                result = max(result, maxRowSum + maxColumnSum - 1)
            else:
                result = max(result, maxRowSum + maxColumnSum)
                print(result)
                exit()

    print(result)


calculate(H, W, M, ARR)
### BUGGY CODE ###

from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())
time_graph = [[] for _ in range(n + 1)]
money_graph = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    time_graph[v].append((b, u))
    time_graph[u].append((b, v))
    money_graph[u][v] = a
    money_graph[v][u] = a


rate = [(0, 0) for _ in range(n + 1)]
for i in range(1, n + 1):
    c, d = map(int, input().split())
    rate[i] = (c, d)

start = 1

time = [infi] * (n + 1)
time[start] = 0
que = [(0, s, start)]
cnt = 0
visited = set()
used_pair = set()
cnt = 0
while que:
    t_edge, m_edge, edge = heappop(que)
    if (t_edge, m_edge, edge) in used_pair:
        continue
    used_pair.add((t_edge, m_edge, edge))
    if time[edge] > t_edge:
        time[edge] = t_edge
    if not (edge in visited):
        cnt += 1
        visited.add(edge)
    if cnt == n:
        break
    delta_money, delta_time = rate[edge]
    heappush(que, (t_edge + delta_time, m_edge + delta_money, edge))
    for t_newedge, newedge in time_graph[edge]:
        newtime = t_edge + t_newedge
        newmoney = m_edge - money_graph[edge][newedge]
        if newmoney < 0:
            continue
        heappush(que, (newtime, newmoney, newedge))

print(*time[2:], sep="\n")


### FIXED CODE ###

from heapq import heappush, heappop

infi = 10 ** 20
n, m, s = map(int, input().split())

s = min(s, 2500)

edges = [[] for _ in range(51 * 2501 + 1)]
# edge:1-50, max silver=0-2500

for _ in range(m):
    u, v, a, b = map(int, input().split())
    for i in range(a, 2501):
        edges[v + 50 * i].append((b, u + 50 * (i - a)))
        edges[u + 50 * i].append((b, v + 50 * (i - a)))


for edge_num in range(1, n + 1):
    c, d = map(int, input().split())
    # c枚, d分
    for i in range(2501):
        # 点edge_num+ i * 50のところに
        if edge_num + (i + c) * 50 <= 51 * 2501:
            edges[edge_num + i * 50].append((d, edge_num + min((i + c), 2500) * 50))
start = 1 + 50 * s


def dijkstra(edges, start):
    time = [infi] * (51 * 2501 + 1)
    used = [False] * (51 * 2501 + 1)
    # time[i][j] 頂点i, 銀貨jのときの時間
    time[start] = 0
    edgelist = []
    heappush(edgelist, (0, start))
    while edgelist:
        nowtime, nowedge = heappop(edgelist)
        if used[nowedge] is True:
            continue
        used[nowedge] = True
        time[nowedge] = nowtime
        for vt, v in edges[nowedge]:
            if used[v] is True:
                continue
            newtime = nowtime + vt
            heappush(edgelist, (newtime, v))
    return time


time = dijkstra(edges, start)

ans = [infi] * (51)
for i in range(1, 51 * 2501 + 1):
    temp = time[i]
    a = i % 50
    if a == 0:
        a += 50
    ans[a] = min(temp, ans[a])

print(*ans[2 : (n + 1)], sep="\n")
### BUGGY CODE ###

import sys
from collections import deque
import copy

input = sys.stdin.readline

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for _ in range(h)]

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(2,2), (2,1), (2,0), (2,-1), (2,-2), (1,2), (1,1), (1,-1), (1,-2), (0,2), (0,-2), (-1,2), (-1,1),(-1,-1), (-1,-2), (-2,2), (-2,1), (-2,0),(-2,-1),(-2,-2)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
q2 = deque([(ch-1, cw-1)])
q3 = deque([])
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))

    for i,j in q2:
        for ii,jj in d2:
            if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp+1
                    q.append((i+ii,j+jj))
                    q3.append((i+ii,j+jj))
    if not q:
        break
    tmp += 1
    q2 = copy.copy(q3)

print(v[dh-1][dw-1])


### FIXED CODE ###

import sys
from collections import deque
import copy

input = sys.stdin.readline

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for _ in range(h)]

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(2,2), (2,1), (2,0), (2,-1), (2,-2), (1,2), (1,1), (1,-1), (1,-2), (0,2), (0,-2), (-1,2), (-1,1),(-1,-1), (-1,-2), (-2,2), (-2,1), (-2,0),(-2,-1),(-2,-2)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
q2 = [(ch-1, cw-1)]
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))

    cnt = 0
    for k in range(len(q2)):
        i,j = q2[k][0], q2[k][1]
        for ii,jj in d2:
            if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp+1
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))
                    cnt += 1
    if not q:
        break
    tmp += 1
    q2 = q2[-cnt:]
print(v[dh-1][dw-1])
### BUGGY CODE ###

n = int(input())
a = [int(_) for _ in input().split()]

a_sorted = sorted(a, reverse=True)
x = 0
y = 0

while True:
    if len(a_sorted) == 0:
        break
    max = a_sorted[0]
    if x != 0 and y != 0:
        break
    if a_sorted.count(max) >= 2:
        if x == 0:
            x = max
        else:
            y = max
        a_sorted.remove(max)
        a_sorted.remove(max)
    else:
        a_sorted.remove(max)
print(x * y)

### FIXED CODE ###

n = int(input())
a = [int(_) for _ in input().split()]

a_sorted = sorted(a, reverse=True)
x = 0
y = 0

while True:
    if len(a_sorted) <= 1:
        break
    max = a_sorted[0]
    if x != 0 and y != 0:
        break
    if a_sorted[1] == max:
        if x == 0:
            x = max
        else:
            y = max
        a_sorted.remove(max)
        a_sorted.remove(max)
    else:
        a_sorted.remove(max)
print(x * y)
### BUGGY CODE ###

import collections as C
n, q = map(int,input().split())

g = C.Counter([])
p = C.Counter([])

for i in range(n-1):
	a,b = map(int,input().split())
	if a not in g.keys():
		g[a] = [b]
	else:
		g[a] = g[a] + [b]

for i in range(q):
	a,b = map(int,input().split())
	if a not in p.keys():
		p[a] = b
	else:
		p[a] = p[a] + b

ans = [0 for _ in range(n)]
que = [0]
i = 1
while i > 0:

	if i in p.keys():
		ans[i-1] += p[i]
	if i in g.keys():
		for j in g[i]:
			ans[j-1] = ans[i-1]
			que.append(j)
	i = que.pop()


for i in ans:
	print(i, end=" ")






### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N, Q = map(int ,input().split())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
	at,bt = map(int ,input().split())
	E[at].append(bt)
	E[bt].append(at)
cnt = [0 for _ in range(N+1)]
for _ in range(Q):
	pt,xt = map(int, input().split())
	cnt[pt] += xt

flg = [0 for _ in range(N+1)]
q = [[1,-1]]
while q:
	cp, root = q.pop()
	for np in E[cp]:
		if np == root:
			continue
		cnt[np] += cnt[cp]
		q.append([np,cp])

cnt.pop(0)
for c in cnt:
	print(c, end = " ")
print()
### BUGGY CODE ###

S = input()
n = len(S)

dp = [[0]*3 for i in range(n+1)]
cnt = 0 #はてなの数
#初期は後で構築
mod = 10**9 + 7 

for i in range(n):
    if S[i] == "A":
        dp[i+1][0] = dp[i][0] + int(3**(cnt))
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][2]
    elif S[i] == "B":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][0] + dp[i][1]
        dp[i+1][2] = dp[i][2]
    elif S[i] == "C":
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][1] + dp[i][2]
    elif S[i] == "?":
        dp[i+1][0] = dp[i][0] * 3 + int(3**(cnt))
        dp[i+1][1] = dp[i][1] * 3 + dp[i][0]
        dp[i+1][2] = dp[i][2] * 3 + dp[i][1]        
        cnt += 1

print(dp[n][2]%mod)

### FIXED CODE ###

"""
We Love ABC
DP使う問題
T : 文字列
i < j < k < len(T)
Ti = "A"
Tj = "B"
Tk = "C"
i j k の順で取れたら、1カウント
- TはA, B, C, ? で構成される
- ? は　ABC のいずれか
これらを満たす場合の数

i番目の文字において、ABCのどこまで進んだか
null:   0
A   :   1
B   :   2
C   :   3

?の扱いが厄介
?があると単純に選択肢が3倍になる
A? -> AA, AB, AC
B? -> BA, BB, BC
まだ選んでいない時 : 入力の選択肢が3倍に増える
dp[i+1][1]: 
    すでにAを選んでいる時 : iまでのAの選び方が3倍に増えるので、dp[i][1]*3
    何も選んでいない場合  : ?がAになれるので、dp[i][0]を加える
ほかも同じ
"""
mod = 10**9 + 7

S = input()
N = len(S)
dp = [[0]*4 for i in range(100800)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    dp[i+1][0] = dp[i][0] 
    dp[i+1][1] = dp[i][1] 
    dp[i+1][2] = dp[i][2] 
    dp[i+1][3] = dp[i][3] 
    if s == "A":
        # Aを選ぶ選択肢がそれまでのA,?分増える
        dp[i+1][1] += dp[i][0]
    if s == "B":
        # Bを選ぶ選択肢がそれまでのAの選択肢分増える
        dp[i+1][2] = dp[i][2] + dp[i][1] 
    if s == "C":
        # Cを選ぶ選択肢がBまでを選んだ分だけ増える
        dp[i+1][3] = dp[i][3] + dp[i][2]
    if s == "?":
        # ?を選んだ場合。選択肢は3倍に広がる
        dp[i+1][0] = (3*dp[i][0])%mod
        dp[i+1][1] = (dp[i][0] + 3*dp[i][1]) % mod
        dp[i+1][2] = (dp[i][1] + 3*dp[i][2]) % mod
        dp[i+1][3] = (dp[i][2] + 3*dp[i][3]) % mod
        
# Cまで行った数を求める
print(dp[N][3]%mod)
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
ans = 0
cpn = 0
for i in range(a,b+1):
  if i % c == 0 or i % d == 0:
    cpn = 0
  else:  
    ans += 1
print(ans)


### FIXED CODE ###

A,B,C,D = map(int,input().split())

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

def F(N,C,D):
  x = N
  x -= N//C
  x -= N//D
  lcm = C*D//gcd(C,D)
  x += N//lcm
  return x

answer = F(B,C,D) - F(A-1,C,D)
print(answer)
### BUGGY CODE ###

Neg_INF=-10**10

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

P=list(map(int,input().split()))
C=list(map(int,input().split()))

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

ans=Neg_INF
for i in range(1,K+1):
    for j in range(N):
        dp[j][i]=dp[P[j]-1][i-1]+C[P[j]-1]
        if ans<dp[j][i]:
            ans=dp[j][i]

print(ans)

### FIXED CODE ###

INF=10**20

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

array=list(map(int,input().split()))
P=[]
C=list(map(int,input().split()))
for i in array:
    P.append(i-1)

ans=-1*INF

for i in range(N):
    v=i
    cycle_sum=0
    cycle_cnt=0

    while(True):
        cycle_cnt+=1
        cycle_sum+=C[v]
        v=P[v]
        if v==i:
            break

    path=0
    cnt=0

    while(True):
        cnt+=1
        path+=C[v]

        if cnt>K:
            break

        num=(K-cnt)//cycle_cnt
        score=path+max(0,cycle_sum)*num
        ans=max(ans,score)

        v=P[v]
        if v==i:
            break

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

n, q = map(int, input().split())
s = input()
for i in range(q):
  l, r = map(int, input().split())
  ans = 0
  for i in range(l-1, r-1):
    if s[i]=='A' and s[i+1]=='C':
      ans += 1
  
  print(ans)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split())) for i in range(q)]
data=[0]*(n+1)
if s[0]=='A' and s[1]=='C':
  data[1]=1
for i in range(1,n-1):
  if s[i]=='A' and s[i+1]=='C':
    data[i+1]+=1
  data[i+1]+=data[i]
data[n]=data[n-1]
for i in range(q):
  print(data[lr[i][1]-1]-data[lr[i][0]-1])
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    py = [list(map(int, input().split())) for _ in range(m)]

    summary = [[] for _ in range(n)]

    for p, y in py:
        summary[p - 1].append(y)

    for i in range(n):
        summary[i].sort()

    for p, y in py:
        print(str(p).zfill(6), str(summary[p - 1].index(y) + 1).zfill(6), sep='')


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit
from bisect import bisect_left


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    py = [list(map(int, input().split())) for _ in range(m)]

    summary = [[] for _ in range(n)]

    for p, y in py:
        summary[p - 1].append(y)

    for i in range(n):
        summary[i].sort()

    for p, y in py:
        print(str(p).zfill(6), str(bisect_left(summary[p - 1], y) + 1).zfill(6), sep='')


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

import math
a, b, n = map(int, input().split())
ans = -100
for x in range(1, n+1):
    fx = math.floor(a*x/b) - a * math.floor(x/b)
    if ans < fx:
        ans = fx
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
y = 0
if n >= b:
    y = b - 1
else:
    y = n
print(int(a*y/b))
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]
#かぶった回数
cnt = 0
already = [""]
for i in range(N):
    for j in range(len(already)):
        if(S[i] == already[j]):
            cnt += 1
            break
        else:
            already.append(S[i])
print(N - cnt)

### FIXED CODE ###

N = int(input())
S = sorted(list(input() for i in range(N)))
cnt = 0
for i in range(1, N):
    if(S[i-1] != S[i]):
        cnt += 1
print(cnt + 1)
### BUGGY CODE ###

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

number_sum = []
for i in range(N+1-K):
  number_sum.append(sum(numbers[i:i+K]))
    
answer = (max(number_sum) + K) / 2
print(answer)


### FIXED CODE ###

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

mx = sum(p[:K])
cur = mx
for i in range(N-K):
  cur = cur-p[i]+p[i+K]
  mx = max(mx, cur)
  
ans = (mx+K) / 2
print(ans)
### BUGGY CODE ###

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

for k, val in enumerate(A):
    count = 0
    for i, x in enumerate(A):
        for j, y in enumerate(A):
            if i == k or j == k or i == j:
                continue
            if x == y:
                count += 1
    print(count // 2)

### FIXED CODE ###

from math import factorial

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

def comb(n, r):
    if n - r < 0:
        return 0
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))

nums = [0] * (N + 1)
for i, v in enumerate(A):
    nums[v] += 1
combs = list(map(lambda n: comb(n, 2), nums))
total = sum(combs)

for k, val in enumerate(A):
    print(total - (nums[val] - 1))
### BUGGY CODE ###

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

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
  n,m=map(int,input().split())
  a=tuple(int(input()) for _ in range(m))
  a=set(a)
  mod=10**9+7
  pattern=[0]*(n+1)
  pattern[0]=pattern[1]=1
  if 1 in a:
      pattern[1]=0
  for i in range(2,n+1):
      if i in a:
          pattern[i]=0
      else:
          pattern[i]=(pattern[i-1]+pattern[i-2])%mod
  print(pattern[n])
main()
### BUGGY CODE ###

import collections

n, q = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(n - 1)]
query = [tuple(map(int, input().split())) for _ in range(q)]

tree = [[] for _ in range(n)]
edge.sort()
edge = collections.deque(edge)
flag = [False] * n
flag[0] = True
while len(edge) != 0:
    a, b = edge.popleft()
    if flag[a - 1]:
        tree[a - 1].append(b - 1)
        flag[b - 1] = True
    elif flag[b - 1]:
        tree[b - 1].append(a - 1)
        flag[a - 1] = True
    else:
        edge.append((a, b))

p = [0] * n
for x, y in query:
    p[x - 1] += y
counter = [0] * n

que = collections.deque([0])
while len(que) != 0:
    i = que.popleft()
    counter[i] += p[i]
    for j in tree[i]:
        counter[j] = counter[i]
        que.append(j)

print(' '.join([str(c) for c in counter]))

### FIXED CODE ###

import collections

n, q = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(n - 1)]
counter = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x

tree = [[] for _ in range(n)]
edge = collections.deque(edge)
while len(edge) != 0:
    a, b = edge.popleft()
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

que = collections.deque([0])
flag = [False] * n
while len(que) != 0:
    i = que.popleft()
    flag[i] = True
    for j in tree[i]:
        if flag[j]: continue
        counter[j] += counter[i]
        que.append(j)

print(' '.join([str(c) for c in counter]))
### BUGGY CODE ###

N=int(input())

answer=0

if N%2==0:
    for i in range(N//2):
        answer+=N-1
else:
    for i in range(N//2):
        answer+=N-1
    answer+=(N-1)//2
print(answer)

### FIXED CODE ###

N=int(input())

answer=0

answer+=(N**2-N)//2

print(answer)
### BUGGY CODE ###

import sys
import random
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

import math
A, B, N = MII_split()

def f(x):
    """最小値を求めたい関数"""
    return math.floor(A * x / B) - A * math.floor(x / B)

def numerical_diff(f, x):
    """中央差分を元に数値微分する関数"""
    h = 1e-4
    return (f(x + h) - f(x - h)) / (2 * h)

def gradient_descent(f, initial, learning_rate=1, steps=10**5):
    """一階導関数から勾配法で最小値を求める関数"""
    # 現在地を示すカーソル
    x = initial

    # 所定の回数を繰り返す
    for _ in range(steps):
        # 現在地の勾配 (どちらにどれだけ進むべきか) を得る
        grad = numerical_diff(f, x)
        # 勾配を元にして現在地を移動する
        x -= learning_rate * grad

    # 最終的な位置を返す
    return f(x)

ma = 0
for _ in range(100):
    ini = random.randrange(N + 1)
    tmp = gradient_descent(f, ini)
    # tmp = f(ini)
    if ma < tmp:
        ma = tmp


print(ma)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

import math

A, B, N = MII_split()

def f(x):
    return math.floor(A * x / B) - A * math.floor(x / B)

# max = 0
# for x in range(min(B + 1, N + 1)):
#     if x > N:
#         break
#     fx = f(x)
#     # print(fx)
#     if fx > max:
#         max = fx
print(f(min(B-1, N)))
### BUGGY CODE ###

def gcd(x, y):
    while y!=0:
        x, y = y, x%y
    return x

def process():
    n = int(raw_input().strip())
    if n%2 == 0:
        print str(n)+' '+str(n)+' '+str(n>>1)
        return
    for x in xrange(max(n>>2, 1), 3501):
        for y in xrange(x, 3501):
            b = x*y/gcd(x, y)
            b = b*n/gcd(b, n)
            a = b*4/n
            a -= b/x
            a -= b/y
            r = gcd(a, b)
            a /= r
            b /= r
            if a==1:
                print str(x)+' '+str(y)+' '+str(b)
                return

process()

### FIXED CODE ###

def gcd(x, y):
    while y!=0:
        x, y = y, x%y
    return x

def process():
    n = int(raw_input().strip())
    if n%2 == 0:
        print str(n)+' '+str(n)+' '+str(n>>1)
        return
    for x in xrange(max(n>>1, 1), 3501):
        for y in xrange(x, 3501):
            b = n*x*y
            a = 4*x*y-n*x-n*y
            if a>0 and (b%a)==0:
                print str(x)+' '+str(y)+' '+str(b/a)
                return

process()