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

import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]


NN = 10 ** 6 + 100
primes = []
isprime = [True for _ in range(NN + 1)]
min_factor = [-1 for _ in range(NN + 1)]
#エラトステネスの篩
for i in range(2, NN + 1):
    if not isprime[i]:
        continue
    primes.append(i)
    min_factor[i] = i
    for j in range(i * 2, NN + 1, i):
        isprime[j] = False
        if min_factor[j] == -1:
            min_factor[j] = i
def prime_factrize(n):
    res = []
    while n != 1:
        prime = min_factor[n]
        exp = 0
        while min_factor[n] == prime:
            exp += 1
            n //= prime
        res.append([prime, exp])
    return res


n = INT()
a = LIST()
ll = []
for i in range(n):
    aa = prime_factrize(a[i])
    end = len(ll) - 1
    for j in range(len(aa)):
        if len(ll) == 0:
            ll.append(aa[j])
        else:
            left = 0
            rght = end
            while left < rght:
                cntr = (rght + left) // 2
                if ll[cntr][0] == aa[j][0]:
                    left = cntr
                    rght = cntr
                elif ll[cntr][0] > aa[j][0]:
                    rght = cntr - 1
                elif ll[cntr][0] < aa[j][0]:
                    left = cntr + 1
            if left <= end and ll[left][0] == aa[j][0]:
                ll[left][1] = max(ll[left][1], aa[j][1])
            else:
                ll.append(aa[j])
    ll.sort(key=lambda x: x[0])
l = 1
for i in range(len(ll)):
    l *= pow(ll[i][0], ll[i][1], mod)
ans = 0
for i in range(n):
    ans += l // a[i]
    ans %= mod
print(ans)


### FIXED CODE ###

import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
a = LIST()
l = 1
for i in a:
    l = lcm(l, i)
l %= mod
ans = 0
for i in a:
    ans += l * pow(i, mod - 2, mod)
print(ans % mod)
### BUGGY CODE ###

H, N = map(int, input().split())
G = [0 for i in range(N)]
for i in range(N):
    A, B = map(int, input().split())
    koritu = A / B
    G[i] = (koritu, A, B)
