Harryxun/stf_run huggingface dataset:
n, q = map(int, input().split())
s = input()
ac_list = [0]*len(s)
i = 0
'''while True:
    ac_index = s[i:].find("AC")
    if ac_index == -1:
        break
    else:
        ac_list[ac_index+i] = 1
        i = ac_index + i + 2'''

for i in range(len(s-1)):
    if s[i] == 'A' and s[i+1] == 'C':
        ac_list[i] = 1
        
for _ in range(q):
    lr = tuple(map(int, input().split()))
    print(sum(ac_list[lr[0]-1:lr[1]-1]))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ac_list = [0]*len(s)

'''while True:
    ac_index = s[i:].find("AC")
    if ac_index == -1:
        break
    else:
        ac_list[ac_index+i] = 1
        i = ac_index + i + 2'''

for i in range(len(s)-1):
    if s[i:i+2] == 'AC':
        ac_list[i+1] = ac_list[i] + 1
    else:
        ac_list[i+1] = ac_list[i]
# print(ac_list)
for _ in range(q):
    l, r = map(int, input().split())
    print(ac_list[r-1] - ac_list[l-1])
N, K = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7
result = 0
count = [0] * N
for a in A:
    count[a-1] += 1
    result += K * sum(count[a:])
    result %= mod

kn = 0
total = sum(count) % mod
for i in range(N):
    total -= count[i]
    kn += total
    kn %= mod

result += kn * K*(K-1)//2
result %= 10**9 + 7

print(result)


### FIXED CODE ###

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

mod = 10**9 + 7
result = 0
count = [0] * 2001

# リスト内での繰り返し
for a in A:
    count[a-1] += 1
    result += K * sum(count[a:])
    result %= mod

kn = 0
# 前のループに存在する自分より大きい数
count = [i for i in count if i != 0]
total = sum(count) % mod

for i in count:
    total -= i
    kn += total * i
    kn %= mod

result += kn * K*(K-1)//2
result %= 10**9 + 7

print(result)
import heapq

X,Y,Z,K = map(int, input().split())
A = map(int, input().split())
B = map(int, input().split())
C = map(int, input().split())

A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)

h = []

heapq.heappush(h, (A[0]+B[0]+C[0], 0,0,0))

result = []

for _ in range(K):
	value, i,j,k = h.heappop()
    result.append(value)
    if i < X-1:
    	heapq.heappush(h, (A[i+1]+B[j]+C[k],i,j,k))
    if j < Y-1 and i == 0:
      	heapq.heappush(h, (A[i]+B[j+1]+C[k],i,j+1,k))
    if k < Z-1 and i == 0 and j == 0:
      	heapq.heappush(h, (A[i]+B[j]+C[k+1],i,j,k+1))
        
for v in result:
	print(v)

### FIXED CODE ###

import heapq

X,Y,Z,K = map(int, input().split())
A = [int(x) for x in  input().split()]
B = [int(x) for x in  input().split()]
C = [int(x) for x in  input().split()]

A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)

h = []

heapq.heappush(h, (-A[0]-B[0]-C[0], 0,0,0))

result = []
used = set()

for _ in range(K):
    value, i,j,k = heapq.heappop(h)
    result.append(-value)
    if i < X-1 and (i+1,j,k) not in used:
        heapq.heappush(h, (-A[i+1]-B[j]-C[k],i+1,j,k))
        used.add((i+1,j,k))
    if j < Y-1 and (i,j+1,k) not in used:
        heapq.heappush(h, (-A[i]-B[j+1]-C[k],i,j+1,k))
        used.add((i,j+1,k))
    if k < Z-1 and (i,j,k+1) not in used:
        heapq.heappush(h, (-A[i]-B[j]-C[k+1],i,j,k+1))
        used.add((i,j,k+1))
        
for v in result:
    print(v)
n=int(input())
d=[int(input()) for i in range(n)]

sum=0
for i in range(n-1):
    for l in range(i+1,n):
        sum+=d[i]*d[l]
print(sum)


    


### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
 
