Harryxun/stf_run huggingface dataset:
# グラフ定義
class Edge:
    def __init__(self, f: int, t: int, cost: int):
        self._t = t
        self._cost = cost
        self._f = f

    @property
    def t(self):
        return self._t

    @property
    def f(self):
        return self._f

    @property
    def cost(self):
        return self._cost


INF = 1 << 28


# ここから本実装
def bellman_ford(n: int, edges, s: int):
    dist = [INF for _ in range(n)]
    dist[s] = 0

    for i in range(n):
        for e in edges:

            if dist[e.t] > dist[e.f] + e.cost:
                dist[e.t] = dist[e.f] + e.cost
                if i == n - 1:
                    return None

    return dist


def visitable_node(n, g, rg):

    vis = [False] * n

    def dfs(idx):
        vis[idx] = True
        for e in g[idx]:
            if not vis[e]:
                dfs(e)

    dfs(0)

    rvis = [False] * n

    def rdfs(idx):
        rvis[idx] = True
        for e in rg[idx]:
            if not rvis[e]:
                rdfs(e)

    rdfs(n - 1)

    return [vis[i] & rvis[i] for i in range(n)]


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

edges = []
g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges.append(Edge(a, b, -c + p))
    g[a].append(b)
    rg[b].append(a)

visitable = visitable_node(n, g, rg)
updated = [e for e in edges if visitable[e.f] and visitable[e.t]]

dist = bellman_ford(n, edges, 0)

if dist:
    print(max(0, -dist[n - 1]))
else:
    print(-1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)



# グラフ定義
class Edge:
    def __init__(self, f: int, t: int, cost: int):
        self._t = t
        self._cost = cost
        self._f = f

    @property
    def t(self):
        return self._t

    @property
    def f(self):
        return self._f

    @property
    def cost(self):
        return self._cost


INF = 1 << 28


# ここから本実装
def bellman_ford(n: int, edges, s: int):
    dist = [INF for _ in range(n)]
    dist[s] = 0

    for i in range(2 * n):
        for e in edges:

            if dist[e.t] > dist[e.f] + e.cost:
                dist[e.t] = dist[e.f] + e.cost
                if i >= n - 1:
                    return None

    return dist


def visitable_node(n, g, rg):

    vis = [False] * n

    def dfs(idx):
        vis[idx] = True
        for e in g[idx]:
            if not vis[e]:
                dfs(e)

    dfs(0)

    rvis = [False] * n

    def rdfs(idx):
        rvis[idx] = True
        for e in rg[idx]:
            if not rvis[e]:
                rdfs(e)

    rdfs(n - 1)

    return [vis[i] & rvis[i] for i in range(n)]


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

edges = []
g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges.append(Edge(a, b, -c + p))
    g[a].append(b)
    rg[b].append(a)

visitable = visitable_node(n, g, rg)
updated = [e for e in edges if visitable[e.f] and visitable[e.t]]

dist = bellman_ford(n, updated, 0)

if dist:
    print(max(0, -dist[n - 1]))
else:
    print(-1)
def maximal():
    query = input().split()
    B = query[1]
    B = B.split()
    B = [int(i) for i in B]
    # length of values is N
    # any number more or equals than 0
    result = []

    result.append(B[0])

    for i in range(0, len(B) - 1):
        # if value is same put in first one
        compared = B[i]
        if B[i + 1] <= compared:
            result.append(B[i + 1])
        else:
            result.append(B[i])

    result.append(B[len(B) - 1])
    return sum(result)


print(maximal())

### FIXED CODE ###

def maximal():
    N = int(input())
    B = input()
    B = B.split()
    B = [int(i) for i in B]
    # length of values is N
    # any number more or equals than 0
    result = []
 
    result.append(B[0])
 
    for i in range(0, len(B) - 1):
        # if value is same put in first one
        compared = B[i]
        if B[i + 1] <= compared:
            result.append(B[i + 1])
        else:
            result.append(B[i])
 
    result.append(B[len(B) - 1])
    return sum(result)
 
 
print(maximal())
s = list(input())
t = list(input())