G.sort(reverse = True)
#print(G)
dp = [[0 for i in range(H+1)] for j in range(N)]
for j in range(N):
    k, a, b = G[j]
    if j == 0:
        for i in range(1,H+1):
            dp[j][i] = ((i-1)//a+1) * b
    else:
        for i in range(1, H+1):
            if i >= a:
                dp[j][i] = min(dp[j-1][i], dp[j][i-a] + b)
            else:
                dp[j][i] = min(dp[j-1][i],b)
print(dp[N-1][H])



### FIXED CODE ###

H, N = map(int, input().split())
G = [0 for i in range(N)]
for i in range(N):
    A, B = map(int, input().split())
    koritu = A / B
    G[i] = (koritu, A, B)
G.sort(reverse = True)
#print(G)
dp = [[0 for i in range(H+1)] for j in range(N)]
k, a, b = G[0]
for i in range(1, H + 1):
    dp[0][i] = ((i - 1) // a + 1) * b
for j in range(1, N):
    k, a, b = G[j]
    for i in range(1, H+1):
        if i >= a:
            dp[j][i] = min(dp[j-1][i], dp[j][i-a] + b)
        else:
            dp[j][i] = min(dp[j-1][i],b)
print(dp[N-1][H])
### BUGGY CODE ###

from operator import itemgetter


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

INF = 10**18
dp = [[INF] * (1 << n) for i in range(n)]
for i in range(n):
    dp[i][1 << i] = i

for bit_state in range(1 << n):
    cnt1 = bin(bit_state).count("1")
    for i in range(n):
        cnt0 = -1
        if not(bit_state & (1 << i)):
            continue
        for j in range(n):
            if bit_state & (1 << j):
                continue
            cnt0 += 1
            num_i = a[i] if (cnt1 - 1) % 2 == i % 2 else b[i]
            num_j = a[j] if (cnt1) % 2 == j % 2 else b[j]
            if num_i > num_j:
                continue
            dp[j][bit_state | (1 << j)] = min(dp[j][bit_state | (1 << j)], dp[i][bit_state] + cnt0)

ans = 10**18
for i in range(n):
    ans = min(ans, dp[i][-1]) 
if ans == 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


from operator import itemgetter
from collections import deque

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 10**18


for bit_state in range(1 << n):
    pattern = [[] for i in range(2)]
    for i in range(n):
        if bit_state & (1 << i) and i % 2 == 0:
            pattern[0].append(a[i]*100 + i)
        elif bit_state & (1 << i) and i % 2 == 1:
            pattern[1].append(a[i]*100 + i)
        elif i % 2 == 0:
            pattern[1].append(b[i]*100 + i)
        else:
            pattern[0].append(b[i]*100 + i)

    if len(pattern[0]) == len(pattern[1]) or len(pattern[0]) - 1 == len(pattern[1]):
        for i in range(2):
            pattern[i] = sorted(pattern[i])
        bit = BIT(n)
        ans_tmp = 0
        prev_num = 10**8
        for i in range(n)[::-1]:
            pal = i % 2
            num = pattern[pal].pop()
            ind = num % 100
            num = num // 100
            if prev_num < num:
                break
            prev_num = num
            bit.add(ind, 1)
            ans_tmp += bit.get_sum(0, ind)
        else:
            ans = min(ans, ans_tmp)

if ans == 10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

nonzero = [0]*60

for i in range(N):
    for j in range(60):
        tmp = (A[i] >> j) & 1
        if tmp != 0:
            nonzero[j] += 1

ans = 0
MOD = 10**9+7

for i in range(60):
    ans += (N-nonzero[i])*nonzero[i]*pow(2,(i),MOD)%MOD
    
print(ans%MOD)
    

### FIXED CODE ###

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

nonzero = [0]*60

for i in range(N):
    for j in range(60):
        tmp = (A[i] >> j) & 1
        if tmp != 0:
            nonzero[j] += 1

ans = 0
MOD = 10**9+7

for i in range(60):
    ans += ((N-nonzero[i])*nonzero[i]*(2**i))%MOD
    
print(ans%MOD)
### BUGGY CODE ###

from fractions import gcd
from math import sqrt

a,b = map(int,input().split())
n = gcd(a,b)
k = n
s = set()
s.add(1)
for i in range(2,int(sqrt(n))+10**8):
  while n%i == 0:
    n = n//i
    s.add(i)
  if n == 1:
    break
if len(s) == 1 and k != 1:
  print(len(s)+1)
else:
  print(len(s))

### FIXED CODE ###

from fractions import gcd
from math import sqrt

a,b = map(int,input().split())
n = gcd(a,b)
k = n
s = set()
s.add(1)
for i in range(2,int(sqrt(n))+1):
  while n%i == 0:
    n = n//i
    s.add(i)
  if n == 1:
    break
s.add(n)
print(len(s))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
H,W=map(int,input().split())


def dfs(h,w,num):
    
    l[h][w]=min(l[h][w],num)
    
    if h>0:
        if A[h-1][w]!="#" and l[h-1][w]>=num:
            dfs(h-1,w,num+1)
    if w>0:
        if A[h][w-1]!="#" and l[h][w-1]>=num:
            dfs(h,w-1,num+1)
    if h<H-1:
        if A[h+1][w]!="#" and l[h+1][w]>=num:
            dfs(h+1,w,num+1)
    if w<W-1:
        if A[h][w+1]!="#" and l[h][w+1]>=num:
            dfs(h,w+1,num+1)
    
    return 0


A=[]
for _ in range(H):
    A.append(list(input()))

#print(A)

l=[[300]*W for i in range(H)]

for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            dfs(h,w,0)
ans=0
for item in l:
    ans=max(ans,max(item))

#print(l)
print(ans)


### FIXED CODE ###

# coding: utf-8
# Your code here!
H,W=map(int,input().split())


def dfs(h,w):
    A[h][w]="#"
    que=[]
    if h>0:
        if A[h-1][w]!="#":
            que.append([h-1,w])
            A[h-1][w]="#"
    if w>0:
        if A[h][w-1]!="#":
            que.append([h,w-1])
            A[h][w-1]="#"
    if h<H-1:
        if A[h+1][w]!="#":
            que.append([h+1,w])
            A[h+1][w]="#"
    if w<W-1:
        if A[h][w+1]!="#":
            que.append([h,w+1])
            A[h][w+1]="#"
    
    return que


A=[]
for _ in range(H):
    A.append(list(input()))

#print(A)

ans=0
lis=[]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            lis.append([h,w])
while True:
    pre=[]
    if lis:
        N=len(lis)
        lis=lis[::-1]
        for i in range(N):
            item=lis.pop(-1)
            pre+=dfs(item[0],item[1])
        lis=pre
    if len(lis)==0:
        break
    ans+=1
    #print(lis)
    #print(A)
    
print(ans)
### BUGGY CODE ###

N,M = map(int, input().split())
L = []
C = 0
P = 0
for i in range(M):
    p,S = map(str, input().split())
    if S == 'AC' and [p,S] not in L:
        L.append([p,S])
        C += 1
    elif S == 'WA' and [p,'AC'] not in L:
        L.append([p,S])
        P += 1
print(C,P)

### FIXED CODE ###

N,M = map(int, input().split())
A = {}
C = 0
P = 0
for i in range(M):
    p,S = map(str, input().split())
    if S == 'AC' and A.get(p+S) is None:
        A[p+S] = 0
        C += 1
    elif S == 'WA' and A.get(p+'AC') is None and A.get(p+S) is None:
        A[p+S] = 1
    elif S == 'WA' and A.get(p+'AC') is None:
        A[p+S] += 1
for i in range(1,N+1):
    if A.get(str(i)+'AC') is not None and A.get(str(i)+'WA') is not None:
        P += A[str(i)+'WA']
print(C,P)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
 
flg=1
count=0
while True:
    for i in A: #全て偶数か確かめる
        if i%2==1:
            break
        
    if flg==1:
        for i in A:
            i=i//2
        count+=1
    else:
        break
print(count)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
 
flg=1
count=0
while True:
    for i in A: #全て偶数か確かめる
        if i%2==1:
            flg=0
            break

    if flg==1:
        for i in range(N):
            A[i]=A[i]//2
        count+=1
    else:
        break
print(count)
### BUGGY CODE ###

def putmx(lis,mx):
  ret=[]
  for i in range(len(lis)):
    if lis[i]==mx:
      ret.append(i)
  return ret
  

h,w,m=map(int,input().split())
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(h):
  bmb.append([])
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb[hh].append(ww)
  hb[hh]+=1
  wb[ww]+=1
mhb=max(hb)
mwb=max(wb)
hmx=putmx(hb,mhb)
wmx=putmx(wb,mwb)

#print(hb,wb,hmx,wmx)
fl=False
for i in hmx:
  for j in wmx:
    if not j in bmb[i]:
      print(mhb+mwb)
      fl=True
      break
  if fl:
    break
else:
  print(mhb+mwb-1)



### FIXED CODE ###

#import random

def putmx(lis,mx):
  ret=[]
  for (i,j) in zip(range(len(lis)),lis):
    if j==mx:
      ret.append(i)
  return ret
  

h,w,m=map(int,input().split())
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(h):
  bmb.append({-1})
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb[hh].add(ww)
  hb[hh]+=1
  wb[ww]+=1
mhb=max(hb)
mwb=max(wb)
hmx=putmx(hb,mhb)
wmx=set(putmx(wb,mwb))

#print(hb,wb,hmx,wmx)
fl=False
for i in hmx:
  if wmx|bmb[i]!=bmb[i]:
    print(mhb+mwb)
    break
else:
  print(mhb+mwb-1)

#print(hmx,wmx,bmb)
### BUGGY CODE ###

N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list = [1,0]
    else:
        Dp_list = [1,1]
else:
    Dp_list = [1,1]
if N != 1:
    for i in range(2, N + 1):
        if i not in A_list:
            Dp_list.append(Dp_list[i-2] + Dp_list[i-1])
        elif i in A_list and i-1 in A_list:
            Dp_list = [0] * (N + 1)
            break
        else:
            Dp_list.append(0)
        if Dp_list[i-1] > 1000000007:
            Dp_list[i-1] -= 1000000007
            Dp_list[i] -= 1000000007
    print(Dp_list[N]%1000000007)
else:
    print(1)

### FIXED CODE ###

N, M = map(int,input().split())
A_list = set([int(input()) for _ in range(M)])
Dp_list = [0] * (N+1)
Dp_list[0] = 1

if 1 in A_list:
    Dp_list[1] = 0
else:
    Dp_list[1] = 1

if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue

        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
        Dp_list[i] %= 1000000007
    print(Dp_list[N])
else:
    print(1)
### BUGGY CODE ###

N , K = map(int, input().split())
flag = "F"
while 1:
    if N>10000000*K:
        N = N -10000000*K
    a = N
    N = abs(N - K)
    

    if a<=K and N <= K:
        if a < N:
            result = a
            flag="T"
        else:
            result = N
            flag="T"
    if flag == "T":
        break
print(result)

### FIXED CODE ###

import math

N , K = map(int, input().split())
flag = "F"
if N !=0:
    while 1:
        lenN = int (math.log10(N) + 1)
        lenK = int (math.log10(K) + 1)
        N = abs(N-K*(10**abs(lenN-lenK-1)))
        lenN = int (math.log10(N) + 1)
        if abs(lenN-lenK)<2:
            break



        
while 1:
    
    
    a = N
    N = abs(N - K)
    

    if a<=K and N <= K:
        if a < N:
            result = a
            flag="T"
        else:
            result = N
            flag="T"
    if flag == "T":
        break
print(result)
### BUGGY CODE ###

"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
import sys
sys.setrecursionlimit(1000000)

N = int(input())

A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))
 
