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

def main():
    from heapq import heappush, heappop

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

    h = [(int(s[0][0] == '#'), 0, 0)]

    while h:
        bk, r, c = heappop(h)
        if r == H - 1 and c == W - 1:
            print(bk)
            return

        curr = s[r][c]
        if r < H - 1:
            if curr == s[r + 1][c]:
                heappush(h, (bk, r + 1, c))
            elif curr == '.':
                heappush(h, (bk + 1, r + 1, c))
            else:
                heappush(h, (bk, r + 1, c))

        if c < W - 1:
            if curr == s[r][c + 1]:
                heappush(h, (bk, r, c + 1))
            elif curr == '.':
                heappush(h, (bk + 1, r, c + 1))
            else:
                heappush(h, (bk, r, c + 1))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import deque

    WHITE = 0
    BLACK = 1

    CHAR = '.', '#'

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

    h = deque()
    x = CHAR.index(s[0][0])
    h.append((x, 0, 0, x))

    cost = [[H * W] * W for _ in range(H)]
    cost[0][0] = x

    while h:
        cnt, r, c, mode = h.popleft()
        if cnt > cost[r][c]:
            continue
        if r == H - 1 and c == W - 1:
            print(cnt)
            return

        delta = int(mode == WHITE)
        ncnt = cnt + delta

        if r < H - 1:
            if s[r + 1][c] == CHAR[mode]:
                if cnt < cost[r + 1][c]:
                    cost[r + 1][c] = cnt
                    h.appendleft((cnt, r + 1, c, mode))
            else:
                if delta:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.append((ncnt, r + 1, c, 1 - mode))
                else:
                    if ncnt < cost[r + 1][c]:
                        cost[r + 1][c] = ncnt
                        h.appendleft((ncnt, r + 1, c, 1 - mode))

        if c < W - 1:
            if s[r][c + 1] == CHAR[mode]:
                if cnt < cost[r][c + 1]:
                    cost[r][c + 1] = cnt
                    h.appendleft((cnt, r, c + 1, mode))
            else:
                if delta:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.append((ncnt, r, c + 1, 1 - mode))
                else:
                    if ncnt < cost[r][c + 1]:
                        cost[r][c + 1] = ncnt
                        h.appendleft((ncnt, r, c + 1, 1 - mode))


if __name__ == '__main__':
    main()

