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

from collections import deque
H, W = map(int, input().split())
k=[]
l=[]
def intersection(lst1, lst2): 
    lst3 = [value for value in lst1 if value in lst2] 
    return lst3 
for i in range(W):
    ta,tb = map(int, input().split())
    if ta == 1:
        k.append(tb)
    if tb == H:
        l.append(ta)
s = 0
p = intersection(l,k)
if len(p)>=1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
k=[0]*200000
for i in range(W):
    ta,tb = map(int, input().split())
    if ta == 1:
        k[tb-1]+=1
    if tb == H:
        k[ta-1]+=1
s = 0
for i in range(len(k)):
    if k[i]>=2:s=1
if s ==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]

a = {}
y = []
for mi in range(m):
    pi, yi = [int(i) for i in input().split()]
    if pi in a:
        a[pi].append(yi)
    else:
        a[pi] = [yi]
    y.append(yi)

for av in a.values():
    av.sort()

for yi in y:
    for ak, av in a.items():
        if yi in av:
            print(str(ak).zfill(6) + str(av.index(yi) + 1).zfill(6))
            break

### FIXED CODE ###

n, m = [int(i) for i in input().split()]
ipyo = [[i] + [int(_) for _ in input().split()] + [0] for i in range(m)]

ipyo.sort(key=lambda x: x[2])

cnt = [0] * n
for v in ipyo:
    p = v[1]
    cnt[p - 1] += 1
    v[3] = cnt[p - 1]

ipyo.sort(key=lambda x: x[0])

for v in ipyo:
    print('{0:06d}'.format(v[1]) + '{0:06d}'.format(v[3]))
### BUGGY CODE ###

N = int(input())
X = str(input())

from decimal import Decimal
from functools import lru_cache


@lru_cache(maxsize=200000)
def popcount(bits: str):
    return len([elm for elm in bits if elm == '1'])


cache = dict()

@lru_cache(maxsize=1000000)
def f(num):
    if num == 0:
        return 0
    else:
        # if not cache.get(num % pc, None) is None:
        #     return cache[num % pc]
        # pc = popcount('{:b}'.format(num))
        pc = popcount(''.join(sorted('{:b}'.format(num))))
        ret = 1 + f(num % pc)
        # cache[num % pc] = ret
        return ret


def reverse_bit(bits: str, digit):
    def toggle(a):
        if a == '1':
            return '0'
        else:
            return '1'

    ret = list(bits)
    ret[digit-1] = toggle(bits[digit-1])
    return ''.join(ret)

def convert(x: str):
    ans = 0
    i = 0
    for elm in list(x)[::-1]:
        if elm == '1':
            ans += 2 ** i
        i += 1
    return ans


answers = {}

for i in range(1, N+1):
    bits = reverse_bit(X, i)
    # pc = popcount(bits)
    # print(f'# {bits} {convert(bits)} {pc}')
    x = convert(bits)
    if not answers.get(x, None) is None:
        print(answers[x])
        continue
    ret = f(x)
    answers[x] = ret
    print(ret)

### FIXED CODE ###

n = int(input())
# for i in range(n):
#     print('0', end='')
# print(flush=True)
s = input()
x = int(s, base=2)
popcount = s.count('1')
y_zero = x % (popcount + 1)
if popcount > 1:
    y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0
 
 
def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]
 
 
ans = [0] * n
rem_zero = 1
if popcount > 1:
    rem_one = popcount - 2