flag = True
s_len = len(s)
t_len = len(t)
save = 0
count = 0

for i in range(s_len):
    if s[i] == '?':
        s[i] = 'a'
        count += 1
        if count == t_len and flag:
            save = i - count + 1
            flag = False
    elif s[i] == t[count]:
        count += 1
        if count == t_len and flag:
            save = i - count + 1
            flag = False
    else:
        count = 0
        
for j in range(t_len):
    s[j+save] = t[j]

if flag:
    print("UNRESTORABLE")
else:
    print(s)

### FIXED CODE ###

s = list(input())
t = list(input())

ls = len(s)
lt = len(t)
match = -1

for i in range(ls-lt+1):
    for j in range(lt):
        if s[i+j] == t[j] or s[i+j] == '?':
            pass
            #continueはここで処理が終わってしまう
        else:
            break
            
        if j == lt - 1:
            match = i
        
for i in range(ls):
    if s[i] == '?':
        s[i] = 'a'
        
for i in range(lt):
    s[match+i] = t[i]
        
if match < 0:
    print("UNRESTORABLE")
else:
    print(''.join(s))
import math
a,b=map(int,input().split())
print((a*b)//math.gcd(a,b))

### FIXED CODE ###

import fractions
a,b=map(int,input().split())
print(a*b//fractions.gcd(a,b))
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;

int main(){
    char a, b;
    cin >> a >> b;
    bool flag = false;
    if (a == 'H' && b == 'H'){
        flag = true;
    }
    if (a == 'D' && b == 'D'){
        flag = true;
    }
    if (flag){
        cout << 'H' << endl;
    }else{
        cout << 'D' << endl;
    }
    
}

### FIXED CODE ###

# A問題
a, b = map(str, input().split())
if a == "H":
    if b == "H":
        print("H")
    else:
        print("D")
else:
    if b == "H":
        print("D")
    else:
        print("H")
#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>string to_string(pair<A, B> p);

template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {return '"' + s + '"';}

string to_string(const char* s) {return to_string((string) s);}

string to_string(bool b) {return (b ? "true" : "false");}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p) {return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";}

template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p) {return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

void test_case(vector <long> v, int n){
	sort(v.begin(),v.end());
	long ans = 0;	
	for (int i = 0; i < n - 2; i++){
		for (int j = i + 1; j < n - 1; j++){
			for (int k = j + 1; k < n; k++){
				if (v[i] != v[j] && v[j] != v[k] && v[i] != v[k] && (v[k] < v[j] + v[i] || v[i] < v[j] + v[k] || v[j] < v[k] + v[i])){
					++ans;
				}
			}                                     
		}
	}
	cout << ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector <long> v(n);
	for (auto &x : v){
		cin >> x;
	}
	test_case(v,n);	
    return 0;
}





### FIXED CODE ###

n = int(input())
l = list(map(int,input().split(' ')))

l = sorted(l)

ans = 0
for i in range (0,n-2):
	for j in range (i + 1,n-1):
		for k in range (j + 1,n):
			if l[i] != l[j] and l[j] != l[k] and l[i] != l[k] and l[i] + l[j] > l[k]:
				ans += 1

print(ans)
a=int(input())
b=int(input())
print(max(a+b,max(a-b,a*b)))

### FIXED CODE ###

a,b=map(int,input().split())
print(max(a+b,a-b,a*b))
A,B,M=map(int,input().split())
a=list(map(int,input().split())
b=list(map(int,input().split())
min_price=min(a)+min(b)
for i in range(M):
    m=list(map(int,input().split())
    tmp_price=a[m[0]]+b[m[1]]-m[2]
    if min_price>tmp_price:
        min_price=tmp_price
print(min_price)

### FIXED CODE ###

A,B,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
min_price=min(a)+min(b)
for i in range(M):
    tmp_price=10000
    m=list(map(int,input().split()))
    tmp_price=a[m[0]-1]+b[m[1]-1]-m[2]
    if min_price>tmp_price:
        min_price=tmp_price
print(min_price)
from itertools import groupby

n = int(input())

words = []

for i in range(n):
    words.append(input())

words.sort()

count_w = {}

for key, value in groupby(words):
    count_w[key] = len(list(value))

for i in list(count_w.keys):
    if count_w[i] == max(list(count_w.values)):
        print(i)

### FIXED CODE ###

n = int(input())

words = [input() for _ in range(n)]

d = {}

for i in range(n):
    if words[i] not in d:
        d[words[i]] = 1
    else:
        d[words[i]] += 1

m = max(d.values())
ANS = []

for keys in d.keys():
    if d[keys] == m:
        ANS.append(keys)

ANS = sorted(ANS)

for i in ANS:
    print(i)
a = int(input())
res = sum(a +(a**2)+(a**3))
print(res)

### FIXED CODE ###

a = int(input())
print(a +a**2+a**3)
n = int(input())
dp = [float("Inf")]*(n+1)
for i in range(6):
    dp[i] = i
for i in range(n+1):
    power = 1
    while i >= 6 ** power:
        dp[i] = min(dp[i],dp[i-6**power]+1)
        power += 1
    power = 1
    while i >= 9 ** power:
        dp[i] = min(dp[i],dp[i-9**power]+1)
        power += 1
print(dp[n])

### FIXED CODE ###

n = int(input())
dp = [i for i in range(n+1)]
for i in range(n+1):
    power = 1
    while 6**power <= i:
        dp[i] = min(1+dp[i-6**power],dp[i])
        power += 1
    power = 1
    while 9**power <= i:
        dp[i] = min(1+dp[i-9**power],dp[i])
        power += 1
print(dp[n])
N=int(input())
B=["*"]+list(map(int,input().split()))

X=[]
for t in range(N):
    p=-1
    for k in range(1,(N-t)+1):
        if B[k]==k:
            p=k

    if p>=1:
        X.append(p)
        del B[p]
    else:
        print(-1)
        sys.exit()

print("\n".join(map(str,X[::-1])))


### FIXED CODE ###

N=int(input())
B=["*"]+list(map(int,input().split()))

X=[]
for t in range(N):
    p=-1
    for k in range(1,(N-t)+1):
        if B[k]==k:
            p=k

    if p>=1:
        X.append(p)
        del B[p]
    else:
        print(-1)
        exit()

print("\n".join(map(str,X[::-1])))
N = int(input())
A = map(int, input().split())

sortA = sorted(A)

min_val = sortA[0]
min_count = 1
for i in range(1, N):
    if sortA[i] == min_val:
        min_count += 1
    break

mins = sortA[:min_count]
larges = sortA[min_count:]

result = sum(larges[1:])

if len(mins) < len(larges):
    result += sum(larges[len(larges)-len(mins)-1:-1])
elif len(mins) == len(larges):
    result += sum(larges[len(larges)-len(mins)-1:-1])
    result += larges[0]
else:
    result += sum(larges[len(larges)-len(mins)-1:-1])
    result += larges[0]
    rem_mins_count = len(mins) - len(larges)
    result += rem_mins_count * min_val

print(result)



### FIXED CODE ###

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

sortA = sorted(A)

result = 0
for i in range(1, N):
    result += sortA[N - (i // 2) - 1]

print(result)
N,M = map(int,input().split())
AC = 0
WA = 0
lis_ac = []
dic_wa ={}
if M == 0:
  print(0,0)
else:
  A = [list(input().split()) for i in range(M)]
  for i in range(M):
    if A[i][0] not in lis_ac:
      if A[i][1] == 'AC':
        lis_ac.append(A[i][0])
        WA += dic_wa[A[i][0]]
      elif A[i][0] in dic_wa.keys():
        dic_wa[A[i][0]] += 1
      else:
        dic_wa[A[i][0]] = 1
  print(len(lis_ac), WA)


### FIXED CODE ###

N,M = map(int,input().split())
AC = 0
WA = 0
lis = [0] * N
for i in range(M):
  a,b = input().split()
  if lis[int(a)-1] < 0:
    pass
  elif b == 'AC':
    WA += lis[int(a)-1]
    AC += 1
    lis[int(a)-1] = -1
  else:
    lis[int(a)-1] += 1
print(AC, WA)
a = int(input())
b = int(input())
print(str(a * b))


### FIXED CODE ###

a, b = map(int, input().split())
print(a*b)
x=2
print(X**3)

### FIXED CODE ###

x = int(input())
print(x**3)
N, M = map(int, input().split())
class uft:
  def __init__(self, N):
    self.__N = N
    self.__arr = [-1] * (N + 1)
  def fp(self, x):
    if self.__arr[x] < 0:
      return x
    else:
      self.__arr[x] = self.fp(self.__arr[x])
      return self.__arr[x]
  def add(self, x, y):
    if x > y:
      x, y = y, x
    px = self.fp(x)
    py = self.fp(y)
    self.__arr[px] += self.__arr[py]
    self.__arr[py] = px
  def groups(self):
    ret = -1
    for i in self.__arr:
      if i < 0:
        ret += 1
    return ret
UFT = uft(N)

for i in range(M):
  A, B = map(int, input().split())
  UFT.add(A,B)
print(UFT.groups() -1)



### FIXED CODE ###

import sys
sys.setrecursionlimit(int(1e9))

class uft:
  def __init__(self, N):
    self.__N = N
    self.__arr = [-1] * (N + 1)
  def fp(self, x):
    if self.__arr[x] < 0:
      return x
    else:
      self.__arr[x] = self.fp(self.__arr[x])
      return self.__arr[x]
  def add(self, x, y):
    px = self.fp(x)
    py = self.fp(y)
    if px > py:
      px, py = py, px
    if px == py:
      return 1
    self.__arr[px] += self.__arr[py]
    self.__arr[py] = px
  def groups(self):
    ret = -1
    for i in self.__arr:
      if i < 0:
        ret += 1
    return ret
  def show_arr(self):
    print(self.__arr)
  
N, M = map(int, input().split()) 
UFT = uft(N)

for i in range(M):
  A, B = map(int, input().split())
  UFT.add(A,B)
print(UFT.groups() -1)
N = int(input())
ans = 0

#Pythonのfor文range()の右側<最大値>は書いている値から-1されるものなので、注意する。(+1する)

for i in range(1, N + 1):
    if len(str(i)) % 2 == 1:
    ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
ans = 0

#Pythonのfor文range()の右側<最大値>は書いている値から-1されるものなので、注意する。(+1する)

for i in range(1, N + 1):

    if len(str(i)) % 2 == 1:
        ans += 1

print(ans)
import bisect
n=int(input())
a=[int(input()) for i in range(n)]
inf=10**6
tmp=[inf]*(n+1)
ans=0
for i in range(n-1,-1,-1):
  j= bisect.bisect_right(tmp,a[i])
  tmp[j]=a[i]
for i in range(n):
  if tmp[i]!=inf:
    ans+=1
print(ans)



### FIXED CODE ###

import bisect
n=int(input())
a=[int(input()) for i in range(n)]
inf=10**9+1
tmp=[inf]*n
ans=0
for i in range(n-1,-1,-1):
  j= bisect.bisect_right(tmp,a[i])
  tmp[j]=a[i]
for i in range(n):
  if tmp[i]!=inf:
    ans+=1
print(ans)
import sys
s = sys.stdin.readlines()
N, K = map(int, s[0].split())
A = list(map(int, s[1].split()))
 
b = [1]
i = 0
while True:
    if A[i] in b:
#        print("m: "+str(b.index(A[i])))
#        print("n: "+str(len(b)-A[i]))
        m = b.index(A[i])
        n = len(b)-b.index(A[i])
        K = (K-m)%n + m
        break
    b.append(A[i])
    i = A[i] - 1
    
tmp = 0
for i in range(K):
    next_town = A[tmp]
    tmp = next_town - 1
print(next_town)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int,input().split()))
b = [0]*N
next_town = 1
for i in range(N+1):
    if b[next_town-1] != 0:
        start = next_town
        cycle = i - b[next_town-1]
#        print("start: "+str(start))
#        print("cycle: "+str(cycle))
        break
    b[next_town-1] = i
    next_town = A[next_town-1]
    
next_town = 1
if b[start-1] >= K:
    for i in range(K):
        next_town = A[next_town-1]
    print(next_town)
else:
    next_town = start
    for i in range((K-b[start-1])%cycle):
        next_town = A[next_town-1]
    print(next_town)
def main():
    n, m, x = map(int, input().split(" "))
    ca =[]
    for i in range(n):
        ca.append(list(map(int, input().split(" "))))
    min_c = 1e6
    for i in range(1<<n):
        a = [0]*(m-1)
        c = 0
        for j in range(n):
            if i >> j & 1 ==1:
                for k in range(1,m):
                    a[k-1] += ca[j][k]
                c += ca[j][0]
        if min(a) >= x and c <min_c:
            min_c = c
    if min_c == 1e6: print(-1)
    else:print(min_c)


if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    n, m, x = map(int, input().split(" "))
    ca =[]
    a = []
    c = []
    ans = 1e9
    for i in range(n):
        ca.append(list(map(int, input().split(" "))))
    for i in range(n):
        c.append(ca[i][0])
        a.append(ca[i][1:])
    for i in range(1<<n):
        a_sum = [0]*m
        c_sum = 0
        for j in range(n):
            if i >> j & 1 == 1:
                for k in range(m):
                    a_sum[k] += a[j][k]
                c_sum += c[j]
        if min(a_sum) >= x and c_sum < ans:
            ans = c_sum
    if ans == 1e9:
        print(-1)
    else:
        print(ans)
        

if __name__ == "__main__":
    main()
#from collections import defaultdict
n = int(input())
di = [list(map(int, input().split(' '))) for _ in range(n)]
#result = {0:0}
md = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        else:
            p = di[i][0] - di[j][0]
            q = di[i][1] - di[j][1]
            #result[(p,q)] = result.get((p,q), 0)+1
            md[(p,q)] += 1
#print(result)
#print(n - max(result.values()))
#print(md)
print(n - max(md.values()))

### FIXED CODE ###

#from collections import defaultdict
n = int(input())
di = [list(map(int, input().split(' '))) for _ in range(n)]
result = {0:0}
#md = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        else:
            p = di[i][0] - di[j][0]
            q = di[i][1] - di[j][1]
            result[(p,q)] = result.get((p,q), 0)+1
            #md[(p,q)] += 1
#print(result)
print(n - max(result.values()))
#print(md)
#print(n - max(md.values()))
while True:
    text = input()
    if text == '-':
        break

    count = int(input())
    for c in range(count):
        index = int(input())
        text - text[index:] + text[:index]

print(text)

### FIXED CODE ###

while True:
    text = input()
    if text == '-':
        break

    count = int(input())
    for c in range(count):
        index = int(input())
        text = text[index:] + text[:index]

    print(text)
n = int(input())
x = list(map(int, input().split()))
y = list(x)
y.sort()
if n % 2 != 0:
    a,b,c = y[n//2-1],y[n//2],y[n//2+1]
    m = b
else:
    a,b = y[n//2-1],y[n//2]    
    m = (a+b)/2
for i in range(n):
    if x[i] < m :
        if n%2==0:
            tm = b
        else:
            tm = (b+c)/2
    if i == n//2:
        if n%2==0:
            tm = a
        else:
            tm = (a+c)/2
    if x[i] > m:
        if n%2==0:
            tm = a
        else:
            tm = (a+b)/2
    print(tm)

        
    

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
y = list(x)
y.sort()
if n % 2 != 0:
    a,b,c = y[n//2-1],y[n//2],y[n//2+1]
    m = b
else:
    a,b = y[n//2-1],y[n//2]    
    m = (a+b)/2
for i in range(n):
    if i == n//2:
        if n%2==0:
            tm = a
        else:
            tm = (a+c)/2
    if x[i] < m :
        if n%2==0:
            tm = b
        else:
            tm = (b+c)/2
    else:
        if n%2==0:
            tm = a
        else:
            tm = (a+b)/2
    print(int(tm))
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
  
def gcd_list(y):
    if len(y)==1:
        return y[0]
    if len(y)==2:
        return gcd(y[0],y[1])
    else:
        return gcd(y[0],gcd_list(y[1:]))

N,X= map(int,raw_input().split())

x = map(int,raw_input().split())

for i in range(N):
    x[i]= abs(x[i]-X)

print gcd_list(x)

### FIXED CODE ###

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
  
def gcd_list(y):
    if len(y)==1:
        return y[0]
    if len(y)==2:
        return gcd(y[0],y[1])
    else:
        return gcd(gcd_list(y[:len(y)/2]),gcd_list(y[len(y)/2:]))

N,X= map(int,raw_input().split())

x = map(int,raw_input().split())

for i in range(N):
    x[i]= abs(x[i]-X)

print gcd_list(x)
import time as time

lines =  input().split()
n = int(lines[0])
m = int(lines[1])
#n,m = map(int,input().split())

py = []
od = [[]*1 for i in range(n)]

#print ("create list: " + str(time.time() - s) )

s = time.time()
for i in range(0,m):

    lines =  input().split()
    p = int(lines[0])
    y = int(lines[1])
    py.append([p,y])
       
    odlen = len(od[p-1])
    od[p-1].append(y)
    od[p-1].sort()
    """ if odlen >= 1 :

        low = 0
        high = odlen - 1
        mid = odlen >> 1

        while low <= high:
            mid = (low + high) >> 1
            guess = od[p-1][mid]
            if guess == y:
                break
            if guess > y :
                high = mid - 1
            else:
                low  = mid + 1
        od[p-1].insert(low,y)

    else:
        od[p-1].append(y) """

#print ("sort: " + str(time.time() - s) )
#exit(0)

s = time.time()
for i in range(0,m):
    py0 = py[i][0]
    
    low = 0
    high = odlen - 1
    mid = odlen >> 1
    while low <= high:
        mid = (low + high) >> 1
        guess = od[py0-1][mid]
        if guess == py[i][1]:
           break
        if guess > py[i][1]:
           high = mid - 1
        else:
           low  = mid + 1
    r = low
    #print(r)
    #r = od[py0-1].index(py[i][1])

    tmp = py0
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = tmp // 10
    
    l = 6-digit
    for j in range(l):
        print('0',end="")
    print(py0,end="")

    tmp = r + 1
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = r // 10

    l = 6-digit
    for j in range(l):
        print('0',end="")
    print(r+1)

#print ("index: " + str(time.time() - s) )

### FIXED CODE ###

import sys as sys

lines =  input().split()
n = int(lines[0])
m = int(lines[1])

py = []
od = {}

#lines = sys.stdin.readlines()

for i in range(0,m):


    #l =  lines[i].split()
    l = input().split()
    p = int(l[0])
    y = int(l[1])
    
    if p in od :
        od[p].append([i,y])
    else:
        od[p] = [[i,y]]

a = []
for p in od.keys():
    od[p].sort(key=lambda x:x[1])
    r = 1

    for o in od[p]:
        cs = ""

        tmp = p
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10
        
        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(p)

        tmp = r 
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10

        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(r)        

        a.append([o[0],cs])
        r += 1

a.sort(key=lambda x:x[0])
for aa in a:
    print(aa[1])
a,b,n=map(int,input().split())
score=0
if (n<b):
    print( int(a*n/b))
elif(b＝＝１):
    print(0)
else:
    c = int(n/b)
    score = 0
    for i in range(1,c+1):
        n_ = b*i-1
        t = int(a*n_/b)-a*int(n_/b)
        score = max(score,t)
    t = int(a*n/b)-a*int(n/b)
    score = max(score,t)
    print(score)

### FIXED CODE ###

a,b,n=map(int,input().split())
score=0
if (n<b):
    print( int(a*n/b))
elif(b==1):
    print(0)
else:
    c = int(n/b)
    score = 0
    for i in range(1,c+1):
        n_ = b*i-1
        t = int(a*n_/b)-a*int(n_/b)
        score = max(score,t)
    t = int(a*n/b)-a*int(n/b)
    score = max(score,t)
    print(score)