# import sys
#
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)
# rstrip()
# int(input())
# map(int, input().split())
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    a_s = sorted(a)
    #ans = []
    for i in a_s:
        #ans.append(a.index(i)+1)
        print(a.index(i)+1, end=' ')
    #print(*ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    ans = [None] * n
    for idx, ea in enumerate(a):
        ans[ea-1] = idx+1
    print(*ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import defaultdict


def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

n, m, k = map(int, input().split())
AB = [map(int, input().split()) for _ in range(m)]
CD = [map(int, input().split()) for _ in range(k)]

graph_f = defaultdict(set)
graph_b = defaultdict(set)

for a, b in AB:
    graph_f[a].add(b)
    graph_f[b].add(a)

for c, d in CD:
    graph_b[c].add(d)
    graph_b[d].add(c)

res = [0] * n

for i in range(1, n + 1):
    reachables = dfs(graph_f, i)
    for j in range(1, n + 1):
        if i == j:
            continue
        else:
            if j in reachables and j not in graph_f[i] and j not in graph_b[i]:
                res[i - 1] += 1

print(' '.join(map(str, res)))

### FIXED CODE ###

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 same(self, x, y):
        return self.find(x) == self.find(y)

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


if __name__ == "__main__":
    n, m, k = map(int, input().split())

    u = UnionFind(n)
    f_cnt = [0] * n
    b_cnt = [0] * n

    for _ in range(m):
        a, b = map(int, input().split())
        u.union(a - 1, b - 1)
        f_cnt[a - 1] += 1
        f_cnt[b - 1] += 1

    for _ in range(k):
        c, d = map(int, input().split())
        if u.same(c - 1, d - 1):
            b_cnt[c - 1] += 1
            b_cnt[d - 1] += 1

    print(*[(u.size(i) - f_cnt[i] - b_cnt[i] - 1) for i in range(n)])
### BUGGY CODE ###

n = int(input())
pList = list(map(int,input().split()))

count = 1
for i in range(1,n-1):
  sp = sorted(pList[:i])
  if sp[0] >= pList[i]:
    count += 1

if len(pList) != 1:
    ls = sorted(pList[:-1])
    if ls[0] >= pList[-1]:
      count += 1

print(count)


### FIXED CODE ###

n = int(input())
pList = list(map(int,input().split()))

count = 0
minL = pList[0] 
for i in range(n):
  if minL >= pList[i]:
      count += 1
      minL = pList[i] 
      if minL == 1:
        break

print(count)
### BUGGY CODE ###

import heapq
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

hq = []

for i in range(n):
    a[i] = -a[i]

for i in range(n):
    heapq.heappush(hq,[a[i],i,1])

for i in range(k):
    val,idx,waru = heapq.heappop(hq)
    heapq.heappush(hq, [a[idx]/(waru+1),idx,waru+1])
    #print(hq)
    
val,idx,waru = heapq.heappop(hq)

if val % 1 == 0:
    print(int(val)*(-1))
else:
    print(int(val)*(-1)+1)

### FIXED CODE ###

import heapq
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

low = 0
high = 10**9

if k == 0:
    print(max(a))
    exit()

    
while low+1 < high:
    tmp = 0
    mid = (low + high) //2
    
    for i in range(n):
        tmp += ((a[i]+mid-1) // mid)-1
        
    if tmp <= k:
        high = mid
    else:
        low = mid
        
print(high)
### BUGGY CODE ###

import math

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

### FIXED CODE ###

import math
from itertools import product

K=int(input())
s=0
for a,b,c in product(range(1,K+1), repeat=3):
    	s+=math.gcd(math.gcd(b,c),a)
print(s)
### BUGGY CODE ###

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

p = 1
for i in range(N):
  p = p*A_list[i]
  
if p >1e18:
  print('-1')
else:
  print(p)

### FIXED CODE ###

import sys
N = int(input())
A_list = list(map(int,input().split()))
border = 10**18

if 0 in A_list:
  print(0)
  sys.exit()
else:
  A_list.sort(reverse=True)
  pro = 1
  for i in range(N):
    pro *= A_list[i]
    if pro > 10**18:
      print('-1')
      sys.exit()
    else:
      pass

print(pro)
### BUGGY CODE ###

s = input()
length=len(s)
l = int(len(s)/2)
def erase_01_10(moji):
  moji = moji.replace('01','').replace('0011','').replace('000111','')
  moji = moji.replace('10','').replace('1100','').replace('111000','')
  return moji
for i in range(l):
  if s == erase_01_10(s):
    break
  s = erase_01_10(s)
print(length-len(s))


### FIXED CODE ###

s = input()
length=len(s)
#print(s.count('0'))
#print(s.count('1'))
m=min(s.count('0'),s.count('1'))
print(2*m)
### BUGGY CODE ###

N, T = map(int, input().split())
towns = list(map(int, input().split()))

max_income = 0
ans = 0
for i in range(N-1):
    buy = towns[i]
    sell = max(towns[i+1:])
    earn = sell-buy
    if max_income == earn:
        ans += 1
    elif max_income < earn:
        max_income = earn
        ans = 1

print(ans)


### FIXED CODE ###

N, T = map(int, input().split())
towns = list(map(int, input().split()))

p = towns[-1]
r = []

for i in reversed(range(N)):
    if towns[i] >= p:
        p = towns[i]
    else:
        r.append(p-towns[i])

res = r.count(max(r))
print(res)
### BUGGY CODE ###

# https://beta.atcoder.jp/contests/agc014/submissions/1268295
dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)


def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]
    visited = [[False for _ in range(W)] for _ in range(H)]

    sy, sx = -1, -1
    for r in range(H):
        s = input()
        for c, x in enumerate(s):
            if x == '.':
                a[r][c] = True
            elif x == 'S':
                a[r][c] = True
                sy, sx = r, c

    # print(sy, sx)
    q = [(sy, sx, 0)]
    t = max(H, W)
    n = 1
    i = 0
    while i < n:
        r, c, k = q[i]
        visited[r][c] = True

        t = min(t, r, H - 1 - r, c, W - 1 - c)
        # print(t)
        if t == 0:
            print(1)
            return

        for d_i in range(4):
            nr, nc = r + dr[d_i], c + dc[d_i]
            if 0 <= nr < H and 0 <= nc < W and a[nr][nc] and not visited[nr][nc] and k + 1 <= K:
                q.append((nr, nc, k + 1))
                n += 1
        i += 1

    ans = 1 + (t + K - 1) // K

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# https://beta.atcoder.jp/contests/agc014/submissions/1268295
from collections import deque

dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)


