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

N,D,A=map(int,input().split())
D*=2 # 爆発の長さ
X=[None]*N
for i in range(N):
  X[i]=list(map(int,input().split()))

X=sorted(X,key=lambda x:x[0])
lastX=X[-1][0] # 最後のモンスターの場所
from collections import defaultdict
damage=defaultdict(int)
ans=0
for i in range(len(X)):
  x=X[i][0]
  h=X[i][1]
  if h>0:
    dele=set()
    for d in damage.items():
      if d[0]<x:
        dele.add(d[0])
      else:
        h-=d[1]
    for p in dele:
      del damage[p]
  if h>0:
    turn=(h+A-1)//A
    damage[x+D]=turn*A
    ans+=turn
print(ans)


### FIXED CODE ###

N,D,A=map(int,input().split())
D*=2 # 爆発の長さ
X=[None]*N
for i in range(N):
  X[i]=list(map(int,input().split()))

X=sorted(X,key=lambda x:x[0])
lastX=X[-1][0] # 最後のモンスターの場所
from collections import defaultdict
damage=defaultdict(int)
ans=0
for i in range(len(X)):
  x=X[i][0]
  h=X[i][1]
  if h>0:
    dele=set()
    for d in damage.items():
      if d[0]<x:
        dele.add(d[0])
      else:
        h-=d[1]
    for p in dele:
      del damage[p]
  if h>0:
    turn=(h+A-1)//A
    if x+D>lastX:
      damage[lastX]+=turn*A
    else:
      damage[x+D]=turn*A
    ans+=turn
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch-=1; cw-=1; dh-=1; dw-=1
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]