sum=0
for i in range(n-1):
    for l in range(i+1,n):
        sum+=d[i]*d[l]
print(sum)
import sys
from pprint import pprint

def warshall_floyd(d, n):
    # pprint(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

def solve(h, w, s):
    
    edges = {}
    n_node = 0

    nodes = [] 
    # pprint(nodes)
    for y in range(h):
        nodes.append([])
        for x in range(w):
            nodes[y].append(n_node)
            n_node += 1
    edges = [[float("inf") for i in range(n_node)] for j in range(n_node)]
    # pprint(nodes)
    for y in range(h):
        for x in range(w):
            for dx, dy in ((1,0), (-1,0), (0,1), (0,-1)):
                if s[y][x] != ".":
                    continue
                if 0 <= y+dy < h and 0 <= x+dx < w and s[y+dy][x+dx] == ".":
                    edges[nodes[y][x]][nodes[y+dy][x+dx]] = 1
    for i in range(n_node):
        edges[i][i] = 0
    
    dist = warshall_floyd(edges, n_node)
    # pprint(dist)
    ans = -1
    for y in range(n_node):
        for x in range(n_node):
            if dist[y][x] < float("inf"):
                ans = max(ans, dist[y][x])
    print(ans)


if __name__ == '__main__':
    h, w = map(int, sys.stdin.readline().strip().split(" "))
    s = []
    for i in range(w):
        s.append(list(sys.stdin.readline().strip()))
    # debug
    # pprint(s)
    solve(h, w, s)

### FIXED CODE ###

import sys
from pprint import pprint

def warshall_floyd(d, n):
    # pprint(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

def solve(h, w, s):
    
    n_node = 0
    nodes = [] 
    # pprint(nodes)
    for y in range(h):
        nodes.append([])
        for x in range(w):
            nodes[y].append(n_node)
            n_node += 1
    edges = [[float("inf") for i in range(n_node)] for j in range(n_node)]
    # pprint(nodes)
    for y in range(h):
        for x in range(w):
            if s[y][x] != ".":
                continue
            for dx, dy in ((1,0), (-1,0), (0,1), (0,-1)):
                if 0 <= y+dy < h and 0 <= x+dx < w and s[y+dy][x+dx] == ".":
                    edges[nodes[y][x]][nodes[y+dy][x+dx]] = 1
    for i in range(n_node):
        edges[i][i] = 0
    
    dist = warshall_floyd(edges, n_node)
    # pprint(dist)
    ans = -1
    for y in range(n_node):
        for x in range(n_node):
            if dist[y][x] < float("inf"):
                ans = max(ans, dist[y][x])
    print(ans)


if __name__ == '__main__':
    h, w = map(int, sys.stdin.readline().strip().split(" "))
    s = []
    for i in range(h):
        s.append(list(sys.stdin.readline().strip()))
    # debug
    # pprint(s)
    solve(h, w, s)
a, b, c =  = map(int,input().split())
print('YES') if a == b == c else print('NO')

### FIXED CODE ###

a, b, c = map(int,input().split())
print('YES') if b - a == c - b else print('NO')
import numpy as np
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = np.zeros((n+1, W+1), dtype=int)

for i in range(n):
    dp[i+1][:wv[i][0]] = dp[i][:wv[i][0]]
    dp[i+1][wv[i][0]:] = np.maximum(dp[i][:-wv[i][0]] + wv[i][1], dp[i][wv[i][0]:])
print(dp[n][W])

### FIXED CODE ###

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