def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]

    sy, sx = -1, -1
    for r in range(H):
        s = input()
        for c, x in enumerate(s):
            if x == '.':
                a[r][c] = True
            elif x == 'S':
                a[r][c] = True
                sy, sx = r, c

    visited = [[False for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = True

    t = max(H, W)
    q = deque([(sy, sx, 0)])
    while q:
        r, c, k = q.popleft()

        t = min(t, r, H - 1 - r, c, W - 1 - c)
        # print(t)
        if t == 0:
            print(1)
            return

        for d_i in range(4):
            nr, nc = r + dr[d_i], c + dc[d_i]
            if 0 <= nr < H and 0 <= nc < W and a[nr][nc] and not visited[nr][nc] and k + 1 <= K:
                visited[nr][nc] = True
                q.append((nr, nc, k + 1))

    ans = 1 + (t + K - 1) // K

    print(ans)


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

# ABC163 C

def main():
    n = int(input())
    A = list(map(int, input().split()))

    for i in range(n):
        print(A.count(i+1))

if __name__ == '__main__':
    main()

### FIXED CODE ###

# ABC163 C

def main():
    n = int(input())
    A = list(map(int, input().split()))

    res = [0] * n

    for i in A:
        res[i-1] += 1
    
    for num in res:
        print(num)

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

"""問題文
トキはモンスターと戦っています。
モンスターの体力は  H  です。
トキは  N  種類の魔法が使え、 i  番目の魔法を使うと、モンスターの体力を  A i  減らすことができますが、トキの魔力を  B i  消耗します。
同じ魔法は何度でも使うことができます。魔法以外の方法でモンスターの体力を減らすことはできません。
モンスターの体力を  0  以下にすればトキの勝ちです。  トキがモンスターに勝つまでに消耗する魔力の合計の最小値を求めてください。
"""
from functools import lru_cache
import sys


# @lru_cache(maxsize=1000)
# def attack(h, mp):
#     """
#     毎回Nパターン選択肢がある
#     最小値を返す
#     """
#     min_mp = 999999
#     for a, b in sorted_ab_list:
#         new_h = h - a
#         new_mp = mp + b
#
#         if new_mp >= min_mp:
#             # 既に最小値超えてたら中断
#             continue
#
#         if new_h > 0:
#             min_mp = min(min_mp, attack(new_h, new_mp))
#         else:
#             min_mp = min(min_mp, new_mp)
#
#     # 最小値をとる
#     return min_mp


def use_dp():
    max_a = max([ab[0] for ab in AB])
    dp = [sys.maxsize for i in range(H+1)]
    dp[0] = 0

    # 各ダメージ段階の最小値を求める
    for i in range(H):
        if dp[i] == sys.maxsize:
            continue
        # 各魔法を使って最小値なら更新
        for j in range(N):
            a = min(i + AB[j][0], H)
            b = dp[i] + AB[j][1]
            if dp[a] > b:
                dp[a] = b

    min_mp = dp[H]

    # H < i < H+max(Ai)の範囲で最小値を求める
    # min_mp = sys.maxsize
    # for i in range(H, H+max_a):
    #     min_mp = min(dp[i], min_mp)

    print(min_mp)


if __name__ == '__main__':
    H, N = list(map(int, input().split()))
    AB = []
    for n in range(N):
        AB.append(list(map(int, input().split())))

    use_dp()

    # sorted_ab_list = sorted(AB_list, key=lambda x: x[0]/x[1], reverse=True)
    #
    # print(attack2(H))


### FIXED CODE ###

import sys

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

dp = [sys.maxsize for i in range(H+1)]
dp[0] = 0

# 各ダメージ段階の最小値を求める
for i in range(H):
    if dp[i] == sys.maxsize:
        continue
    # 各魔法を使って最小値なら更新
    for j in range(N):
        a = min(i + AB[j][0], H)
        b = dp[i] + AB[j][1]
        if dp[a] > b:
            dp[a] = b

print(dp[H])
### BUGGY CODE ###

def main():
  n=int(input())
  s=input()
  dp=[[0]*(n+1) for i in range(n+1)]
  for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
      if s[i]==s[j]:
        dp[i][j]+=dp[i+1][j+1]+1
  #print(dp)
  
  ans=0
  for i in range(n):
    for j in range(n):
      if i<j:
        t=min(j-1,dp[i][j])
        ans=max(ans,t)
  print(ans)      
        

if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  n=int(input())
  s=input()
  dp=[[0]*(n+1) for i in range(n+1)]
  for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
      if s[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
  #for i in dp:
  #  print(i)
  
  ans=0
  for i in range(n-1):
    for j in range(i+1,n):
      ans=max(ans,min(j-i,dp[i][j]))
  print(ans)      
        

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

import heapq
n,q=map(int,input().split())

event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append([s-x,1,x])
    event.append([t-x,-1,x])
event.sort()
d=[int(input()) for _ in range(q)]

k=0
stop=set()
hq=[]
for i in range(q):
    while k<2*n and event[k][0]<=d[i]:
        x=event[k][2]
        if event[k][1]==1:
            heapq.heappush(hq,x)
            stop.add(x)
        else:
            stop.remove(x)
        k+=1
    while hq and hq[0] not in stop:
        heapq.heappop(hq) 
    print(hq[0] if hq!=[] else -1)


### FIXED CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)

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

    event=[]
    for _ in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,1,x))
        event.append((t-x,-1,x))

    for i in range(q):
        event.append((int(input()),2,i))
    event.sort()

    ans=[0]*q

    stop=set()
    hq=[]
    for t,op,x in event:
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)

        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