for i in range(n):
    if s[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    elif popcount > 1:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    else:
        ans[n - 1 - i] = 0
    rem_zero = rem_zero * 2 % (popcount + 1)
    if popcount > 1:
        rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

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

print(len([i for i in range(n) if p[i] == min(p[:i+1])]))

### FIXED CODE ###

n = int(input())
p_list = list(map(int, input().split()))
 
mi = p_list[0]
ans = 1
for i in range(1, n):
  if mi >= p_list[i]:
    ans += 1
    mi = p_list[i]
print(ans)
### BUGGY CODE ###

a,b,x=map(int,input().split())
c=0
for i in range(a,b+1):
  if i%x==0:
    c+=1
print(c)

### FIXED CODE ###

a, b, x = [int(x) for x in input().split()]
print((b//x)-((a-1)//x))
### BUGGY CODE ###

import sys
import numpy as np
#from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))


### FIXED CODE ###

from itertools import accumulate
#from operator import add

N,K = map(int,input().split())
A = map(int,input().split()) 
for k in range(K):
    B = [0] * N
    for i,x in enumerate(A):
        L = max(0, i-x)
        R = min(N-1, i+x)
        B[L] += 1
        if R+1 != N:
            B[R+1] -= 1
    #L = accumulate(B,add) 
    L = list(accumulate(B))[:]
    if L == A:
        break
    A = L
print(*A)
### BUGGY CODE ###

from itertools import combinations

n = int(input())
s = input()

ans = 0
for x, y, z in combinations(range(n), 3):
    if y - x != z - y:
        if s[x] != s[y] and s[x] != s[z] and s[y] != s[z]:
            ans += 1

print(ans)

### FIXED CODE ###

import sys
from operator import mul
from functools import reduce
from collections import Counter

n = int(input())
s = input()

c = Counter(s)
if len(c) != 3:
    print(0)
    sys.exit()

ans = reduce(mul, c.values())

for i in range(n - 1):
    x, y, z = i, i + 1, i + 2
    while z <= n - 1:
        if s[x] != s[y] and s[x] != s[z] and s[y] != s[z]:
            ans -= 1
        y += 1
        z += 2

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

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

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

### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
li = []
cnt = 0

for i in range(N-1):
  if S[i]=='A' and S[i+1]=='C':
    cnt += 1
    li.append(cnt)
  else:
    li.append(cnt)

for i in range(Q):
  l, r = map(int, input().split())
  if l > 1:
    ans = li[r-2] - li[l-2]
  else:
    ans = li[r-2]
  print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,p=map(int,input().split())
s=input()
ans=0

if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
        ans += i + 1
  print(ans)
  exit()
    
total=[0]*p#pで割った余りで分類
total[0]=1#t[0]=0の分をあらかじめカウント
t=[0]*(n+1)#s[i:n]を格納する用の配列
for i in range(n-1,-1,-1):
    t[i]=t[i+1]+int(s[i])*10**(n-1-i)%p#s[i:n]を漸化式で付け加えていく
    total[t[i]%p]+=1
    
for i in range(p):
    ans+=total[i]*(total[i]-1)//2
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,p = [int(i) for i in input().split()]
s = input()
ans = 0

import math
def nCr(n, r):
  if n < r:
    return 0
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
    exit()

else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk[m] += 1
  for i in chk:
    ans += nCr(i,2)
  print(ans)
### BUGGY CODE ###

S=input()
T=input()

s=len(S)
t=len(T)
#DPテーブル作成
dp=[['']*(t+1) for _ in range(s+1)]

for i in range(s):
    for j in range(t):
        if S[i] ==T[j]:
            dp[i+1][j+1] =dp[i][j] + S[i]
        else:
            dp[i+1][j+1] =  max([ dp[i+1][j] , dp[i][j+1] ],key=len)
# print(*dp,sep="\n")

print(dp[s][t])

### FIXED CODE ###

S=input()
T=input()

s,t=len(S),len(T)
#DPテーブル作成
dp=[[0]*(t+1) for _ in range(s+1)]

for i in range(s):
    for j in range(t):
        if S[i] ==T[j]:
            dp[i+1][j+1] =dp[i][j] + 1
        else:
            dp[i+1][j+1] =  max([ dp[i+1][j] , dp[i][j+1] ])
# print(*dp,sep="\n")

res = ''
while s != 0 and t != 0:
    if dp[s][t] == dp[s-1][t]:
        s -= 1
    elif dp[s][t] == dp[s][t-1]:
        t -= 1
    else:
        s -= 1
        t -= 1
        res = S[s] + res

# print(dp[s][t])
print(res)
### BUGGY CODE ###

S = input()
N = int(input())
for i in range(N):
  query = input().split()
  if query[0] == "1":
    S = S[::-1]
  if query[0] == "2":
    if query[1] == "1":
      S = query[2] + S
    else:
      S = S + query[2]
print(S)

### FIXED CODE ###

import collections
S = collections.deque(list(input()))
N = int(input())
parity = True
for i in range(N):
  query = input().split()
  if query[0] == "1":
    if parity == True:
      parity = False
    else:
      parity = True
  if query[0] == "2":
    if parity:
      if query[1] == "1":
        S.appendleft(query[2])
      else:
        S.append(query[2])
    else:
      if query[1] == "1":
        S.append(query[2])
      else:
        S.appendleft(query[2])

Sstr = ""
if parity:
  for i in range(len(S)):
    Sstr = Sstr + S.popleft()
else:
  for i in range(len(S)):
    Sstr = Sstr + S.pop()
print(Sstr)
### BUGGY CODE ###

H, W = map(int, input().split()) # 横に2個
state = [[0 if a == '.' else 1 for a in list(input())] for _ in range(H)]

checked = [[False for _ in range(W+1)] for _ in range(H+1)]
qs = []
for h in range(H):
    for w in range(W):
        if state[h][w] == 1:
            qs.append([h, w])
            checked[h][w] = True
for h in range(H+1):
    checked[h][W] = True
for w in range(W+1):
    checked[H][w] = True

c = -1
while qs:
    qqs = []
    for h,w in qs:
        checked[h][w] = True
        if 0 < h and not checked[h-1][w]:
            qqs.append([h-1, w])
        if h < H-1 and not checked[h+1][w]:
            qqs.append([h+1, w])
        if 0 < w and not checked[h][w-1]:
            qqs.append([h, w-1])
        if w < W-1 and not checked[h][w+1]:
            qqs.append([h, w+1])
    c += 1
    qs = qqs

print(c)

### FIXED CODE ###

import sys
input = sys.stdin.readline

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = []
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.append(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        qq = []
        if len(q) == 0:
            break
        for hw in q:
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    qq.append(B*nh + nw)
                    checked[nh][nw] = True
        q = qq
        c += 1

    print(c)


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

import bisect
n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()

data = [None] * m
for i in range(m):
    data[i] = list(map(int, input().split()))
data.sort(key = lambda x : x[1])
data.reverse()


ans = 0
#data[][1] = value, data[][0] = card_num
for i in range(m):
    insert_index = bisect.bisect_left(a, data[i][1])
    count = min(data[i][0], insert_index)
    ans += count * data[i][1]
    a = a[count:]
print(ans + sum(a))


### FIXED CODE ###

import bisect
n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()

data = [None] * m
for i in range(m):
    data[i] = list(map(int, input().split()))
data.sort(key = lambda x : x[1])
data.reverse()


ans = 0
count = 0
pre_index = 0
#print(data)
#print(a)
#data[][1] = value, data[][0] = card_num
for i in range(m):
    insert_index = bisect.bisect_left(a, data[i][1])
    count = min(data[i][0], insert_index - pre_index)
    for j in range(pre_index, pre_index + count):
        if j >= n:
            break
        a[j] = 0
    ans += count * data[i][1]
    pre_index = pre_index + count
print(ans + sum(a))
### BUGGY CODE ###

n = int(input())
p_list = [i for i in map(int, input().split())]

ans = 0

for i in range(n):
    #i番目までのリストを作成
    check_part = p_list[:i+1]
    #その中で一番小さいかどうか
    if p_list[i] == min(check_part):
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
p_list = [i for i in map(int, input().split())]

ans = 0
min = n + 1

for i in range(n):
    if p_list[i] < min:
        min = p_list[i]
        ans += 1

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

n,k=map(int,input().split())
h=list(map(int,input().split()))+[0]*(k+10)
inf=float("inf")
dp=[(inf) for i in range(n+k+10)]
dp[0]=0
#print(dp)
def main():
  for i in range(n-1):
      #print(i)
      for j in range(k):
          dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
      #print(dp,i)
  print(dp[n-1])
main()

### FIXED CODE ###

def main():
  n,k=map(int,input().split())
  h=list(map(int,input().split()))+[0]*(k+10)
  dp=[(float("inf")) for i in range(n+k+10)]
  dp[0]=0
  for i in range(n-1):
    for j in range(k):
      dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
  return (dp[n-1])
print(main())
### BUGGY CODE ###

class LinkedList(object):
    
    def __init__(self):
        self.nodes = []

    def insert(self, node):
        self.nodes.insert(0, node)

    def delete(self, node):
        if node in self.nodes:
            self.nodes.remove(node)

    def deleteFirst(self):
        self.nodes.pop(0)

    def deleteLast(self):
        self.nodes.pop()

def run():
    n = int(input())
    linked_list = LinkedList()
    for _ in range(n):
        order = [x.strip() for x in input().split()]
        if order[0] == 'insert':
            linked_list.insert(int(order[1]))
        elif order[0] == 'delete':
            linked_list.delete(int(order[1]))
        elif order[0] == 'deleteFirst':
            linked_list.deleteFirst()
        elif order[0] == 'deleteLast':
            linked_list.deleteLast()
    print(' '.join([str(n) for n in linked_list.nodes]))
    
if __name__ == '__main__':
    run()


### FIXED CODE ###

from collections import deque

def run():
    n = int(input())
    dq = deque()
    for _ in range(n):
        order = input()
        if order[0] == 'i':
            dq.appendleft(order[7:])
        elif order[6] == ' ':
            key = order.split()[1]
            if not key in dq:
                continue
            for i in range(len(dq)):
                if dq[i] == key:
                    dq.remove(key)
                    break
        elif order[6] == 'F':
            dq.popleft()
        elif order[6] == 'L':
            dq.pop()

    print(' '.join(dq))

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

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

nD = S.count("D")
nC = S.count("C")
if nD < nC:
    S = S[::-1].replace("D","c").replace("C","d").upper()

D = [0]*(N+1)
cntM = [0]*(N+1)
sumM = [0]*(N+1)
ans = [0]*Q
for i,s in enumerate(S):
    D[i+1] = D[i]
    cntM[i+1] = cntM[i]
    sumM[i+1] = sumM[i]
    if s=="D":
        D[i+1] += 1
    elif s=="M":
        cntM[i+1] += 1
        sumM[i+1] += D[i]
    elif s=="C":
        for j,k in enumerate(K):
            ik = max(0,i-k+1)
            d = D[ik]
            ans[j] += (sumM[i]-sumM[ik]) - d*(cntM[i]-cntM[ik])
for out in ans:
    print(out)

### FIXED CODE ###

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

nD = S.count("D")
nC = S.count("C")
if nD < nC:
    S = S[::-1].replace("D","c").replace("C","d").upper()

D = [0]*(N+1)
cntM = [0]*(N+1)
sumM = [0]*(N+1)
ans = [0]*Q
for i,s in enumerate(S):
    D[i+1] = D[i]
    cntM[i+1] = cntM[i]
    sumM[i+1] = sumM[i]
    if s=="D":
        D[i+1] += 1
    elif s=="M":
        cntM[i+1] += 1
        sumM[i+1] += D[i]
    elif s=="C":
        for j,k in enumerate(K):
            ik = max(0,i-k+1)
            d = D[ik]
            ans[j] += (sumM[i]-sumM[ik]) - d*(cntM[i]-cntM[ik])
for out in ans:
    print(out)
### BUGGY CODE ###

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

def zenbu(m, B):
    if m == 1:
        return B[0]
    elif m == 2:
        return max(B[0],B[1])
    elif m == 3:
        return max(B[0],B[1],B[2])
    elif m%2 == 0: #偶数の場合
        temp = 0
        for i in range(m//2-1):
            temp += B[i*2]
        return max(temp+ max(B[m-2],B[m-1]), zenbu(m-2, B[:-2])+ B[m-1])
    else:#奇数の場合
        temp = 0
        for i in range((m-1)//2):
            temp += B[i*2]
        return max(temp, zenbu(m-2,B[:-2])+ B[m-1], zenbu(m-3,B[:-3])+ max(B[m-2],B[m-1]))

ans = zenbu(n,A)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
if N%2 == 0:
  dp = [[0]*2 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  for i in range(2,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3>=0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
  ans = max(dp[-2][0],dp[-1][1])
  print(ans)
#i個目を使ってj(0-2)回多く飛んでいる。
else: #N%2 == 1:
  dp = [[0]*3 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  dp[2][2] = A[2]
  dp[2][0] = A[0]+A[2]
  #print(dp)
  for i in range(3,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3 >= 0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
    if i-4 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],dp[i-4][0])+A[i]
    elif i-3 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],0)+A[i]
  #else:
  #  dp[i][2] = max(dp[i-2][2],0,0)+A[i]
  #print(dp[-1],dp[-2],dp[-3])

  ans = max(dp[-3][0],dp[-2][1],dp[-1][2])
  print(ans)
  exit()
### BUGGY CODE ###

inp = input().split(" ")
takahashi = int(inp[0])
aoki = int(inp[1])
K = int(inp[2])

i = 0
while i != K:
    if takahashi > 0 :
        takahashi = takahashi -1
    elif aoki > 0 :
        aoki = aoki-1
    i=i+1

print(str(takahashi) + " " + str(aoki))

### FIXED CODE ###

A,B,K = map(int,input().split(" "))
if A+B < K:print(0,0)
elif A > K:print(A-K,B)
elif A  <= K:print(0,A+B-K)
# Kenparさん、写経させていただきました。ありがとうございます。
# こんな解法があったなんて・・・
### BUGGY CODE ###

N, W = [int(i) for i in input().split()]
V = [[int(i) for i in input().split()] for j in range(N)]

DP = [0] * (W+1)
V.sort(key=lambda x: x[1])

for w, v in V:
    for i in range(W, -1, -1):
        if w > i:
            break
        DP[i] = max(DP[i], DP[i-w] + v)

print(DP[W])

### FIXED CODE ###

N, W = [int(i) for i in input().split()]
V = [[int(i) for i in input().split()] for j in range(N)]

DP = [0] * (W+1)
V.sort(key=lambda x: x[1])

for w, v in V:
    for i in range(W, -1, -1):
        if w > i:
            break
        DP[i] = max(DP[i], DP[i-w] + v)

print(DP[W])
### BUGGY CODE ###

import itertools

n = int(input())
red = [tuple(map(int, input().split())) for _ in range(n)]
blue = [tuple(map(int, input().split())) for _ in range(n)]

agg = [list() for _ in range(n)]
for i in range(n):
    c, d = blue[i]
    for j in range(n):
        a, b = red[j]
        if c > a and d > b:
            agg[i].append(j)

prod = itertools.product(*[x for x in agg if len(x) > 0])
res = 0
for p in prod:
    res = max(res, len(set(p)))

print(res)

### FIXED CODE ###

n = int(input())
red = sorted([tuple(map(int, input().split())) for _ in range(n)])
blue = sorted([tuple(map(int, input().split())) for _ in range(n)])

res = 0
for bx, by in blue:
    tmp_max = -1
    tmp_cnt = None
    for i, (rx, ry) in enumerate(red):
        if bx <= rx:
            break
        if tmp_max <= ry < by:
            tmp_max = ry
            tmp_cnt = i
    if tmp_cnt is not None:
        res += 1
        red.pop(tmp_cnt)

print(res)
### BUGGY CODE ###

import copy

n = int(input())
A = [int(input()) for _ in range(n)]

for i in range(n):
    tmp_list = copy.deepcopy(A)
    tmp_list.pop(i)
    print(max(tmp_list))


### FIXED CODE ###

import copy

n = int(input())
A = [int(input()) for _ in range(n)]

A_sorted = sorted(A, reverse=True)

for i in range(n):
    if A[i] == A_sorted[0]:
        print(A_sorted[1])
    else:
        print(A_sorted[0])
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    tmp = str(i)
    while len(tmp) < 3:
        tmp = '0' + tmp
    count = 0
    for k in S:
        if 3 <= count:
            break
        if k == tmp[count]:
            count += 1
    if count == 3:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    tmp = str(i)
    while len(tmp) < 3:
        tmp = '0' + tmp
    count = 0
    target = S
    for i in tmp:
        target = target.replace(i,'')
    for k in S:
        if 3 <= count:
            break
        if k == tmp[count]:
            count += 1
    if count == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())
result = []
for i in range(n-1):
    w = s[:i].count("W")
    e = s[i+1:].count("E")
    result.append(w+e)
print(min(result))

### FIXED CODE ###

n = int(input())
s = list(input())
result = [s[1:].count("E")]
for i in range(n-1):
    if s[i:i+2] == ["W","W"]:
        result.append(result[-1]+1)
    elif s[i:i+2] == ["E","E"]:
        result.append(result[-1]-1)
    else:
        continue
print(min(result))
### BUGGY CODE ###

import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm = ans = sum(s)
	for i in range(1,n-1):
		for party in sorted(itertools.combinations(s,i)):
			sm1 = sm - 2*sum(party)
			if sm1 < -ans: break
			ans = min(ans,abs(sm1))
			if ans == 0: break
	print ans

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)


K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(i,j,k)

print(ans)


### FIXED CODE ###

#test.py
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)


K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            if i==1 or j==1 or k ==1:
                ans += 1
            else:
                ans += gcd(i,j,k)

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

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

ans = 0

for i in range(n):
    a = p[:i + 1]
    
    if min(a) >= p[i]:
        ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0

c = p[0]

for i in range(n):
    #a = p[:i + 1]

    if c >= p[i]:
        c = p[i]
    if c >= p[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict

S = list(input())
N = len(S)

dic = defaultdict(int)
dic[0] = 1

ans = 0

tmp = 0
for i in range(N):
    s = S[N - 1 - i]
    tmp += int(s) * 10 ** i
    ans += dic[tmp % 2019]
    dic[tmp % 2019] += 1

print (ans)

# print (dic)

### FIXED CODE ###

from collections import defaultdict

S = list(input())
N = len(S)

dic = defaultdict(int)
dic[0] = 1

ans = 0

tmp = 0
for i in range(N):
    s = S[N - 1 - i]
    tmp += int(s) * pow(10, i, 2019)
    ans += dic[tmp % 2019]
    dic[tmp % 2019] += 1

print (ans)

# print (dic)