inf = 10 ** 10
dp = [[inf] * (10**5+3) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    weight, value = map(int, input().split())
    for j in range(10**5 + 3):
        if j - value >= 0:
            dp[i+1][j] = min(
                dp[i][j - value] + weight,
                dp[i][j]
            )
        else:
            dp[i+1][j] = dp[i][j]
for i in reversed(range(10**5+3)):
    if dp[n][i] <= w:
        print(i)
        break
x = map(int, input())

def is_sosu(num):
  st = 2
  if num % st == 0:
    print(num)
  else:
    st += 1
    if num == st:
      is_sosu(num+1)

is_sosu(x)

### FIXED CODE ###

x = input()

def is_sosu(num):
  st = 2
  while True:
    if num % st == 0:
      break
    st += 1
  if st == num:
    print(num)
    return
  is_sosu(num+1)

is_sosu(int(x))
def Z_algo(S):
    n = len(S)
    z = [0]*n
    L = 0
    R = 0
    for i in range(1, n):
        if i > R:
            L = i
            R = i
            while (R < n):
                if s[R - L] == s[R]:
                    z[i] = R - L + 1
                else:
                    break
                R += 1
        else:
            k = i - L
            # print(k)
            if z[k] < R - i + 1:
                z[i] = z[k]
            else:
                L = i
                while (R < n):
                    if s[R - L] == s[R]:
                        z[i] = R - L + 1
                    else:
                        break
                    R += 1
    return z
  
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP
  
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 998244353
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,S = inputIL()
l = inputIL()

dp = [[[0,0] for s in range(S+2)] for r in range(N+1)]

for r in range(N):
  for s in range(S):
    if s == 0:
      dp[r][s] = [1,r+2]
    if r == 0:
      if s == l[r]:
        dp[r][s] = [1,1]
      else:
        dp[r][s] = [0,0]
    else:
      dp[r][s] = [dp[r-1][s][0] + dp[r-1][s][1] + dp[r-1][s-l[r]][1],dp[r-1][s][1]+dp[r-1][s-l[r]][1]]


print(dp[N-1][S][0])


### FIXED CODE ###

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

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

"""
dpなのはそうだろう
普通に行けば、ナップサックdpでいける
S以下のみしか保持しなくていい

始点を保持してしまうと、Sになった時に…？
始点より左にあるやつの個数の和を記録しておけばいい！

連続してなくていいから
"""

dp = [0] * (S+1)
ans = 0
mod = 998244353

for i in range(N):

    ndp = []
    for ll in dp:
        ndp.append(ll)

    if A[i] <= S:
        ndp[A[i]] += i+1
        ndp[A[i]] %= mod

    for j in range(S):

        if j+A[i] <= S:
            ndp[j+A[i]] += dp[j]
            ndp[j+A[i]] %= mod

    ans += ndp[S]
    ans %= mod

    dp = ndp

    #print (dp)

    
print (ans)
# -*- coding: utf-8 -*-
n,k = map(int, input().split())
o = {}

for _ in range(n):
    t,d = map(int, input().split())
    if t not in o:
        o[t] = []
    o[t].append(d)

tl = list(o.keys())
tl.sort(reverse=True,key=lambda x:o[x])
# print(tl)
for t in tl:
    o[t].sort(reverse=True)
# print(o)
res = -1
sel = {}
for t in tl:
    if len(o[t])<=k:
        sel[t] = len(o[t])
        k -= sel[t]
    else:
        sel[t] = k
        k = 0
    if k==0:
        break

# print(sel)

def calc(sel):
    res = 0
    cnt = 0
    for t in sel:
        if sel[t]>0:
            cnt += 1
        for i in range(sel[t]):
            res += o[t][i]
    return res+cnt*cnt

idx = None
for i in range(len(tl)-1):
    if tl[i+1] not in sel:
        idx = i
        break

if idx is None:
    print(calc(sel))
    exit()

# print(idx)

res = calc(sel)
for i in range(idx+1,len(tl)):
    while sel[tl[idx]]==1:
        idx -= 1

    sel[tl[idx]] -= 1
    sel[i] = 1
    res2 = res + o[i][0] - o[tl[idx]][-1]
    res = max(res, res2)
    # res = max(res, calc(sel))

print(res)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque
n,k = map(int, input().split())
td = []

for _ in range(n):
    t,d = map(int, input().split())
    td.append((t,d))

td.sort(reverse=True, key=lambda x:x[1])

used = set()
q = []
res = 0
kind = 0
for i in range(k):
    t,d = td[i]
    if t not in used:
        kind += 1
        used.add(t)
    else:
        q.append((t,d))
    res += d
res += kind**2
q = deque(sorted(q, key=lambda x:x[1]))

tmp = res
for i in range(k,n):
    if len(q)==0:
        break
    t2,d2 = td[i]
    if t2 in used:
        continue
    used.add(t2)
    t,d = q.popleft()

    r = tmp - d + d2
    r -= kind**2
    kind += 1
    r += kind**2
    res = max(res, r)
    tmp = r

print(res)
s = sorted(list(input()))
t = sorted(list(input()), reverse = 1)
for i in range(len(s)):
    if s[i] < t[i]:
        print("Yes")
        break
else:
    if len(s) < len(t):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

s = sorted(list(input()))
t = sorted(list(input()), reverse = 1)
if s < t:
    print("Yes")
else:
    print("No")
S = [int(input()) for _ in range(5)]
l=[]
m=10
for i in range(5):
    if (S[i]%10)<m and S[i]%10!=0:
        m=S[i]%10
        a=S[i]
        j=i
if m==10:
    a=S[0]        
for i in range(5):
    if  i!=j:
        if S[i]%10!=0:
            S[i]+=10-(S[i]%10)
        l.append(S[i])
l.append(a)
print(sum(l))

### FIXED CODE ###

S = [int(input()) for _ in range(5)]
l=[]
m=10
for i in range(5):
    if (S[i]%10)<m and S[i]%10!=0:
        m=S[i]%10
        a=S[i]
        j=i
if m==10:
    a=S[0]  
    j=0      
for i in range(5):
    if  i!=j:
        if S[i]%10!=0:
            S[i]+=10-(S[i]%10)
        l.append(S[i])
l.append(a)
print(sum(l))
l = map(int, raw_input().split())
set_1974 = (1,9,7,4)

output_word = "YES"
for i in l:
  if i not in set_1974:
    output_word = "NO"
print(output_word)

### FIXED CODE ###

l = set([int(e) for e in input().split()])
set_1974 = set([1,9,7,4])

if l == set_1974:
  print("YES")
else:
  print("NO")
SHEEP = True
WOLF = False


def print_tree(tree):
    print(''.join(['S' if e else 'W' for e in tree]))


def calc_next_animal(tree, cur_pos):
    if answer[cur_pos]:
        if tree[cur_pos] == SHEEP:
            return tree[cur_pos - 1]
        else:
            return not tree[cur_pos - 1]
    else:
        if tree[cur_pos] == SHEEP:
            return not tree[cur_pos - 1]
        else:
            return tree[cur_pos - 1]


def calc_prev_animal(tree, cur_pos):
    if answer[cur_pos]:
        if tree[cur_pos] == SHEEP:
            return tree[cur_pos + 1]
        else:
            return not tree[cur_pos + 1]
    else:
        if tree[cur_pos] == SHEEP:
            return not tree[cur_pos + 1]
        else:
            return tree[cur_pos + 1]


def wfs(tree, cur_pos, N):
    tree[cur_pos + 1] = calc_next_animal(tree, cur_pos)
    cur_pos += 1
    if cur_pos == N - 1:
        return tree[0] == calc_next_animal(tree, cur_pos) and tree[cur_pos] == calc_prev_animal(tree, 0)
    else:
        return wfs(tree, cur_pos, N)


if __name__ == '__main__':
    N = int(input())
    answer = [True if i == 'o' else False for i in input().rstrip()]
    aa = [[WOLF, WOLF]
        , [WOLF, SHEEP]
        , [SHEEP, SHEEP]
        , [SHEEP, WOLF]]
    super_list = [0] * int(2E5)
    for a in aa:
        super_list[:2] = a
        if wfs(super_list, 1, N):
            print_tree(super_list[:N])
            break
    else:
        print(-1)

### FIXED CODE ###

if __name__ == '__main__':
    N = int(input().rstrip())
    print(800 * N - 200 * (N // 15))
n = input()
 
A = list(map(int, input().split())
 
counts = 0
while all(a%2==0 for a in A):
	A = [a/2 for a in A]
    counts += 1
print(counts)

### FIXED CODE ###

n = input()
 
A = list(map(int, input().split()))
 
counts = 0
while all(a%2==0 for a in A):
  A = [a/2 for a in A]
  counts += 1
print(counts)
a=int(input())
cnt=0
for i in range(math.inf):
  if a%2==0:
    cnt+=1
    a/=2
  else:
    print(cnt)
 


### FIXED CODE ###

n=int(input())
for i in range(99):
  if 2**i <= n:
    continue
  else:
    print(2**(i-1))
    break
n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
c=b[n//2]
d=b[n//2+1]
if c==d:
  for i in range(n):print(c)
else:
  for i in range(n):
    if a[i]<=c:print(d)
    else:print(c)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
l=b[:n//2]
u=b[n//2:]
for i in a:
  if i <= l[-1]:
    print(u[0])
  else:
    print(l[-1])
h,n=map(int,input().split())
arr=list(map(int,input().split()))
if h<=sum(arr):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

h,n=map(int,input().split())
arr=list(map(int,input().split()))
if h<=sum(arr):
  print("Yes")
else:
  print("No")
S = input()

al_list = [chr(i) for i in range(97, 97+26)]
s_list = []
Flag = True

for al in S:
    s_list.append(al)

if s_list == al_list:
    print('None')
else:
    print(min(list(set(al_list) - set(s_list))))

### FIXED CODE ###

S = input()

al_list = [chr(i) for i in range(97, 97+26)]
s_list = []
Flag = True

for al in S:
    s_list.append(al)

if set(s_list) == set(al_list):
    print('None')
else:
    print(min(list(set(al_list) - set(s_list))))
a, b = map(int, input().split())
if ((a+b)/2)is_integer():
  print((a+b)//2)
  exit()
print("IMPOSSIBLE")

### FIXED CODE ###

a, b = map(int, input().split())
if ((a+b)/2).is_integer():
  print((a+b)//2)
  exit()
print("IMPOSSIBLE")
import numpy as np
n, ma, mb = map(int, input().split())

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

INF = 5000
dp = np.full((n + 1, 444, 444), INF, dtype=np.int)

dp[0][0][0] = 0

for i in range(n):
    for j in range(401):
        for k in range(401):
            a, b, c = item[i]
            dp[i + 1][j + a][k + b] = min(dp[i + 1]
                                          [j + a][k + b], dp[i][j][k] + c)
            dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])

ans = INF
for i in range(1, 401):
    for j in range(1, 401):  # i : j == ma : mb
        if ma * j == i * mb:
            ans = min(ans, dp[n][i][j])
print(ans if ans != INF else -1)


### FIXED CODE ###

n, ma, mb = map(int, input().split())

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

INF = 5000
dp = [[INF] * 444 for _ in range(444)]


dp[0][0] = 0

for i in range(n):
    next = [[INF] * 444 for _ in range(444)]
    for j in range(401):
        for k in range(401):
            a, b, c = item[i]
            next[j + a][k + b] = min(next
                                     [j + a][k + b], dp[j][k] + c)
            next[j][k] = min(next[j][k], dp[j][k])
    dp = next

ans = INF
for i in range(1, 401):
    for j in range(1, 401):  # i : j == ma : mb
        if ma * j == i * mb:
            ans = min(ans, dp[i][j])
print(ans if ans != INF else -1)
N = int(input())
A = list(map(int, input().split()))
chinpo = 0

for i in range(N-2):

    if A[i] > A[i+1]:
        A[i] -= 1
        if A[i+1] >= A[i]:
            chinpo += 1
    else:
        chinpo += 1

if chinpo == N-1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a,b,c = map(int,input().split())

X = b + c - a
if X >= 0:
    print(X)
else:
    print(0)
n=int(input())
num=[0]
ans=0
count=0
k=1
for i in range(n):
    a=int(input())
    num.append(a)
 
 for i in range(n+1):
    k=num[k]
    count+=1
    if k==2:
        ans=1
        break
if ans==1:
    print(count)
else:
    print("-1")
# coding: utf-8

### FIXED CODE ###

n=int(input())
num=[0]
ans=0
count=0
k=1
for i in range(n):
    a=int(input())
    num.append(a)

for i in range(n+1):
    k=num[k]
    count+=1
    if k==2:
        ans=1
        break
if ans==1:
    print(count)
else:
    print("-1")
def start(l):
    for i in range(1, l-1):
        if S_list[i] == "A":
            return i + 1


def finish(l):
    for i in range(1, l-1):
        if S_list[l - i] == "Z":
            return l - i + 1


S_list = list(input())
l = len(S_list)
print(finish(l) - start(l) + 1)

### FIXED CODE ###

x = int(input())
if x < 1200:
    print('ABC')
else:
    print('ARC')
N,K=list(map(int,input().split()))
h=[int(input()) for i in range(N)]
 
h.sort()
 
m="a"
for i in range(N-K+1):
	if m=="a" or m>h[i+K-1]-h[i]: m=h[i+K-1]-h[i]
 
print(m)

### FIXED CODE ###

d = int(input())
if(d==25):
    print("Christmas")
elif(d==24):
    print("Christmas Eve")
elif(d==23):
    print("Christmas Eve Eve")
else:
    print("Christmas Eve Eve Eve")
while True:
  n = int(input())
  if not n:
    break

  start = int(input()) - 1 #開始の位置
  goal = int(input()) - 1  #あたりの位置
  d = int(input())
  
  nums = [[i for i in range(n)]] #各段での数字の並び
  bars = [] #横棒リスト
  
  for i in range(d):
    s = input()
    bars.append(s)
    new = nums[-1][:]
    for j in range(n - 1):
      if s[j] == "1": #横棒があれば入れ替え
        new[j], new[j + 1] = new[j + 1], new[j]

    nums.append(new)
  
  to_goal = nums[-1][goal] #あたりにたどり着くスタートの番号

  for i, status in enumerate(nums):
    to_goal_ind = status.index(to_goal) #to_goalの位置
    start_ind = status.index(start)     #startの位置
    ind1, ind2 = min(to_goal_ind, start_ind), max(to_goal_ind, start_ind)

    if ind2 - ind1 == 1:  #隣あっていた場合
      if bars[i][ind1] == "0" and (ind2 == n - 1 or bars[i][ind2] == "0"):  #隣り合う横棒がなければ出力
        print(i + 1, ind1 + 1)
        break
  else:
    print(1)



### FIXED CODE ###

while True:
  n = int(input())
  if not n:
    break

  start = int(input()) - 1 #開始の位置
  goal = int(input()) - 1  #あたりの位置
  d = int(input())
  
  nums = [[i for i in range(n)]] #各段での数字の並び
  bars = [] #横棒リスト
  
  for i in range(d):
    s = input()
    bars.append(s)
    new = nums[-1][:]

    for j in range(n - 1):
      if s[j] == "1": #横棒があれば入れ替え
        new[j], new[j + 1] = new[j + 1], new[j]

    nums.append(new)
    
  to_goal = nums[-1][goal] #あたりにたどり着く初期位置
  
  if to_goal == start: #元からあたりにたどり着く場合
    print(0)

  else: #各段について、to_goalとスタートが隣り合うかチェック
    for i, status in enumerate(nums[1:]):
      to_goal_ind = status.index(to_goal) #to_goalの位置
      start_ind = status.index(start)     #startの位置
      ind1, ind2 = min(to_goal_ind, start_ind), max(to_goal_ind, start_ind)
  
      if (ind2 - ind1 == 1                               #隣り合っていて、 
          and bars[i][ind1] == "0"                       #該当位置と
          and (ind1 == 0 or bars[i][ind1 - 1] == "0")    #左と
          and (ind2 == n - 1 or bars[i][ind2] == "0")):  #右に、辺がなければ出力
          print(i + 1, ind1 + 1)
          break
    else:
      print(1)