Harryxun/stf_run huggingface dataset:
from collections import deque
n, k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7

p = []
m = []
for i in a:
    if i >= 0:p.append(i)
    elif i < 0:m.append(i)

p.sort(reverse=True)
m.sort()
res = 1

if len(p) == 0 and k % 2 == 1:
    for i in range(k):
        res = (res * m[-(i + 1)]) %mod
    print(res)

else:
    p_ind = 0
    m_ind = 0
    while k:
        
        temp = p[p_ind] * p[p_ind + 1] if p_ind + 1 < len(p) else p[p_ind]
        temp1 = m[m_ind] * m[m_ind + 1] if m_ind + 1 < len(m) else -1
        if temp > temp1 or k == 1:
            res = (res * p[p_ind]) %mod
            p_ind += 1
            k -= 1
        else:
            res = (res * temp1) %mod
            m_ind += 2
            k -= 2
    print(res)

### FIXED CODE ###

from collections import deque
n, k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7

p = []
m = []
for i in a:
    if i >= 0:p.append(i)
    elif i < 0:m.append(i)

p.sort(reverse=True)
m.sort()
res = 1
if n == k:
    for i in a:
        res = (res * i) %mod
    print(res)
    exit()
    
if len(p) == 0 and k % 2 == 1:
    for i in range(k):
        res = (res * m[-(i + 1)]) %mod
    print(res)

else:
    p_ind = 0
    m_ind = 0
    while k:
        if k == 1:
            res = (res * p[p_ind]) % mod
            break
        
        temp = p[p_ind] * p[p_ind + 1] if p_ind + 1 < len(p) else 0
        temp1 = m[m_ind] * m[m_ind + 1] if m_ind + 1 < len(m) else 0
        if temp > temp1:
            res = (res * p[p_ind]) %mod
            p_ind += 1
            k -= 1
        else:
            res = (res * temp1) %mod
            m_ind += 2
            k -= 2
    print(res)