#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

matchs = []
for i in range(1,N+1):
    for j in range(i+1,N+1):
        matchs.append((i,j))

edges = {}
for match in matchs:
    edges[match] = []
    i,j = match
    if reverseMemo[i][j] != N-1:
        nx = A[i][reverseMemo[i][j]+1]
        edges[match].append((min(i,nx),max(i,nx)))
    if reverseMemo[j][i] != N-1:
        nx = A[j][reverseMemo[j][i]+1]
        edges[match].append((min(j,nx),max(j,nx)))

stepMemo = {}
def dfs(i,j,cnt):
    if cnt > N*N:
        print(-1)
        exit()
    #i,jの試合日を含めて、あと何日必要なのかを返す。
    if (i,j) not in stepMemo:
        res = 1
        for a,b in edges[(i,j)]:
            res = max(res,dfs(a,b,cnt+1)+1)
        stepMemo[(i,j)] = res
    return stepMemo[(i,j)]

ans = 0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        ans = max(ans,dfs(i,j,1))
print(ans)





### FIXED CODE ###

"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline

    N = int(input())

    A = [[0]*(N)]
    for i in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = [[-1]*(N+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j
    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            match = (i,j)
            edges[match] = []
            if reverseMemo[i][j] != N-1:
                nx = A[i][reverseMemo[i][j]+1]
                edges[match].append((min(i,nx),max(i,nx)))
            if reverseMemo[j][i] != N-1:
                nx = A[j][reverseMemo[j][i]+1]
                edges[match].append((min(j,nx),max(j,nx)))
    
    del reverseMemo
    del A
    
    stepMemo = {}
    def dfs(i,j,path):
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            if (i,j) in path:
                print(-1)
                exit()
            else:
                path.add((i,j))
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,path)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if (i,j) not in stepMemo:
                ans = max(ans,dfs(i,j,set()))
    print(ans)
main()
### BUGGY CODE ###

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

for i in range(m):
  a.sort(reverse = True)
  a[0] //= 2
print(sum(a))


### FIXED CODE ###

import heapq

n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
a = list(map(lambda x:x*(-1),a))
heapq.heapify(a)

for i in range(m):
  mx = heapq.heappop(a)
  mx= -(-mx//2)
  heapq.heappush(a,mx)

a = list(map(lambda x:x*(-1),a))
print(sum(a))
### BUGGY CODE ###

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

c = 0
for i in range(10):
        for j in range(10):
            for k in range(10):
                count = 0
                for l in s:
                    if l == str(k) and count == 2:
                        count += 1
                    if l == str(j) and count == 1:
                        count += 1
                    if l == str(i) and count == 0:
                        count += 1
                if count == 3:
                    c += 1
print(c)


### FIXED CODE ###

n = int(input())
s = list(map(int,input()))

def nc(n,s,i,j,k):
    c1 = -1
    for l in range(n):
        if s[l] == i:
            c1 = l
            break
    if c1 == -1:
        return 0
    c2 = -1
    for l in range(c1+1,n):
        if s[l] == j:
            c2 = l
            break
    if c2 == -1:
        return 0
    c3 = -1
    for l in range(c2+1,n):
        if s[l] == k:
            c3 = l
            break
    if c3 == -1:
        return 0
    return 1

c = 0
for i in range(10):
        for j in range(10):
            for k in range(10):
                c += nc(n,s,i,j,k)



print(c)
### BUGGY CODE ###

import  math
K = int(input())

ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for l in range(1, K + 1):
            ans  += math.gcd(l, math.gcd(i, j))
            
            
print(ans)


### FIXED CODE ###

from math import gcd
 
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for m in range(1,k+1):
            ans += gcd(i, gcd(j,m))
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split())) 
a.sort
p = True
ans = 1 
for i in a : 
  ans *= i 
  if(ans == 0) : 
    print(0)
    p = False 
    break 