main()
### BUGGY CODE ###

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

fact = [1] + [0] * N
for i,ai in enumerate(A, 1):
  fact[i] = fact[i-1] * ai

for i in range(1, N - K + 1):
  score_2 = fact[K + i] // fact[i]
  score_1 = fact[K + i - 1] // fact[i - 1]
  print('Yes' if score_1 < score_2 else 'No')

### FIXED CODE ###

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

for i in range(N - K):
  score_2 = A[i+K]
  score_1 = A[i]
  print('Yes' if score_1 < score_2 else 'No')
### BUGGY CODE ###

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

old = 0

for i in range(k,n+1):
  new=1
  for j in range(i-k,i):
    new*=a[j]
  if i != k:
    if new > old:
      print("Yes")
    else:
      print("No")
  old = new

### FIXED CODE ###

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

old = 0

for i in range(k,n+1):
  if i == k:
    new = 1
  elif i != k:
    new = a[i-1] / a[i-k-1]
    if new > 1:
      print("Yes")
    else:
      print("No")
  old = new
### BUGGY CODE ###

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

count = 0

x = 0
while (x <= K):
    y = 0
    while (y <= K):
        z = S - (x + y)
        if z <= K and 0 <= z:
            #print(x, y, z)
            count += 1
        y += 1
    x += 1



print(count)

### FIXED CODE ###

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

count = 0

x = 0
while (x <= K):
    y = 0
    while (y <= K):
        if 0 <= S - (x + y) <= K:
            count += 1
        y += 1
    x += 1



