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

N,M,Q=map(int,input().split())
L,R=[],[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    if i>j:
      c[i][j]=0
    c[i][j]+=c[i][j-1]
ans=[0]*Q
for i in range(Q):
  for j in range(Pl[i],Ql[i]+1):
    ans[i]+=c[j][Ql[i]]-c[j][Pl[i]-1]
for i in range(Q):
  print(ans[i])

### FIXED CODE ###

N,M,Q=map(int,input().split())
L,R=[],[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i][j-1]
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i-1][j]
for i in range(Q):
  ans=c[Ql[i]][Ql[i]]-c[Pl[i]-1][Ql[i]]-c[Ql[i]][Pl[i]-1]+c[Pl[i]-1][Pl[i]-1]
  print(ans)
### BUGGY CODE ###

import math
import copy

def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l

n=nCast(input())
a=nCast(inputArr1(n))
b=copy.deepcopy(a)





def akey(a):
    return a[0],a[1]
def bkey(a):
    return a[1],a[0]
list.sort(a,key=akey,reverse=True)
list.sort(b,key=bkey,reverse=True)

def remove(a, data,tag):
    if tag:
        tag=0
    else:
        tag=1
    n = len(a)
    first = 0
    last = n - 1

    while first <= last:
        mid = int(first + ((last - first) / 2))

        if a[mid][tag] < data[tag] or (a[mid][tag] == data[tag] and a[mid][1-tag] < data[1-tag]):
            last = mid - 1
        elif a[mid][tag] > data[tag] or (a[mid][tag] == data[tag] and a[mid][1-tag] > data[1-tag]):
            first = mid + 1
        else:
            del a[mid]
            return

def func(a,b):
    pa,pb=0,0
    tag=True
    while len(a)!=0:
        if a[0]==b[0]:
            tmp=a[0]
        else:
            v1=a[0][0]-b[0][1]
            v2=b[0][0]-b[1][1]
            if v1>v2:
                tmp=a[0]
            else:
                tmp=b[0]
        if tag:
            pa+=tmp[0]
        else:
            pb+=tmp[1]
        remove(a,tmp,tag)
        remove(b,tmp,not tag)
        tag=not tag
        a,b=b,a

    return pa-pb
    
print(func(a,b)) 







### FIXED CODE ###

import math
import copy

def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l

n=nCast(input())
a=nCast(inputArr1(n))

def akey(a):
    return a[0]+a[1]
list.sort(a,key=akey,reverse=True)


def func(a):
    pa,pb=0,0
    tag=True
    for idx in range(0,len(a)):
        if tag:
            pa+=a[idx][0]
        else:
            pb+=a[idx][1]
        tag=not tag
    return pa-pb
    
print(func(a))
### BUGGY CODE ###

#!/usr/bin/env python3


def is_ok(mid, K, A, F):
    used = 0
    for a, f in zip(A, F):
        upper = int(mid / f)
        if upper < a:
            used += a - upper
        if K < used:
            return False
    return True


def main():
    N, K = input_line(int, int)
    A = input_line([int])
    F = input_line([int])
    A.sort()
    F.sort(reverse=True)

    ng = -1
    ok = int(1e12)
    while ok - ng > 1:
        mid = (ng + ok) // 2
        if is_ok(mid, K, A, F):
            ok = mid
        else:
            ng = mid
    print(ok)


def input_line(*types):
    if isinstance(types[0], list):
        return list(map(types[0][0], input().split()))
    elif len(types) == 1:
        return types[0](input())
    else:
        return [t(x) for t, x in zip(types, input().split())]


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import numpy as np