if p:
  if ans > 10 **18 : 
    print(-1)
  else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
p = True
ans = 1
for i in a :
  ans *= i
  if(ans == 0) :
    print(0)
    p = False
    break
  if(ans > 1000000000000000000):
    print(-1)
    p =False
    break
if p:
  if ans > 1000000000000000000:
    print(-1)
  else:
    print(ans)
### BUGGY CODE ###

# atcoder 動的計画法
# I Coins

def get_inputs():
    # N コインの枚数
    # ps 各コインが表となる確率の配列(リスト)
    
    N = int(input())
    
    ps = list(map(float, input().split()))
    
    return N, ps

# 動的計画法の基づきテーブルを作成する
# dp[i][j] : i番目までのコインを投げた時に、j枚が表である確率
# 漸化式は下のようになる
# dp[i + 1][j + 1] = dp[i + 1][j + 1] + dp[i][j] * p(i + 1)
# dp[i + 1][j] = dp[i + 1][j] + dp[i][j] * (1 - p(i + 1))
#
# 0相対で考えて 0<= i < N, 0 <= j <= N  

N, ps = get_inputs()

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

dp[0][0] = 1 - ps[0]
dp[0][1] = ps[0]

for i in range(N - 1):
    for j in range(i + 2):
        dp[i + 1][j] = dp[i + 1][j] + dp[i][j] * (1 - ps[i + 1])
        dp[i + 1][j + 1] = dp[i + 1][j + 1] + dp[i][j] * ps[i + 1]