print(*sorted.map(int, input().split())


### FIXED CODE ###

#print(*sorted(map(int, input().split())))

print(*sorted(map(int, input().split())))
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import collections
N = int(input())
A = list(map(int, input().split()))
cA = collections.Counter(A)

LIM = 10 ** 6 + 10
# LIM = 25

A.sort()
dp = [1] * LIM

for i in set(A):
    s = i * 2
    while s <= LIM:
        dp[s] = 0
        s += i

ans = 0
# print(dp)
for a in A:
    # print("{} {}".format(dp[a], cA[a]))
    if dp[a] and cA[a] == 1:
        # print(a)
        ans += 1
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import collections
N = int(input())
A = list(map(int, input().split()))
cA = collections.Counter(A)

LIM = 10 ** 6 + 1
# LIM = 25

A.sort()
dp = [1] * LIM

for i in set(A):
    s = i * 2
    while s < LIM:
        dp[s] = 0
        s += i

ans = 0
# print(dp)
for a in A:
    # print("{} {}".format(dp[a], cA[a]))
    if dp[a] and cA[a] == 1:
        # print(a)
        ans += 1
print(ans)
n = int(input())
result = 0
for i in range(2,n+1):
  total = 0
  for j in range(i):
    if (i%j == 0):
      tatal += 1
  if(total == 8):
    result += 1
print(result)

### FIXED CODE ###

n = int(input())
result = 0
for i in range(1,n+1,2):
  total = 0
  for j in range(1,i+1):
    if (i%j == 0):
      total += 1
  if(total == 8):
    result += 1
    #print(i,j)
print(result)
import sys
sys.setrecursionlimit(100000)

N = int(input())

min = float('inf')

def dfs(x, y, count):
    global min

    if x<0 or y<0 or (((x+1)*(y+1))>N):
        return

    if (x+1)*(y+1)==N:
        
        if min > count:
            min = count
            return
        return

    dfs(x+1, y, count+1)
    dfs(x, y+1, count+1)

    return

dfs(0,0,0)

while 

print(min)

### FIXED CODE ###

N = int(input())

min = float('inf')

times = int(N**0.5)

for i in range(1, times+1, 1):

    if N%i==0:
        j = N//i
    else:
        continue
    temp = i+j-2
    if min > temp:
        min = temp

print(min)
m = {"yotta":24, "zetta":21, "exa":18, "peta":15, "tera":12, "giga":9, "mega":6, "kilo":3, "hecto":2, "deca":1, "deci":-1, "centi":-2, "milli":-3, "micro":-6, "nano":-9, "pico":-12, "femto":-15, "ato":-18, "zepto":-21, "yocto":-24}
for _ in range(int(input())):
    v, *b = input().split()
    if len(b) == 2:
        k, b = b[0], b[1]
        a = m[k]
    else:b = b[0];a = 0
    s = 0
    for i in range(len(v)):
        if v[i] in "123456789":
            s = len(v) - i
            if "." in v[i + 1:]:s -= 1
            break
    x = float(v)
    while x < 1:
        x *= 10
        a -= 1
    while x >= 10:
        x /= 10
        a += 1
    while 1:
        if v[0] in "123456789":
            if len(v) != 1:
                v = v[0] + "." + v[1:]
                if "." in v[2:]:
                    a = 2 + v[2:].index(".")


### FIXED CODE ###

m = {"yotta":24, "zetta":21, "exa":18, "peta":15, "tera":12, "giga":9, "mega":6, "kilo":3, "hecto":2, "deca":1, "deci":-1, "centi":-2, "milli":-3, "micro":-6, "nano":-9, "pico":-12, "femto":-15, "ato":-18, "zepto":-21, "yocto":-24}
for _ in range(int(input())):
    v, *b = input().split()
    if len(b) == 2:
        k, b = b[0], b[1]
        a = m[k]
    else:b = b[0];a = 0
    s = 0
    for i in range(len(v)):
        if v[i] in "123456789":
            if i != 0:
                a -= i - 1
                if i != len(v) - 1:v = v[i] + "." + v[i + 1:]
                else:v = v[i]
            else:
                try:
                    j = v[i:].index(".")
                    a += j - 1
                    v = v[0] + "." + v[1:j] + v[j + 1:]
                except:
                    a += len(v) - 1
                    v = v[0] + "." + v[1:]
            break
    print("{} * 10^{} {}".format(v, a, b))
while 1:
 x, y = map(int, raw_input().split())
 if x <= y:
    print '%d %d' %(x,y)
 if y < x:
    print '%d %d' %(y,x)
 if x == y == 0:
    break

### FIXED CODE ###

while 1:
   x, y = map(int, raw_input().split())
   if x == 0 and y == 0:
      break
   elif x > y:
      print '%s %s' % (y,x)
   else:
      print '%s %s' % (x,y)
a=int(input(a))
b=int(input(b))

if (a*b)%2 ==1:
	print('Odd')
else:
	print('Even')

### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2 ==0:
  print('Even')
else:
  print('Odd')
import numpy as np
N = int(input())
# div=np.zeros(N+1,np.int64)
count=0
for n in range(1 ,N+1):
    for m in range(n,N+1,n):
        count+=m
print(count)


### FIXED CODE ###

from  numba import njit

@njit
def main(N):
    count=0
    for n in range(1 ,N+1):
        for m in range(n,N+1,n):
            count+=m
    print(count)
if __name__ == "__main__":
    N = int(input())
    main(N)
import math
print(math.pi * 2 * R)

### FIXED CODE ###

import math
a = int(input())
print(2 * a * math.pi)
n,k,x = (int(x) for x in input().split())
C = []
A = []
for i in range(n):
    list = [int(i) for i in input().split()]
    C.append(list[0])
    A.append(list[1:])
case = [0]*(2**n)
chk = []
for i in range(2**n):
    chk.append([0]*m)

for i in range(2 ** n):
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            case[i] += C[j]
            for l in range(m):
                chk[i][l] += A[j][l]

ans = []
flag = [True]*(2**n)
for i in range(2**n):
    for j in range(m):
        if chk[i][j]<x:
            flag[i] = False
    if flag[i]:
        ans.append(case[i])

if ans==[]:
    print(-1)
else:
    print(min(ans))

### FIXED CODE ###

n,m,x = (int(x) for x in input().split())
C = []
A = []
for i in range(n):
    list = [int(i) for i in input().split()]
    C.append(list[0])
    A.append(list[1:])
i = 0
case = [0]*(2**n)
chk = []
for i in range(2**n):
    chk.append([0]*m)
i = 0
for i in range(2 ** n):
    for j in range(n):
        if ((i >> j) & 1):
            case[i] += C[j]
            for l in range(m):
                chk[i][l] += A[j][l]
i = 0
j = 0
ans = []
flag = [True]*(2**n)
for i in range(2**n):
    for j in range(m):
        if chk[i][j]<x:
            flag[i] = False
    if flag[i]:
        ans.append(case[i])

if ans==[]:
    print(-1)
else:
    print(min(ans))
n=int(input())
a=list(map(int,input().split()))
left=[0]
for i in a:
  left.append(max(left[-1],i))
right=[0]
for i in reversed(a):
  right.append(max(right[-1],i))
right.reverse()
for i in range(n):
  print(max(left[i],right[n-i]))

### FIXED CODE ###

n=int(input())
a=[int(input())for _ in range(n)]
left=[0]
for i in a:
  left.append(max(left[-1],i))
right=[0]
for i in reversed(a):
  right.append(max(right[-1],i))
right.reverse()
for i in range(n):
  print(max(left[i],right[i+1]))
s = input()

if s[0]=="W":
    l = [1]
else:
    l = [0,1]

for i in range(1,len(s)):
    if s[i]==s[i-1]:
        l[-1]+=1
    else:
        l.append(1)

rightw = sum(l[2::2])

ans = 0

for i in range(len(s)//2):
    ans += l[2*i+1]*rightw
    rightw -= l[2*i+2]

print(ans)

### FIXED CODE ###

s = input()

if s[0]=="W":
    l = [1]
else:
    l = [0,1]

for i in range(1,len(s)):
    if s[i]==s[i-1]:
        l[-1]+=1
    else:
        l.append(1)

rightw = sum(l[2::2])

ans = 0

for i in range(len(l)//2):
    ans += l[2*i+1]*rightw
    if i!=len(l)//2-1:
        rightw -= l[2*i+2]

print(ans)
from math import factorial
n,k = map(int, input().split())
mod = 10**9+7
# a = comb(n, r)
for i in range(1,k+1):
    if n-k+1 < i:
        print(0)
    else:
        a = factorial(n-k+1) //factorial(i) //factorial(n-k+1 - i)
        print((a*(i**(k-i)))%mod)

### FIXED CODE ###

s = str(input())
s1 = set(s)
s2 = list(s)
cnt = 0
if len(s1) != 2:
    print("No")
else:
    for i in range(1,len(s2)):
        if s[0] == s[i]:
            cnt += 1
    if cnt == 1:
        print("Yes")
    else:
        print("No")
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

#define Whats(x) cout<<#x<<" is "<<(x)<<endl
#define Divhim() cout<<">>>>>>>>>>>>>>>"<<endl
#define Divher() cout<<"<<<<<<<<<<<<<<<"<<endl
#define Oops() cout<<"!!!!!!!!!!!!!!!"<<endl

template<typename T> bool GetMin(T &a,T b)
{
	return ((a<=b)?false:(a=b,true));
}

template<typename T> bool GetMax(T &a,T b)
{
	return ((a>=b)?false:(a=b,true));
}

/*
	 -<Unlimited Blade Works>-
 */

#define LL long long

const int N=1e6+10;
const int H=1e5+10;
const LL INF=0x3f3f3f3f3f3f3f3f;

struct Heap
{

	priority_queue<LL,vector<LL>,greater<LL> > P,Q;

	void Push(LL x)
	{
		P.push(x);
	}

	void Del(LL x)
	{
		Q.push(x);
	}

	LL Top()
	{
		while(!Q.empty()&&P.top()==Q.top())
		{
			P.pop();
			Q.pop();
		}
		return P.empty()?INF:P.top();
	}

};

LL tr0[H<<2],tr1[H<<2];
Heap hp0[H<<2],hp1[H<<2];

void Insert(int p,LL w0,LL w1,int o=1,int l=1,int r=H)
{
	if(l==r)
	{
		hp0[o].Push(w0);
		hp1[o].Push(w1);
		GetMin(tr0[o],w0);
		GetMin(tr1[o],w1);
		return;
	}
	int mid=(l+r)>>1,lc=o<<1,rc=lc^1;
	if(p<=mid)
		Insert(p,w0,w1,lc,l,mid);
	else
		Insert(p,w0,w1,rc,mid+1,r);
	tr0[o]=min(tr0[lc],tr0[rc]);
	tr1[o]=min(tr1[lc],tr1[rc]);
}

void Del(int p,LL w0,LL w1,int o=1,int l=1,int r=H)
{
	if(l==r)
	{
		hp0[o].Del(w0);
		hp1[o].Del(w1);
		tr0[o]=hp0[o].Top();
		tr1[o]=hp1[o].Top();
		//Whats(tr0[o]);
		//Whats(tr1[o]);
		return;
	}
	int mid=(l+r)>>1,lc=o<<1,rc=lc^1;
	if(p<=mid)
		Del(p,w0,w1,lc,l,mid);
	else
		Del(p,w0,w1,rc,mid+1,r);
	tr0[o]=min(tr0[lc],tr0[rc]);
	//cout<<l<<","<<r<<endl;
	tr1[o]=min(tr1[lc],tr1[rc]);
}

LL Ask(int ql,int qr,LL *tr,int o=1,int l=1,int r=H)
{
	if(ql<=l&&r<=qr)
		return tr[o];
	int mid=(l+r)>>1,lc=o<<1,rc=lc^1;
	LL res=INF;
	if(ql<=mid)
		GetMin(res,Ask(ql,qr,tr,lc,l,mid));
	if(qr>mid)
		GetMin(res,Ask(ql,qr,tr,rc,mid+1,r));
	return res;
}

int n,ki,h[N];
LL dp[N];

void Insert(int x)
{
	Insert(h[x],dp[x]-h[x],dp[x]+h[x]);
}

void Del(int x)
{
	Del(h[x],dp[x]-h[x],dp[x]+h[x]);
}

int main()
{
	memset(tr0,0x3f,sizeof tr0);
	memset(tr1,0x3f,sizeof tr1);
	scanf("%d%d",&n,&ki);
	for(int i=1;i<=n;++i)
		scanf("%d",h+i);
	for(int i=1;i<=n;++i)
	{
		if(i>1)
			dp[i]=min(Ask(1,h[i],tr0)+h[i],Ask(h[i],H,tr1)-h[i]);
		if(i<n)
		{
			Insert(i);
			if(i>ki)
				Del(i-ki);
		}
		//Whats(i);
		//Whats(dp[i]);
	}
	printf("%lld",dp[n]);
	return 0;
}

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
	dp[i]=dp[i-1]+abs(h[i]-h[i-1])
	for j in range(2,min(k,i)+1):
		dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[n-1])
n, m = map(int, input().split())
ac = [0] * n
pen = [0] * n
pen_count = 0
for i in range(m):
    p, s = input().split()
    p = int(p) - 1
    if ac[p] == "AC":
        continue
    elif s == "AC":
        ac[p] = "AC"
    else:
        pen[p] += 1
 
for i in range(n):
    if ac[i] == "AC":
        pen_count += pen[i]
 
print(ac.count("AC"), pen_count)

### FIXED CODE ###

c = input()
a_list= list('abcdefghijklmnopqrstuvwxyz')
for i in range(0, len(a_list)):
    if a_list[i] == c:
        i += 1
        print(a_list[i])
A, B = [int(i) for i in input().split(" ")]
if B <= 5:
  print(str(0))
elif B <= 13:
  print(str(int(B/2)))
else:
  print(str(b))


### FIXED CODE ###

A, B = [int(i) for i in input().split(" ")]
if A <= 5:
  print(str(0))
elif A <= 12:
  print(str(round(B/2)))
else:
  print(str(B))
from math import ceil
N, K = map(int, raw_input().split())
A = map(int, raw_input().split())

print (ceil((N-1)/(K-1)))


### FIXED CODE ###

import math
N, K = map(int, input().split())
input()
     
print(math.ceil((N-1)/(K-1)))
N, L = map(int, input().split())
S = [input() for i in range(L)]

print(''.join(sorted(S)))


### FIXED CODE ###

N, L = map(int, input().split())
S = [input() for i in range(N)]

print(''.join(sorted(S)))
import math
n=int(input())
k=int(input())

b=2**n
ans=math.inf
for i in range(b):
    bit_b=bin(i)[2:].zfill(n)
    ans_i=1
    for j in range(len(bit_b)):
        if(bit_b[j]=='0'):
            ans_i*=2
        elif(bit_b[j]=='1'):
            ans_i+=k

    if(ans>ans_i):
        ans=ans_i

print(ans)

### FIXED CODE ###

n=int(input())
k=int(input())

b=2**n
ans=999999999999999999
for i in range(b):
    bit_b=bin(i)[2:].zfill(n)
    ans_i=1
    for j in range(len(bit_b)):
        if(bit_b[j]=='0'):
            ans_i*=2
        elif(bit_b[j]=='1'):
            ans_i+=k

    if(ans>ans_i):
        ans=ans_i

print(ans)
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N,L=map(int,input().split())

list=soeted([input() for i in range(N)])
print(*list,sep="")

### FIXED CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N,L=map(int,input().split())

list=sorted([input() for i in range(N)])
print(*list,sep="")
n,q=map(int,input().split())
s=input()
index=[]
num=0
for i in range(len(s)-1):
    if s[i:i+2]=='AC':
        index+=[[i+1,num+1]]
        num+=1
ans=[]
for i in range(q):
    l,r=map(int,input().split())
    j=0
    k=1
    while index[j][0]<l or index[k*(-1)][0]+1>r:
        if index[j][0]<l:
            j+=1
        if index[k*(-1)][0]+1>r:
            k+=1
    ans+=[index[k*(-1)][1]-index[j][1]+1]

for i in ans:
    print(i)



### FIXED CODE ###

n,q=map(int,input().split())
s=input()
index1=[0]*(n+2)

num=0
for i in range(len(s)):
    if s[i:i+2]=='AC':
        num+=1
    index1[i+1]=num


ans=[]

for i in range(q):
    l,r=map(int,input().split())
    if index1[l-1]==index1[l] and index1[r-1]==index1[r]:
        ans+=[index1[r]-index1[l]]
    elif index1[l-1]!=index1[l] and index1[r-1]==index1[r]:
        ans+=[index1[r]-index1[l]+1]
    elif index1[l-1]==index1[l] and index1[r-1]!=index1[r]:
        ans+=[index1[r]-index1[l]-1]
    elif index1[l-1]!=index1[l] and index1[r-1]!=index1[r]:
        ans+=[index1[r]-index1[l]]
for i in ans:
    print(i)
N, A, B = map(int, input().split())

tmp = [1]*A + [0]*B
while len(tmp) < N:
    tmp += tmp
ans = sum(tmp[:N])

print(ans)

### FIXED CODE ###

N, A, B = map(int, input().split())
if N >= (A+B):
    ans = A * (N//(A+B)) + min((N - ((A + B) * (N//(A+B)))), A)
elif N > A:
    ans = A
elif A >= N:
    ans = N
print(ans)
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    return d
'''
result = Dijkstra(r, vertex)
for i in range(vertex):
    if i == r:
        result[i] = 0
    if result[i] == infty:
        result[i] = "INF"
    print(result[i])



### FIXED CODE ###

# Single Source Shortest Path
import heapq

[vertex, edge, r] = list(map(int, input("").split()))
infty = 999999999
final_c = [infty for i in range(vertex)]
dict_c = [[] for i in range(vertex)]

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    dict_c[e1].append((e2, c))

final_c[r] = 0
root_c = [(final_c[r], r)]

def Dijkstra(root, n):
    global infty, root_c, final_c, dict_c, root_c
    while(root_c):
        (cost, v) = heapq.heappop(root_c)
        if cost > final_c[v]:
            continue
        for i in range(len(dict_c[v])):
            (e2, c) = dict_c[v][i]
            if final_c[e2] > final_c[v] + c:
                final_c[e2] = final_c[v] + c
                heapq.heappush(root_c, (final_c[e2], e2))

Dijkstra(r, vertex)
for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print(final_c[i])
n, x = map(int, input().split())
l = [int(i) for i in range(n)]
print(n+((x-sum(l))//min(l)))


### FIXED CODE ###

n, x = map(int, input().split())
l = [int(input()) for _ in range(n)]
print(n+(x-sum(l))//min(l))
a = str(input())
b = str(input())
c = b[-1]
if a + c == b:
    print("Yes")
else:
    print("No"

### FIXED CODE ###

a = str(input())
b = str(input())
c = b[-1]
if a + c == b:
    print("Yes")
else:
    print("No")
a,b,h=map(int, input().split())

N = (a+b)*h/2

print(int(N))


### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
print((a+b)*h//2)
N,W = map(int,input().split())
w = []
v = []
for i in range(N):
  w_,v_ = map(int,input().split())
  w.append(w_)
  v.append(v_)

dp = [[0]*(W+1) for _ in range(N+1)]

def memo(i,j):
  if dp[i][j]:
    return dp[i][j]
  if i == N:
    dp[i][j] = 0
  elif w[i] > j:
    dp[i][j] = memo(i+1,j)
  else:
    dp[i][j] = max(memo(i+1,j),memo(i+1,j-w[i])+v[i])
  return dp[i][j] 
print(memo(0,W))

### FIXED CODE ###

N = int(input())
h = list(map(int,input().split()))
h = [0] + h
dp = [0]*(N+1)
dp[2] = abs(h[2]-h[1])
for i in range(3,N+1):
  dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[N])
import intertools

n , m = map(int,input().split())
sw = [[] for _ in range(m)]
for i in range(m):
    sw[i] = list(map(int,input().split()[1::]))

ans = 0

for tpl in intertools.product([0,1],repeat = n):
    bl = True
    for i in range(m):
        s = sum(tpl[s-1] for s in sw[i])
        if (s-p[i])%2 != 0:
            bl = False
            break
    if bl:
        ans +=1
print(ans)

### FIXED CODE ###

import itertools
n , m = map(int,input().split())
sw = [[] for _ in range(m)]
for i in range(m):
    sw[i] = list(map(int,input().split()[1::]))
p = [int(x) for x in input().split()]
ans = 0

for tpl in itertools.product([0,1],repeat = n):
    bl = True
    for i in range(m):
        s = sum(tpl[s-1] for s in sw[i])
        if (s-p[i])%2 != 0:
            bl = False
            break
    if bl:
        ans +=1
print(ans)
N=int(input())
S=input()
K=int(input())
s=S[K]

X=[]*N

for i in S:

    if i==s:
        X.append(i)
    else:
        X.append("*")

Y="".join(X)
print(Y)


### FIXED CODE ###

N=int(input())
S=input()
K=int(input())
s=S[K-1]

X=[]*N

for i in S:

    if i==s:
        X.append(i)
    else:
        X.append("*")

Y="".join(X)
print(Y)
h, w = map(int, input().split())
a = [input() for w in range(h)]

for i in range(h)[::-1]:
    if "#" not in a[i]:
        del a[i]
        h -= 1

n = []
for j in range(w):
    m = ["".join(t[j] for t in a)]
    if "#" in m[0]:
        n += m

for k in range(h):
    print("".join(u[k] for u in n))


### FIXED CODE ###

n,i = input().split()
print(int(n)-int(i)+1)
N,A,B,C,D = map(int, input().split())
s = input()
index = [(n+1) for n, v in enumerate(s) if s[n:n+3] == "..."]

if s.count("##")>=1:
    print("No")
    exit()

if C < D:
    print("Yes")

elif C > D:
    if len(index)>=1:
        for i in range(B-1:D):
            if s[i-1]=="." and s[i]=="." and s[i+1]==".":
                print("Yes")
                exit()
        print("No")
    else:
        print("No")


### FIXED CODE ###

N,A,B,C,D = map(int, input().split())
s = input()
index = [(n+1) for n, v in enumerate(s) if s[n:n+3] == "..."]

if C < D:
    if "##" in s[A-1:D]:
        print("No")
    else:
        print("Yes")

if C > D:
    if "##" in s[A-1:C]:
        print("No")
    else:
        if len(index)>=1:
            for i in index:
                if B <= i+1 <= D:
                    print("Yes")
                    exit()
            print("No")
        else:
            print("No")
a, b, c = map(int, input().split())

if a == b and a != c:
    print("Yes")
elif a == c and a != b:
    print("Yes")
elif b == c and a != b:
    print("Yes")
ese:
    print("No")


### FIXED CODE ###

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

if a == b and a != c:
    print("Yes")
elif a == c and a != b:
    print("Yes")
elif b == c and a != b:
    print("Yes")
else:
    print("No")
import math

(x1, y1, x2, y2) = [float(i) for i in input().split()]
#distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
distance - math.hypot((x2 - x1), (y2 - y1))
print('{0:.5f}'.format(distance))

### FIXED CODE ###

import math

(x1, y1, x2, y2) = [float(i) for i in input().split()]
#distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
distance = math.hypot((x2 - x1), (y2 - y1))
print('{0:.5f}'.format(distance))
a, b, c=map(int,input().split())
m=max(max(a+b, a-b),a*b)
print(m)

### FIXED CODE ###

a, b=map(int, input().split())
print(max(a*b,a+b,a-b))
import sys
n  = int(input())
a = list(map(int,input().split()))
ans = 1
for i in ans:
  ans*=i
  if ans>int(1e18):
    print(-1)
    sys.exit()
print(ans)
    

### FIXED CODE ###

import sys
n  = int(input())
a = list(map(int,input().split()))
ans = 1
a.sort()
for i in a:
  ans*=i
  if ans>int(1e18):
    print(-1)
    sys.exit()
print(ans)
n, q = map(int, input().split())
s = input()
li_lr = list()

li_flg = [0] * len(s)

for i in range(q):
    li_lr.append(list(map(int, input().split())))


for idx, v in enumerate(s):
    if v == 'A':
        if idx != len(s) and s[idx + 1] == 'C':
            li_flg[idx] = 1


for l in li_lr:
    li_w = li_flg[l[0] - 1: l[1]]
    if li_w[-1] == 1:
        print(sum(li_w) - 1)
    else:
        print(sum(li_w))



### FIXED CODE ###

n, q = map(int, input().split())
s = input()
li_lr = list()

li_flg = [0] * len(s)

for i in range(q):
    li_lr.append(list(map(int, input().split())))


for idx, v in enumerate(s):
    if v == 'C' and idx != 0 and s[idx - 1] == 'A':
        li_flg[idx] = li_flg[idx - 1] + 1
    else:
        li_flg[idx] = li_flg[idx - 1]

for l in li_lr:
    print(li_flg[l[1] - 1] - li_flg[l[0] - 1])