def is_ok(mid, K, A, F):
    return np.maximum(A - mid // F, 0).sum() <= K


def main():
    N, K = input_line(int, int)
    A = input_line([int])
    F = input_line([int])
    A = np.array(sorted(A))
    F = np.array(sorted(F, reverse=True))

    ng = -1
    ok = int(1e12)
    while ok - ng > 1:
        mid = (ng + ok) // 2
        if is_ok(mid, K, A, F):
            ok = mid
        else:
            ng = mid
    print(ok)


def input_line(*types):
    if isinstance(types[0], list):
        return [types[0][0](x) for x in input().split()]
    elif len(types) == 1:
        return types[0](input())
    else:
        return [t(x) for t, x in zip(types, input().split())]


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

N, Q = map(int,input().split())
S= input()
lr_list = [list(map(int,input().split())) for _ in range(Q)]
for i in range(Q):
    l = lr_list[i][0] -1
    r = lr_list[i][1] -1
    s = S[l:r+1]
    ans = s.count('AC')
    print(ans)


### FIXED CODE ###

N, Q = map(int,input().split())
S= input()
lr_list = [list(map(int,input().split())) for _ in range(Q)]

# ac_tf_list = [1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]
t = [0]*N
for i in range(N-1):
    if S[i:i+2]=='AC':
        t[i+1] = t[i]+1
    else:
        t[i+1] = t[i]

for i in range(Q):
    l = lr_list[i][0]-1
    r = lr_list[i][1]-1
    print(t[r]-t[l])
### BUGGY CODE ###

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

end_list = list(filter(lambda x: x[1] == N, ab_list))

res = False

for end in end_list:
    if res:
        break
    if len(list(filter(lambda x: (x[1] == end[0]) and (x[0] == 1) or end[0] == 1, ab_list))) > 0:
        res = True
        break


if res:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

N, M = map(int, input().split())
ab_list = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

lis = [[] for i in range(N)]

for i in range(M):
    lis[ab_list[i][0]].append(ab_list[i][1])

que = [[0, 0, lis[0], []]]
ends = []
res = False

while que:
    count, now, next_nodes, visited = que.pop()
    visited.append(now)
    if now == N - 1:
        ends = visited[:]
    for node in next_nodes:
        if node in visited or count == 2:
            continue
        que.append([count + 1, node, lis[node], visited[:]])

if N - 1 in ends:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

s = list(input())
l = int(input())
s1 = sorted(s)
ans = set()

for i in range(len(s)):
    sta = s1[i]
    for j in range(len(s)):
        if s[j] == sta:
            ans.add(s[j])
            check = s[j]
            for k in range(j+1,len(s)):
                check = check+s[k]
                ans.add(check)
    if len(ans) >= l:
        ans1 = sorted(ans)
        print(ans1[l-1])
        exit()
ans1 = sorted(ans)
print(ans1[l-1])

### FIXED CODE ###

s = list(input())
l = int(input())
s1 = sorted(s)
ans = set()

for i in range(len(s)):
    sta = s1[i]
    for j in range(len(s)):
        if s[j] == sta:
            ans.add(s[j])
            check = s[j]
            for k in range(j+1,min(len(s),j+5)):
                check = check+s[k]
                ans.add(check)
    if len(ans) >= l:
        ans1 = sorted(ans)
        print(ans1[l-1])
        exit()
ans1 = sorted(ans)
print(ans1[l-1])
### BUGGY CODE ###

import sys,gc

    
A=[]
n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.insert(0,s[7:])
    elif s[6] == ' ':
        try:
            A.remove(s[7:])
        except:
            pass
    elif s[6] == 'F':
        A.pop(0)
    elif s[6] == 'L':
        A.pop()
    n -=1
    
for e in A:
    print int(e),

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
### BUGGY 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 size(self, x):
        return -self.parents[self.find(x)]

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m,k = map(int,input().split())
uf = UnionFind(n)
block = {i:[] for i in range(n)}
count = [-1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)   
    block[min(a-1,b-1)].append(max(a-1,b-1))
for i in range(k):
    c,d = map(int,input().split())
    block[min(c-1,d-1)].append(max(c-1,d-1))
for i in range(n):
    for j in range(n):
        if uf.same(i,j) and not max(i,j) in block[min(i,j)]:
            count[i] += 1
print(" ".join(map(str,count)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
class UnionFind():
    def __init__(self, n):
        self.parents = [-1]*n
        self.count = [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
        self.parents[y] = x
        self.count[x] +=  self.count[y]
n,m,k = map(int,input().split())
uf = UnionFind(n)
block = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1) 
    block[a-1].append(b-1)
    block[b-1].append(a-1)
for i in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1].append(d-1)
        block[d-1].append(c-1)
ans = []
for i in range(n):
    ans.append(uf.count[uf.find(i)]-len(block[i])-1)
print(" ".join(map(str,ans)))
### BUGGY CODE ###

n,*s=map(int,open(0).read().split());s,t,f,g=[s[i*n:i*n+n]for i in range(4)];r=range(n);a=[n*[0]for _ in r];e=enumerate
for b in range(64):
 y=1<<b;u=[k&y for k in f];v=[k&y for k in g];l=[0]*n;m=l[:]
 for i,k in e(u):
  for j,h in e(v):
   if(k&h)|((s[i]^1)*k)|((t[j]^1)*h):a[i][j]|=y;l[i]+=1;m[j]+=1
 for i in r:
  for j in r:
   if(l[i]==0)*s[i]*u[i]*(t[j]^1)*(n-m[j]>1):a[i][j]|=y;m[j]+=1;break
   if(m[i]==0)*t[i]*v[i]*(s[j]^1)*(n-l[j]>1):a[j][i]|=y;l[j]+=1;break
h=a[0][:];w=[i[0]for i in a]
for i,k in e(a):
 for j,l in e(k):w[i]=(l|w[i]if s[i]else w[i]&l);h[j]=(l|h[j]if t[j]else h[j]&l)
if(g!=h)|(f!=w):print(-1);exit() 
for i in a:print(*i)


### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
u=list(map(int,input().split()))
v=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
ss=[u[i]if s[i]==0 else 0 for i in range(n)]
tt=[v[i]if t[i]==0 else 0 for i in range(n)]
son=[[]for _ in range(n)]
ton=[[]for _ in range(n)]
sno=[[n-1]*64 for _ in range(n)]
tno=[[n-1]*64 for _ in range(n)]
for i in range(n):
  for j in range(n):
    ans[i][j]=u[i]&v[j]
    if s[i]==0:
      ans[i][j]|=u[i]
      ss[i]&=ans[i][j]
    else:
      ss[i]|=ans[i][j]
    if t[j]==0:
      ans[i][j]|=v[j]
      tt[j]&=ans[i][j]
    else:
      tt[j]|=ans[i][j]
    if s[i]==0 or t[i]==0:
      for k in range(64):
        if ans[i][j]&1<<k:
          if s[i]==0:sno[i][k]-=1
          if t[j]==0:tno[j][k]-=1
    if j==n-1:
      if s[i]==1:
        if ss[i]|u[i]>u[i]:print(-1);exit()
        if ss[i]!=u[i]:
          for k in range(64):
            if u[i]&1<<k:
              if (ss[i]&1<<k)==0:
                son[i].append(k)
          ss[i]=1
        else:ss[i]=0
      else:
        if ss[i]!=u[i]:print(-1);exit()
        else:ss[i]=2
    if i==n-1:
      if t[j]==1:
        if tt[j]|v[j]>v[j]:print(-1);exit()
        if tt[j]!=v[j]:
          for k in range(64):
            if v[j]&1<<k:
              if (tt[j]&1<<k)==0:
                ton[j].append(k)
          tt[j]=1
        else:tt[j]=0
      else:
        if tt[j]!=v[j]:print(-1);exit()
        else:tt[j]=2
for i in range(n):
  for k in son[i]:
    for j in range(n):
      if t[j]==0:
        if tno[j][k]>0:
          ans[i][j]|=1<<k
          tno[j][k]-=1
          break
      if j==n-1:print(-1);exit()
for j in range(n):
  for k in ton[j]:
    for i in range(n):
      if s[i]==0:
        if sno[i][k]>0:
          ans[i][j]|=1<<k
          sno[i][k]-=1
          break
      if i==n-1:print(-1);exit()
for i in range(n):
  if s[i]==0:uu=ans[i][0]
  else:uu=0
  for j in range(n):
    if s[i]==0:uu&=ans[i][j]
    else:uu|=ans[i][j]
  if uu!=u[i]:print(-1);exit()
for j in range(n):
  if t[j]==0:vv=ans[0][j]
  else:vv=0
  for i in range(n):
    if t[j]==0:vv&=ans[i][j]
    else:vv|=ans[i][j]
  if vv!=v[j]:print(-1);exit()
for i in ans:print(*i)
### BUGGY CODE ###

if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = {}
    for i in range(n):
        key = str(i+1)
        ans[key] = a[i]
    ans = sorted(ans.items(), key=lambda x: x[1])
    ans_str =""
    for i in ans:
        if ans_str =="":
            ans_str = str(i[0])
        else:
            ans_str = ans_str+" "+str(i[0])
    print(ans_str)

### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = [0]*n
    for i in range(n):
        ans[a[i]-1] = i+1
    ans_list = map(str, ans)  # mapで要素すべてを文字列に
    ans_str =' '.join(ans_list)
    print(ans_str)
### BUGGY CODE ###

X, Y = map(int, input().split())
count = 0
flag = 0


def checkY(N, count, X):
    if count == X and N == 0:
        return True
    elif count == X and N != 0:
        return False

    if checkY(N - 2, count + 1, X):
        return True

    if checkY(N - 4, count + 1, X):
        return True

    return False


if checkY(Y, 0, X):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

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

crane = (4 * X - Y) / 2
turtle = (Y - 2 * X) / 2


def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False


if is_integer_num(crane) and crane >= 0 and is_integer_num(turtle) and turtle >= 0:
    print("Yes")

else:
    print("No")
### BUGGY CODE ###

A = list(map(int, input().split()))
A.sort()
a = A[0]
b = A[1]
ans = a

for i in range(1, b-a+1):
    ans *= a + i
    i += 1

if ans > 0:
    print("Positive")
elif ans < 0:
    print("Negative")
else:
    print("Zero")    


### FIXED CODE ###

A = list(map(int, input().split()))
A.sort()
a = A[0]
b = A[1]
c = b-a

if a <= 0 <= b:
    print("Zero")

elif a > 0:
    print("Positive")

elif b < 0:
    if c%2 == 1:
        print("Positive")
    else:
        print("Negative")
### BUGGY CODE ###

h,n=map(int,input().split())
magics=[list(map(int,input().split())) for i in range(n)]

import numpy as np

dp = np.full((n+1, h+1), 10**10)
dp[0][0]=0
for i in range(0,n):
  damage = magics[i][0]
  cost = magics[i][1]
  for j in range(0,h+1):
    dp[i+1][j] = min( dp[i+1][j], dp[i][j] )

    to = min( j+damage, h )
    dp[i+1][to] = min( dp[i+1][j]+cost, dp[i+1][to] )
                                                 
print(dp[n][h])

### FIXED CODE ###

h,n=map(int,input().split())
magics=[list(map(int,input().split())) for i in range(n)]

#import numpy as np

#dp = np.full((n+1, h+1), 10**10)
dp=[[10**10 for _ in range(h+1)]for _ in range(n+1)]
dp[0][0]=0
for i in range(0,n):
  damage = magics[i][0]
  cost = magics[i][1]
  for j in range(0,h+1):
    dp[i+1][j] = min( dp[i+1][j], dp[i][j] )

    to = min( j+damage, h )
    dp[i+1][to] = min( dp[i+1][j]+cost, dp[i+1][to] )
                                                 
print(dp[n][h])
### BUGGY CODE ###

from collections import Counter
 
def verify_anagrams(first_word, second_word):
    def get_counter(s):
        return Counter(s.upper().replace(' ', ''))

    return get_counter(first_word) == get_counter(second_word)

n = int(input())
s = []
for i in range(n):
    l = input()
    s.append(l)
cnt = 0 
for i in range(n-1):
    for j in range(i+1, n):
        if verify_anagrams(s[i], s[j]) == True:
            cnt += 1
print(cnt)



### FIXED CODE ###

from collections import Counter
n=int(input())
s = []
for i in range(n):
    t = list(input())
    t.sort()
    s.append(''.join(t))
c = Counter(s)
sum = 0
for i in c.values():
    sum += i*(i-1)//2
print(sum)

"""
n = int(input())
dic = {}
for i in range(n):
    s = list(input())
    s.sort()
    t = "".join(s)
    if t in dic.keys():
        dic[t] += dic[t] + 1
    elif t not in dic.keys():
        dic[t] = 0
print(sum(dic.values()))
"""
### BUGGY CODE ###

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

maxim = 0
for i in range(N-1):
    count = 0
    for j in range(i,N-1):
        if H[j] >= H[j+1]:
            count += 1
        else:
            break
    if count > maxim:
        maxim = count
print(maxim)

### FIXED CODE ###

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

maxim = 0
count = 0
for i in range(N-1):
    if H[i] >= H[i+1]:
        count += 1
    else:
        count = 0
    if count > maxim:
        maxim = count
print(maxim)
### BUGGY CODE ###

import sys
from bisect import bisect_left as bi_l, bisect_right as bi_r


x, y, z, k = map(int, sys.stdin.readline().split())
a, b, c = (sorted(map(int, sys.stdin.readline().split())) for _ in range(3))

def count_atleast_k(border):
    combs = 0
    for i in range(x):
        for j in range(y):
            combs += z - bi_r(c, border - a[i] - b[j])
    return combs >= k

def main():
    hi = 3 * 10 ** 10 + 1
    lo = 2
    while lo + 1 < hi:
        border = (lo + hi) // 2
        if count_atleast_k(border):
            lo = border
        else:
            hi = border

    res = []
    for i in range(x-1, -1, -1):
        if hi - a[i] > b[-1] + c[-1]:
            break
        for j in range(y-1, -1, -1):
            if hi - a[i] - b[j] > c[-1]:
                break
            for k in range(z-1, -1, -1):
                if hi - a[i] - b[j] - c[k] > 0:
                    break
                res.append(a[i] + b[j] + c[k])
    
    return sorted(res, reverse=True)

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

### FIXED CODE ###

import sys
import numpy as np
from heapq import heappush, heappop


def main():
    x, y, z, K = map(int, sys.stdin.readline().split())
    abc = np.array(sys.stdin.read().split(), dtype=np.int64)
    a = abc[:x]
    b = abc[x:x + y]
    c = abc[x + y:x + y+ z]
    a = np.sort(a)[::-1]
    b = np.sort(b)[::-1]
    c = np.sort(c)[::-1]

    hq = []
    heappush(hq, (-(a[0]+b[0]+c[0]), 0, 0, 0))
    res = []
    added_before = set()
    # setで確認をO(1)でする
    added_before.add((0, 0, 0))

    for _ in range(K):
        sum_deli, i, j, k = heappop(hq)
        res.append(-sum_deli)
        if i < x - 1 and not (i+1, j, k) in added_before:
            heappush(hq, (-(a[i+1]+b[j]+c[k]), i+1, j, k))
            added_before.add((i+1, j, k))
        if j < y - 1 and not (i, j+1, k) in added_before:
            heappush(hq, (-(a[i]+b[j+1]+c[k]), i, j+1, k))
            added_before.add((i, j+1, k))
        if k < z - 1 and not (i, j, k+1) in added_before:
            heappush(hq, (-(a[i]+b[j]+c[k+1]), i, j, k+1))
            added_before.add((i, j, k+1))

    for s_deli in res:
        print(s_deli)

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

# -*- coding: utf-8 -*-
 
num_product, num_coupon = [int(s) for s in input().split()]
price_list = [int(s) for s in input().split()]
price_list.sort()
price_list.reverse()
discountable_price = price_list[0:num_coupon]

fixed_sum = 0

for price in price_list[num_coupon:]:
  fixed_sum += price

for i in range(num_coupon):
  discountable_price[0] //= 2
  discountable_price.sort()
  discountable_price.reverse()

sum = 0
for price in discountable_price:
  sum += price

sum += fixed_sum
print(sum)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq

num_product, num_coupon = [int(s) for s in input().split()]
price_list = []
for s in input().split():
  heapq.heappush(price_list, int(s)*-1)

for i in range(num_coupon):
  min = price_list[0]
  heapq.heapreplace(price_list, (min*-1//2)*-1)

sum = 0
for price in price_list:
  sum -= price

print(sum)
### BUGGY CODE ###

from sys import stdout
import random

def query(num):
    print(num)
    stdout.flush()
    return input()

N = int(input())

ans = [None]*(N-1)
minimum = 0
maximum = N-1

q = minimum
ans[q] = query(q)
if ans[q] != "Vacant":
    while True:
        if q == 0:
            q = maximum
            ans[q] = query(q)
            if ans[q] == "Vacant":
                break
        else:
            q = (minimum + maximum) // 2
            ans[q] = query(q)
            if ans[q] == "Vacant":
                break

            if ((q - 1) - minimum)%2 == 0 and ans[q-1] != ans[minimum]:
                maximum = q - 1
            elif ((q - 1) - minimum)%2 == 1 and ans[q-1] == ans[minimum]:
                maximum = q - 1
            elif (maximum - (q + 1))%2 == 0 and ans[maximum] != ans[q + 1]:
                minimum = q + 1
            elif (maximum - (q + 1))%2 == 1 and ans[maximum] == ans[q + 1]:
                minimum = q + 1

### FIXED CODE ###

N = int(input())
 
def query(x):
    print(x, flush=True)
    response = input()
    if response == "Vacant":
        exit()
    return response
 
lb = 0
ub = N - 1

l_query = query(lb)
u_query = query(ub)

while True:
    m = (lb + ub) // 2
    m_query = query(m)
    if (m_query == l_query) == (m % 2 == lb % 2):
        lb = m
        l_query = m_query
    else:
        ub = m
### BUGGY CODE ###

from collections import deque
from collections import Counter
S = (input())
A = deque([0])
n = 0
t = 1
for i in reversed(S):
    x = int(i)
    n += x*t
    A.append(n%2019)
    t *= 10
C = Counter(A)
cnt= 0
for v in C.values():
    cnt += v*(v-1)//2
print(cnt)

### FIXED CODE ###

S = input()
cnt = [0]*2019
cnt[0] = 1
n = 0
t = 1
for i in reversed(S):
    n += int(i)*t
    n %= 2019
    cnt[n] += 1
    t *= 10
    t %= 2019
print(sum(i*(i-1)//2 for i in cnt))