print(sum(dp[N - 1][(N + 1)//2:]))


### FIXED CODE ###

# atcoder 動的計画法
# I Coins

import numpy as np


def get_inputs():
    # N コインの枚数
    # ps 各コインが表となる確率の配列(リスト)

    N = int(input())

    ps = list(map(float, input().split()))

    return N, ps


# 動的計画法の基づきテーブルを作成する
# dp[i][j] : i番目までのコインを投げた時に、j枚が表である確率
# 集める漸化式は下のようになる
# dp[i ][j ] = dp[i -1][j ]  *  (1 - p[i])  + dp[i - 1][j - 1] * p[i]
#
#

N, ps = get_inputs()

# dp = [[0.0] * (N + 1) for _ in range(N)]
dp = np.zeros((N, N + 1), dtype=float)

dp[0][1] = float(ps[0])
dp[0][0] = float(1.0 - ps[0])

for i in range(1, N):
    dp[i][:i + 2] = dp[i - 1][:i + 2] * (1 - ps[i])
    dp[i][1:i + 2] = dp[i - 1][:i + 1] * ps[i] + dp[i][1:i + 2]

print(sum(dp[N - 1][(N + 1) // 2:]))
### BUGGY CODE ###

s=input()
li=list(input())

min = 100000000

w = 0

for index, i in enumerate(li):
  a = 0
  
  s = li[index + 1:].count('E')

  a = w + s
    
  if min > a:
    min = a
    
  if i == 'W':
    w += 1

print(min)

### FIXED CODE ###

from itertools import accumulate
 
n = int(input())
s = [c == 'W' for c in input()]
l = accumulate([0] + s[:-1])
r = accumulate([0] + [not c for c in reversed(s[1:])])
print(min(e + w for e, w in zip(l, reversed(list(r)))))
### BUGGY CODE ###

from itertools import count

H, N = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(N)]

dp = [10 ** 9 for _ in range(H + 1)]
dp[0] = 0
for hp in range(1, H + 1):
    # print(dp)
    for A, B in ABs:
        if A <= hp:
            dp[hp] = min(dp[hp], dp[hp - A] + B)
        else:
            dp[hp] = min(dp[hp], B)

print(dp[-1])


### FIXED CODE ###

from itertools import count
 
H, N = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(N)]
 
dp = [10 ** 9 for _ in range(H + 1)]
dp[0] = 0
for hp in range(1, H + 1):
    # print(dp)
    for A, B in ABs:
        if A <= hp:
            dp[hp] = min(dp[hp], dp[hp - A] + B)
        else:
            dp[hp] = min(dp[hp], B)
print(dp[-1])
### BUGGY CODE ###

from itertools import combinations

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

d = {}
for i in range(N):
    if A[i] < N:
        d[i] = A[i]

result = 0
for a, b in combinations(d, 2):
    if abs(a - b) == A[a] + A[b]:
        result += 1
print(result)


### FIXED CODE ###

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

c1 = {}
c2 = {}

for i in range(N):
    c1.setdefault(i + A[i], 0)
    c1[i + A[i]] += 1
    c2.setdefault(i - A[i], 0)
    c2[i - A[i]] += 1

result = 0
for k in set(c1).intersection(c2):
    result += c1[k] * c2[k]
print(result)
### BUGGY CODE ###

n = int(input())
a = input().split()

ans = 1
for i in a:
    i = int(i)
    ans = ans * i
if ans > 10 ** 18:
    ans = '-1'
print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

N = int(input())
A_List =[]
for i in range(N):
    A = int(input())
    A_List.append(A)
for i in range(N):
    print(max(A_List[:i]+A_List[i+1:]))

### FIXED CODE ###

N = int(input())
A_List =[]
for i in range(N):
    A = int(input())
    A_List.append(A)
A_List2 = A_List.copy()
A_List2 = sorted(A_List2)

A_max = A_List2[-1]
A_max2 = A_List2[-2]

for a in A_List:
    if a ==A_max:
        print(A_max2)
    else:
        print(A_max)
### BUGGY CODE ###

N, M, Q  = map(int, input().split())
count = [[0] * N for i in range(N)]

for _ in range(M):
  L,R = map(int, input().split())
  for i in range(0,L):
    for j in range(R-1,N):
      count[i][j] += 1

for _ in range(Q):
  p,q = map(int, input().split())
  print(count[p-1][q-1])

### FIXED CODE ###

N, M, Q  = map(int, input().split())
count = [[0] * (N+1) for i in range(N)]

for _ in range(M):
  L,R = map(int, input().split())
  count[L-1][R] += 1

for i in range(N):
  for j in range(1,N+1):
    count[i][j] += count[i][j-1]




for _ in range(Q):
  p,q = map(int, input().split())
  ans = 0

  for i in range(p-1,q):
    ans += count[i][q] - count[i][p-1]
  print(ans)