print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
V = [[] for _ in range(N)]
X = [0 for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    V[a].append(b)
    V[b].append(a)

for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x
# p親、n現在、s合計
def dfs(p, n):
    for i in V[n]:
        if i == p:
            continue
        else:
            X[i] += X[n] 
            dfs(n, i)
dfs(-1,0)
print(*X)
        

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
 
n , q = map(int,input().split())
point = [0] * n
edge = [[] for i in range(n)]
 
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
 
for _ in range(q):
    a , b = map(int,input().split())
    point[a-1] += b
 
def dfs(now, last=-1):
    for nxt in edge[now]:
        if nxt==last: continue
        point[nxt] += point[now]
        dfs(nxt, now)
dfs(0)
print(*point)
### BUGGY CODE ###

k,s=map(int,input().split())

count=0
for i in range(k+1):
  for j in range(k+1):
    for k in range(k+1):
      if i+j+k==s:
        count+=1
print(count)


### FIXED CODE ###

k,s=map(int,input().split())

count=0
for i in range(k+1):
  for j in range(k+1):
    if 0<=s-i-j<=k:
      count+=1
      
print(count)
### BUGGY CODE ###

import heapq

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

heapq.heapify(A)
#print(A)

for i in range(M):
    A[0] = -(-A[0] // 2)
    heapq.heapify(A)

ans = - sum(A)
print(ans)





### FIXED CODE ###

import heapq

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

heapq.heapify(A)
#print(A)

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

ans = - sum(A)
print(ans)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
from collections import *

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
es = defaultdict(set)
h = defaultdict(int)
for i, a in enumerate(A):
    for j, k in zip(a, a[1:]):
        a, b = (i, j) if i < j else (j, i)
        c, d = (i, k) if i < k else (k, i)
        if not (c, d) in es[(a, b)]:
            es[(a, b)].add((c, d))
            h[(c, d)] += 1
dq = deque()
for i in range(N-1):
    for j in range(i+1, N):
        if h[(i, j)] == 0:
            dq.append(((i, j), 1))
cnt, day = 0, defaultdict(int)
while len(dq) > 0:
    cnt += 1
    p, d = dq.popleft()
    for q in es[p]:
        h[q] -= 1
        if h[q] == 0:
            dq.append((q, d+1))
            day[q] = max(day[q], d+1)
ans = max(day.values()) if cnt == N*(N-1)//2 else -1
print(ans)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
import time

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
P = [0] * N
cnt = 0
ALL = N*(N-1)//2
s = time.time()
for day in range(ALL):
    if time.time()-s > 1.6:
        print(N*(N-1)//2)
        break
    used = [0] * N
    flag = 0
    for i, p in enumerate(P):
        if p != N-1 and used[i] == 0:
            x = A[i][p]
            if x < N and used[x] == 0 and A[x][P[x]] == i:
                P[i] += 1
                P[x] += 1
                used[i] = 1
                used[x] = 1
                flag = 1
                cnt += 1
    if cnt == ALL:
        print(day+1)
        break
    if flag == 0:
        print(-1)
        break
### BUGGY CODE ###

S,C=map(int,input().split())
#start=time.time()
scc=0
count=0

while (S>0 or C>=4): #and count<max(S,C*44301):
    if S>0 and C>=2:
        S-=1
        C-=2
        scc+=1
        
        count+=1
        #print(count)
        
    elif S<=0 and C>=4:
        C-=4
        scc+=1
        
        count+=1
        #print(count)
    else:
        count+=1
        #print(count)
    
print(scc)

### FIXED CODE ###

S,C=map(int,input().split())
scc=0

if 2*S<=C:
    scc+=S
    C-=S*2
    scc+=C//4
else:
    scc=C//2
    
print(scc)
### BUGGY CODE ###

N,M = map(int,input().split())
flag = 0
lis  = [list(map(int,input().split())) for _ in range(M)]
ans_pra_lis = []
ans_beh_lis = [0] * M
lis_sort = sorted(lis)
for _ in lis:
    s = str(_[0])
    ans_pra_lis.append(s)
i = 1
for _ in range(len(lis_sort)):
    if flag != lis_sort[_][0]:
        flag = lis_sort[_][0]
        i = 1
    ans_beh_lis[lis.index(lis_sort[_])] = str(i)
    i += 1
for x,y in zip(ans_pra_lis,ans_beh_lis):
    print('0'*(6-len(x)),x,'0'*(6-len(y)),y,sep='')



### FIXED CODE ###

N,M = map(int,input().split())
lis  = [list(map(int,input().split())) for _ in range(M)]
ans_lis = [0] * M
lis_sort = sorted(lis,key =lambda x:(x[0],x[1]))
flag = lis_sort[0][0]
i = 1
for x in lis_sort:
    if x[0] != flag:
        flag = x[0]
        i=1
    x[1] = '0'*(6-len(str(i)))+str(i)
    i+=1
for x in lis:
    print('0'*(6-len(str(x[0]))),str(x[0]),x[1],sep='')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])

x, h = xh[0]
cnt = -(-h//a)
ans = cnt
bomb_list = [(x+2*d, cnt*a)]
effective_bomb_idx = 0
for x, h in xh[1:]:
    for bomb in bomb_list[effective_bomb_idx:]:
        area, damage = bomb
        if x <= area:
            h -= damage
        else:
            effective_bomb_idx += 1

    if 0 < h:
        cnt = -(-h//a)
        bomb_list.append((x+2*d, cnt*a))
        ans += cnt

print(ans)


### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])
x_list = [x for x, h in xh]

damage = [0]*(n+1)
ans = 0
for i in range(n):
    x, h = xh[i]
    h -= damage[i]
    if h <= 0:
        damage[i+1] += damage[i]
        continue
    cnt = -(-h//a)
    ans += cnt
    damage[i] += cnt*a
    end_idx = bisect.bisect_right(x_list, x+2*d)
    damage[end_idx] -= cnt*a
    damage[i+1] += damage[i]

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

n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
x=[i for i,_ in z]
y=[j for _,j in z]
x.sort()
y.sort()
a=10**20
for i,l in enumerate(x):
    for r in x[i+1:]:
        for v,d in enumerate(y):
            for u in y[v+1:]:
                if sum([1for i,j in z if l<=i<=r and d<=j<=u])>=k:
                    a=min(a,(r-l)*(u-d))
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
z.sort()
a=10**20
for i in range(n):
    for j in range(i+1,n):
        x=z[j][0]-z[i][0]
        l=sorted(t[1]for t in z[i:j+1])
        for u,v in zip(l,l[k-1:]):
            a=min(a,x*(v-u))
print(a)