dwalk = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def Dijkstra(ch, cw):
    import heapq
    edgelist = [(0, ch, cw)]
    heapq.heapify(edgelist)
    dist[ch][cw] = 0
    while len(edgelist):
        cost, y, x = heapq.heappop(edgelist)
        dist[y][x] = cost
        if y==dh and x==dw:
            return dist
        for next_y, next_x in dwalk:
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if area[y+next_y][x+next_x]=='#': continue
                if dist[y+next_y][x+next_x]>cost:
                    dist[y+next_y][x+next_x] = cost
                    heapq.heappush(edgelist, (cost, y+next_y, x+next_x))
        for next_y in range(-2, 3):
            for next_x in range(-2, 3):
                    if 0<=y+next_y<h and 0<=x+next_x<w:
                        if area[y+next_y][x+next_x]=='#': continue
                        if dist[y+next_y][x+next_x]>cost+1:
                            dist[y+next_y][x+next_x] = cost+1
                            heapq.heappush(edgelist, (cost+1, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
if dist[dh][dw] == inf:
    print(-1)
else:
    print(dist[dh][dw])

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch-=1; cw-=1; dh-=1; dw-=1
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]

dwalk = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def Dijkstra(ch, cw):
    import heapq
    edgelist = [(0, ch, cw)]
    heapq.heapify(edgelist)
    dist[ch][cw] = 0
    while len(edgelist):
        cost, y, x = heapq.heappop(edgelist)
        if y==dh and x==dw:
            return dist
        if dist[y][x] < cost: continue
        for next_y, next_x in dwalk:
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if area[y+next_y][x+next_x]=='#': continue
                if dist[y+next_y][x+next_x]>cost:
                    dist[y+next_y][x+next_x] = cost
                    heapq.heappush(edgelist, (cost, y+next_y, x+next_x))
        for next_y in range(-2, 3):
            for next_x in range(-2, 3):
                    if 0<=y+next_y<h and 0<=x+next_x<w:
                        if area[y+next_y][x+next_x]=='#': continue
                        if dist[y+next_y][x+next_x]>cost+1:
                            dist[y+next_y][x+next_x] = cost+1
                            heapq.heappush(edgelist, (cost+1, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
if dist[dh][dw] == inf:
    print(-1)
else:
    print(dist[dh][dw])
### BUGGY CODE ###

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

BL = (300000).bit_length()
WIDTH = pow(2, BL)
BUFSIZE = pow(2, BL+1) - 1
BASE = BUFSIZE - WIDTH

# TODO: default value
buf = [0] * BUFSIZE

def update(i, x):
    i += BASE
    buf[i] = x
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2

# [q_left, q_right]
def search(q_left, q_right):
    return _search(0, WIDTH, 0, q_left, q_right)

def _search(l, width, i, q_left, q_right):
    if q_right < l or l + width - 1 < q_left:
        return 0
    if q_left <= l and l + width - 1 <= q_right:
        return buf[i]
    nwidth = width // 2
    c1 = _search(l, nwidth, 2*i+1, q_left, q_right)
    c2 = _search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
    return compare(c1, c2)

def compare(i1, i2):
    if i1 > i2:
        return i1
    else:
        return i2

for _ in range(N):
    a = int(input())
    maxlen = search(a-K, a+K)
    update(a, maxlen+1)
print(search(0, 300000))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())

BL = (300001-1).bit_length()
WIDTH = pow(2, BL)
BUFSIZE = pow(2, BL+1) - 1
BASE = BUFSIZE - WIDTH
DEFAULT = 0

buf = [DEFAULT] * BUFSIZE

def update(i, x):
    i += BASE
    buf[i] = x
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2

# [q_left, q_right]
def search(left, right):
    ansl = ansr = DEFAULT
    left += BASE
    right += BASE
    while left < right:
        if not (left & 1):
            ansl = compare(ansl, buf[left])
            left += 1
        if right & 1:
            ansr = compare(ansr, buf[right])
            right -= 1
        left = (left-1) // 2
        right = (right-1) // 2
    if left == right:
        ansl = compare(ansl, buf[left])
    return compare(ansl, ansr)

def compare(v1, v2):
    return v1 if v1 > v2 else v2

for _ in range(N):
    a = int(input().rstrip())
    maxlen = search(max(0, a-K), min(a+K, 300000))
    update(a, maxlen+1)
print(search(0, 300000))
### BUGGY CODE ###

import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    B = 61

    one_cnt = [0] * B
    for i in range(N):
        for b in range(B):
            one_cnt[b] += (A[i] >> b) & 1

    ans = 0
    for b in range(B):
        ans += 2 ** b * one_cnt[b] * (N - one_cnt[b])
        ans %= P
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

import numpy as np

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = np.array(A)

    ans = 0
    for b in range(60 + 1):
        cnt_1 = int(np.sum((A >> b) & 1))
        ans += 2 ** b * cnt_1 * (N - cnt_1)
        ans %= P
    print(ans)


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

N,Q = map(int,input().split())
S = input()

for i in range(Q):
    l, r = map(int,input().split())
    str = S[l-1:r]
    print(str.count("AC"))

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()

count_list = [0]*(N+1)

for i in range(N):
    if S[i:i+2] == 'AC':
        count_list[i+1] = count_list[i] + 1
    else:
        count_list[i+1] = count_list[i]

for i in range(Q):
    l, r = map(int,input().split())
    print(count_list[r-1] - count_list[l-1])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
num = 0
for i in range(N + 1):
    for j in range(N + 1):
        if N - R * i - G * j < 0:
            break
        if 0 <= N - R * i - G * j and (N - R * i - G * j) % B == 0:
            num += 1

print(num)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
num = 0
for i in range(N + 1):
    if N - R * i < 0:
        break
    for j in range(N + 1):
        if N - R * i - G * j < 0:
            break
        if 0 <= N - R * i - G * j and (N - R * i - G * j) % B == 0:
            num += 1

print(num)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 1
for i in range(1,N):
  minP = min(P[j] for j in range(0,i+1))
  if P[i] <= minP:
    ans += 1
  else:
    pass
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 1
Pj = P[0]
for i in range(1,N):
  Pj = min(Pj,P[i])
  if P[i] <= Pj:
    ans += 1
  else:
    pass
print(ans)
### BUGGY CODE ###

import hashlib

def make_table(N, S):
    mod = 2 ** 61 - 1
    table = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for head in range(N):
        for tail in range(head+1, N+1):
            if head < tail:
                encoded = S[head:tail].encode()
                table[head][tail] = int(hashlib.md5(encoded).hexdigest(), 16) // mod
    return table

def solve(N, S):
    table = make_table(N, S)
    longest = 0
    for i in range(1, N//2+1):
        for j in range(0, N-i):
            for k in range(j+i, N):
                if k+i > N:
                    continue
                # compare S[j:j+i] and S[k:k+i]
                if table[j][j+i] == table[k][k+i]:
                    longest = max(longest, i)
    return longest

def main():
    N = int(input().strip())
    S = input().strip()
    result = solve(N, S)
    print(result)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=999999937):
        """任意の基数と法でハッシュを生成する"""
        n = len(S)
        self.prefix = prefix = [0] * (n+1)
        self.power = power = [1] * (n+1)
        self.b = b
        self.m = m
        for i in range(n):
            c = ord(S[i])
            prefix[i+1] = (prefix[i] * b + c) % m
            power[i+1] = (power[i] * b) % m
    
    def get(self, l, r):
        """S[l, r) のハッシュを求める"""
        return (self.prefix[r] - self.power[r-l] * self.prefix[l]) % self.m
    
    def concat(self, h1, h2, l2):
        """S1+S2 のハッシュを、それぞれのハッシュから求める"""
        return (self.power[l2] * h1 + h2) % self.m
    
    def lcp(self, l1, r1, l2, r2):
        """S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める"""
        low = 0
        high = min(r1-l1, r2-l2) + 1
        while high - low > 1:
            mid = (high + low) // 2
            if self.get(l1, l1 + mid) == self.get(l2, l2 + mid):
                low = mid
            else:
                high = mid
        return low


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    ans = []
    for m in [999999937, 10**9+7]:
        b = random.randint(10000, m-1)
        rh = RollingHash(S, b=b, m=m)
        low = 0
        high = (N+1) // 2 + 1
        dmax = defaultdict(int)
        dmin = defaultdict(int)
        while high - low > 1:
            dmax.clear()
            dmin.clear()
            mid = (high + low) // 2
            for i in range(0, N-mid+1):
                h = rh.get(i, i+mid)
                dmax[h] = max(dmax[h], i+1)
                dmin[h] = max(dmin[h], N+1-i)
            is_match = False
            for h in dmax.keys():
                if dmax[h] - (N+2 - dmin[h]) >= mid:
                    is_match = True
                    break
            if is_match:
                low = mid
            else:
                high = mid
        ans.append(low)
    return min(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
### BUGGY CODE ###

import collections

N = input()
A = map(int, raw_input().split())
A.sort(reverse=1)
c = collections.Counter(A)
res = 0
for i in A:
    for j in xrange(60):
        p = 2 ** j
        if i > p:
            continue
        elif i == p:
            res += c[i] // 2
            c[i] = c[i] // 2 * 2
        else:
            num = min(c[i], c[p - i])
            res += num
            c[i] -= num
            c[p - i] -= num
print res


### FIXED CODE ###

import collections

N = input()
A = map(int, raw_input().split())
C = collections.Counter(A)
K = C.keys()
K.sort(reverse=1)
res = 0
for i in K:
    for j in xrange(60):
        p = 2 ** j
        if i <= p:
            break
    if i == p:
      res += C[i] // 2
      C[i] = C[i] // 2 * 2
    else:
      num = min(C[i], C[p - i])
      res += num
      C[i] -= num
      C[p - i] -= num
print res
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int


class ModOperator:
    def __init__(self, MOD: int = 10 ** 9 + 7):
        self.MOD = MOD

    def mod_pow(self, x: int, n: int):
        bi = str(format(n, "b"))
        res = 1
        a = x
        for i in range(len(bi)):
            if n >> i & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
        return res
    
    def mod_fact(self, x: int):
        res = 1
        for i in range(1, x + 1):
            res = res * i % self.MOD
        return res % self.MOD
    
    def mod_partial_fact(self, x: int, y: int):
        res = 1
        for i in range(x - y + 1, x + 1):
            res = res * i % self.MOD
        return res % self.MOD

    def mod_inv(self, x: int):
        return self.mod_pow(x, self.MOD - 2)
    
    def mod_comb(self, n: int, k: int):
        numerator = self.mod_partial_fact(n, k)
        denomintator = self.mod_fact(k)
        return numerator * self.mod_inv(denomintator) % self.MOD

def main():
    N, M, K = map(int, input().split())

    op = ModOperator(MOD)
    sum = 0
    for i in range(K + 1):
        sum += M * op.mod_pow(M - 1, N - 1 - i) * op.mod_comb(N - 1, i)
    print(sum % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int


class ModOperator:
    def __init__(self, MOD: int = 10 ** 9 + 7):
        self.MOD = MOD
        self.factorials = [1, 1]

    # x^n % MOD
    def mod_pow(self, x: int, n: int):
        bi = str(format(n, "b"))
        res = 1
        a = x
        for i in range(len(bi)):
            if n >> i & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
        return res
    
    # x! % MOD
    def mod_fact(self, x: int):
        if x < len(self.factorials):
            return self.factorials[x]
        else:
            res = self.factorials[-1]
            for i in range(len(self.factorials), x + 1):
                res = res * i % self.MOD
                self.factorials.append(res)
        return res % self.MOD

    # inverse of a number
    def mod_inv(self, x: int):
        return self.mod_pow(x, self.MOD - 2)
    
    # conmination nCk
    def mod_comb(self, n: int, k: int):
        numerator = self.mod_fact(n)
        denomintator1 = self.mod_fact(k)
        denomintator2 = self.mod_fact(n - k)
        denomintator = denomintator1 * denomintator2 % self.MOD
        return numerator * self.mod_inv(denomintator) % self.MOD

def main():
    N, M, K = map(int, input().split())

    op = ModOperator(MOD)
    sum = 0
    for i in range(K + 1):
        sum += M * op.mod_pow(M - 1, N - 1 - i) * op.mod_comb(N - 1, i)
    print(sum % MOD)


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

l, r = map(int, input().split())
n = range(l, r+1)
x = []
for i in range (len(n)-1):
    for j in range (i+1, len(n)):
        x.append(n[i]*n[j] % 2019)
print(min(x))

### FIXED CODE ###

l, r = map(int, input().split())
if l - r >= 2019:
    print(0)
else:
    n = range(l, r+1)
    min_x = 2018
    for i in range(len(n)-1):
        for j in range(i+1, len(n)):
            cur_x = ((n[i]%2019)*(n[j]%2019))%2019
            min_x = min(cur_x, min_x)
            if min_x == 0:
                break
        if min_x == 0:
                break
    print(min_x)
### BUGGY CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
Q=int(input())
B=[0]*Q;C=[0]*Q
for i in range(Q):
  B[i],C[i]=map(int,input().split())

#c = collections.Counter(A)
#print(c)

for i in range(Q):
  A = [C[i] if B[i]==A[j] else A[j] for j in range(N)]
#  print(A)
  print(sum(A))

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
Q=int(input())
B=[0]*Q;C=[0]*Q
for i in range(Q):
  B[i],C[i]=map(int,input().split())

D = collections.Counter(A)
s=sum(A)
for i in range(Q):
  s=s-B[i]*D[B[i]]
  D[C[i]]+=D[B[i]]
  s=s+C[i]*D[B[i]]
  D[B[i]]=0
#  A = [C[i] if B[i]==A[j] else A[j] for j in range(N)]
#  print(A)
  print(s)
### BUGGY CODE ###

N = int(input())
S = input()
R = []
G = []
B = []
for i, s in enumerate(S):
    if s == 'R':
        R.append(i+1)
    elif s == 'G':
        G.append(i+1)
    else:
        B.append(i+1)
res = [sorted([r, g, b]) for r in R for g in G for b in B]
print(len([x for x in res if x[1] - x[0] != x[2] - x[1]]))

### FIXED CODE ###

from collections import Counter

N = int(input())
S = input()
RGB_Counter = Counter(S)
ans = RGB_Counter['R'] * RGB_Counter['G'] * RGB_Counter['B']

dum = []
d = 0
while 3 + d*2 <= N:
    for i in range(N - 2*(d+1)):
        a = S[i]
        b = S[i+d+1]
        c = S[i+2*(d+1)]
        if a != b and b != c and c != a:
            ans -= 1
    d += 1

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

N = int(input())
A = list(map(int, input().split()))
mod = int(1e9+7)
A.sort(reverse=True)
for i in range(N):
    A[i] = format(A[i], 'b')
    A[i] = A[i].zfill(len(A[0]))
ans = 0
for i in range(len(A[0])):
    count_1 = 0
    count_0 = 0
    for a in A:
        if a[i] == '0':
            count_0 += 1
        else:
            count_1 += 1
    ans += count_0 * count_1 * pow(2, len(A[0])-i-1, mod) 
    ans %= mod
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = int(1e9+7)
A.sort(reverse=True)
for i in range(N):
    A[i] = format(A[i], 'b')
    A[i] = A[i].zfill(len(A[0]))
ans = 0
for i in range(len(A[0])):
    count_1 = 0
    count_0 = 0
    for a in A:
        if a[i] == '0':
            count_0 += 1
        else:
            count_1 += 1
    ans += count_0 * count_1 * pow(2, len(A[0])-i-1, mod) 
    ans %= mod
print(ans)
### BUGGY CODE ###

# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys
import bisect

N = int(input())
now = int(sys.stdin.readline().strip())
ans = [now]

for n in range(N - 1):
    now = int(sys.stdin.readline().strip())

    if now > ans[0]:
        ans[0] = now
    elif ans[-1] >= now:
        ans.append(now)
    else:
        # 2部探査で行進位置を探る
        left = 0  # 挿入不可能
        right = len(ans) - 1  # 挿入可能

        while right - left > 1:
            mid = (right - left) // 2
            if ans[mid] > now:
                right = mid
            else:
                left = mid

        ans[right] = now

print(len(ans))

    # if ans:  # 最初の入力以外であり、すでに追加対象のリストが存在する
    #     if ans[0][-1] < now:
    #         ans[0].append(now)
    #     elif ans[-1][-1] >= now:
    #         appending = [now]
    #         ans.append(appending)
    #     else:
    #         # 二分探索で追加するリストの位置を特定する
    #         left = 0   # 追加できない  ans[left][-1] > now
    #         right = len(ans) - 1  # ans[right][-1] < now
    #
    #         while right - left > 1:
    #             mid = (right - left) // 2
    #             if ans[mid][-1] < now:
    #                 right = mid
    #             else:
    #                 left = mid
    #         ans[right].append(now)
    # else:
    #     appending = [now]
    #     ans.append(appending)

    # for a in ans:
    #     if a[-1] < now:
    #         a.append(now)
    #         break
    # else:
    #     appending = [now]
    #     ans.append(appending)

# print(len(ans))


### FIXED CODE ###

# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys
import bisect

N = int(input())
now = int(sys.stdin.readline().strip())
ans = [now]

for n in range(N - 1):
    now = int(sys.stdin.readline().strip())

    if now > ans[0]:
        ans[0] = now
    elif ans[-1] >= now:
        ans.append(now)
    else:
        # 2部探査で行進位置を探る
        left = 0  # 挿入不可能
        right = len(ans) - 1  # 挿入可能

        while right - left > 1:
            mid = (right + left) // 2
            if now > ans[mid]:
                right = mid
            else:
                left = mid

        ans[right] = now

print(len(ans))

    # if ans:  # 最初の入力以外であり、すでに追加対象のリストが存在する
    #     if ans[0][-1] < now:
    #         ans[0].append(now)
    #     elif ans[-1][-1] >= now:
    #         appending = [now]
    #         ans.append(appending)
    #     else:
    #         # 二分探索で追加するリストの位置を特定する
    #         left = 0   # 追加できない  ans[left][-1] > now
    #         right = len(ans) - 1  # ans[right][-1] < now
    #
    #         while right - left > 1:
    #             mid = (right - left) // 2
    #             if ans[mid][-1] < now:
    #                 right = mid
    #             else:
    #                 left = mid
    #         ans[right].append(now)
    # else:
    #     appending = [now]
    #     ans.append(appending)

    # for a in ans:
    #     if a[-1] < now:
    #         a.append(now)
    #         break
    # else:
    #     appending = [now]
    #     ans.append(appending)

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

n,k = map(int,input().split())
P = [-1] + list(map(int,input().split())) + [2*(10**5)+1]
Q = [''.join(map(str,P))]
for i in range(1,n-k+1):
    q = P[:i] + sorted(P[i:i+k]) + P[i+k:]
    Q += [''.join(map(str,q))]
print(len(set(Q)))

### FIXED CODE ###

class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res

    def add(self, index, x):
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1


N, K = map(int, input().split())
P = list(map(lambda x: int(x) + 1, input().split()))

bit = BinaryIndexedTree(N + 1)
count = 1

for i in range(K):
    bit.add(P[i], 1)

for i in range(N - K):
    mi = bit.bisect_left(1)
    ma = bit.bisect_left(K)
    if P[i] != mi or P[K + i] < ma:
        count += 1
    bit.add(P[i], -1)
    bit.add(P[K + i], 1)

inc = 1
incseq = 0

for i in range(N - 1):
    if P[i] < P[i + 1]:
        inc += 1
        if inc == K:
            incseq += 1
    else:
        inc = 1

print(count - max(0, incseq - 1))
### BUGGY CODE ###

n, q = map(int, input().split())
gu = [set() for _ in range(n)]
gl = [set() for _ in range(n)]

def upper(a,b):
  if gu[a] == {}:
    gl[a].add(b)
  else:
    gl[a].add(b)
    for l in gu[a]:
      upper(l, b)

candidate = set()
for i in range(n-1):
  a, b = map(int,input().split())
  a, b = a-1, b-1
  gu[b].add(a)
  candidate.add(b)

for b in candidate:
  for a in gu[b]:
    upper(a,b)

#print(gu)
#print(gl)

c = [0]*n
for j in range(q):
  x, p = map(int, input().split())
  x = x-1
  c[x] += p
  for k in gl[x]:
    c[k] += p

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

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append(b)
  #g[b].append(a)

ans = [0]*n  
for j in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
from collections import deque
s = deque()
s.append(0)

while s:
  v = s.pop()
  for v_ in g[v]:
    ans[v_] += ans[v]
    s.append(v_)

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