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

import sys

input=sys.stdin.readline

N=int(input())
p=[]
for i in range(N):
    x,y=map(int,input().split())
    p.append([x,y])
mod=998244353

pow=[1]
for i in range(N):
    pow.append((pow[-1]*2)%mod)

p.sort(key=lambda x:x[1])
for i in range(N):
    p[i][1]=i+1


data=[[0 for i in range(4)] for i in range(N)]
#A1 ... AnのBIT(1-indexed)
n=N
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    if idx==0:
        return 0
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

p.sort()
for i in range(N):
    x,y=p[i]
    data[i][0]=BIT_query(N)-BIT_query(y)
    data[i][3]=BIT_query(y-1)
    BIT_update(y,1)

BIT=[0]*(n+1)
for i in range(N-1,-1,-1):
    x,y=p[i]
    data[i][1]=BIT_query(N)-BIT_query(y)
    data[i][2]=BIT_query(y-1)
    BIT_update(y,1)

ans=0
for i in range(N):
    ban=0
    for j in range(4):
        ban+=(pow[data[i][j]]-1)*pow[data[i][j-1]]
        ban%=mod
    ans+=pow[N]-ban-1
    ans%=mod
print(ans)


### FIXED CODE ###

import sys

input=sys.stdin.readline

N=int(input())
p=[]
for i in range(N):
    x,y=map(int,input().split())
    p.append([x,y])
mod=998244353

pow=[1]
for i in range(N):
    pow.append((pow[-1]*2)%mod)

p.sort(key=lambda x:x[1])
for i in range(N):
    p[i][1]=i+1


data=[[0 for i in range(4)] for i in range(N)]
#A1 ... AnのBIT(1-indexed)
n=N
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    if idx==0:
        return 0
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

p.sort()
for i in range(N):
    x,y=p[i]
    a,b=i,BIT_query(y)
    data[i][0]=a-b
    data[i][3]=b
    BIT_update(y,1)

BIT=[0]*(n+1)
for i in range(N-1,-1,-1):
    x,y=p[i]
    a,b=N-1-i,BIT_query(y)
    data[i][1]=a-b
    data[i][2]=b
    BIT_update(y,1)

ans=0
for i in range(N):
    ban=0
    for j in range(4):
        ban+=(pow[data[i][j]]-1)*pow[data[i][j-1]]
        ban%=mod
    ans+=pow[N]-ban-1
    ans%=mod
print(ans)
### BUGGY CODE ###

n, *a = map(int, open(0).read().split())
b = [0] * 60
c = [0] * 60
ans = 0
for i in range(n):
    for j in range(60):
        c[j] += i - b[j] if a[i] >> j & 1 else b[j]
        b[j] += a[i] >> j & 1
for j in range(60):
    ans += c[j] << j
print(ans % (10**9 + 7))

### FIXED CODE ###

#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
b = [0] * 60
ans = 0
for i in range(n):
    for j in range(60):
        ans += (i - b[j] if a[i] >> j & 1 else b[j]) << j
    ans %= 10**9 + 7
    for j in range(60):
        b[j] += a[i] >> j & 1
print(ans)
### BUGGY CODE ###

from operator import sub

N = int(input())
data = list(map(int, input().split()))
step = N * (N+1) // 2
total = sum(data)
#print("-->", total, step)
if total % step:
  print("NO")
else:
  K = total // step
  #print("-->", total, step, K)
  datar = [data[i % N] for i in range(-1, N)] 
  delta = list(map(sub, datar[1:], datar))
  #print(*delta)
  #print("-->", *list(map(lambda x:(K-x) % N, delta)))
  #print("-->", *list(map(lambda x:(K-x) // N, delta)))
  if any(map(lambda x:(K-x) % N, delta)):
    print("NO")
  else:    
    ops = list(map(lambda x:(K-x) // N, delta))
    if sum(ops) == K:
      for i, v in enumerate(data):
        vv = sum([ops[(i-k) % N] * (k+1) for k in range(N)])
        if v != vv:        
          print("NO")
          break
      else:    
        print("YES")
    else:
      print("NO")
    

### FIXED CODE ###

from operator import sub

N = int(input())
data = list(map(int, input().split()))
step = N * (N+1) // 2
total = sum(data)
#print("-->", total, step)
if total % step:
  print("NO")
else:
  K = total // step
  #print("-->", total, step, K)
  datar = [data[i % N] for i in range(-1, N)] 
  delta = list(map(sub, datar[1:], datar))
  #print(*delta)
  #print("-->", *list(map(lambda x:(K-x) % N, delta)))
  #print("-->", *list(map(lambda x:(K-x) // N, delta)))
  if any(map(lambda x:(K-x) % N, delta)):
    print("NO")
  elif any(map(lambda x: K-x < 0, delta)): 
    print("NO")
  else:    
    ops = list(map(lambda x:(K-x) // N, delta))
    if sum(ops) == K:
      for i, v in enumerate(data[0:1]):
        vv = sum([ops[(i-k) % N] * (k+1) for k in range(N)])
        if v != vv:        
          print("NO")
          break
      else:    
        print("YES")
    else:
      print("NO")
### BUGGY CODE ###

import sys 
input=sys.stdin.readline

N=int(input())
L=[[]]

for i in range(N):
    a=list(map(int,input().split()))
    L.append(a)
#print(L)

day=0
cnt=0
for i in range(10**6+5):
    if cnt==N*(N-1)/2:
        break
    D=dict()
    CNT=0
    for j in range(1,N+1):
        if L[j]==[] or j in D:
            continue
        elif L[L[j][0]][0]==j and L[j][0] not in D:
            D[j]=1
            D[L[j][0]]=1
            X=L[j][0]
            del L[j][0]
            del L[X][0]
            CNT+=1
    if CNT==0:
        print(-1)
        exit()
    cnt+=CNT
    day+=1
#print(L)
#print(cnt)
print(day)

### FIXED CODE ###

N=int(input())
A=[[0]]
for i in range(N):
    a=list(map(int,input().split()))
    a+=[0]
    A.append(a)
    
#print(A)
B=[0 for i in range(N+1)]
C=[a for a in range(1,N+1)]
cnt=0
for i in range(10**6):
    D=[]
    F=0
    for j in C:
        if A[A[j][B[j]]][B[A[j][B[j]]]]==j and j not in D and A[j][B[j]] not in D:
            D.append(j)
            D.append(A[j][B[j]])
            B[A[j][B[j]]]+=1
            B[j]+=1
            F=1
            cnt+=1
            #print("A",i,B,D)
            #print(A[j][B[j]],B,D)
    if F==0:
        break
    D.sort()
    C=D
    
if cnt==N*(N-1)//2:
    print(i)
else:
    print(-1)
### BUGGY CODE ###

n = input()
x = map(int, raw_input().split())
for i in xrange(n):
    x2 = x[:i]+x[i+1:]
    print sorted(x2)[(n/2)-1]


### FIXED CODE ###

n = input()
x = map(int, raw_input().split())
x2 = sorted(x)
mid1 = x2[(n/2)-1]
mid2 = x2[n/2]
if mid1 == mid2:
    for i in xrange(n):
        print mid1
else:
    for i in xrange(n):
        if x[i] <= mid1:
            print mid2
        else:
            print mid1
### BUGGY CODE ###

import sys
n, D, a = map(int, input().split())
tg = []
for _ in range(n):
    x, h = map(int, sys.stdin.readline().split())
    c = h // a
    if h % a > 0:
        c+=1
    tg.append([x, c])


tg = sorted(tg, key=lambda x:x[0])
result = 0
for i in range(n):
    c = tg[i][1]
    d = tg[i][0]
    if c <= 0:
        continue
    result += c
    wd = d + 2*D
    for j in range(i, n):
        if tg[j][0] <= wd:
            tg[j][1] -= c
        else:
            break
print(result)

### FIXED CODE ###

import sys
n, D, a = map(int, input().split())
tg = []
for _ in range(n):
    x, h = map(int, sys.stdin.readline().split())
    c = h // a
    if h % a > 0:
        c+=1
    tg.append([x, c])

class BIT:
    def __init__(self, n):
        self.n = n
        self.N = 1 << n.bit_length()
        self.data = [0] * (self.N +1)

    def add(self, i, x):
        while i <= self.N:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        total = 0
        while i > 0:
            total += self.data[i]
            i -= i&-i
        return total

    def search(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.N >> 1
        while k > 0:
            if x+k <= self.N and self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k = k >> 1
        return x+1

    def len(self):
        return self.data[self.N]

tg = sorted(tg, key=lambda x:x[0])
bit = BIT(n+2)
result = 0
ind = 0
for i in range(n):
    c = tg[i][1] - bit.sum(i+1)
    d = tg[i][0]
    if c <= 0:
        continue
    result += c
    wd = d + 2*D
    if ind < i:
        ind = i
    for j in range(ind, n):
        if tg[j][0] <= wd:
            ind = j
        else:
            break
    bit.add(i+1, c)
    bit.add(ind+2, -c)
print(result)
### BUGGY CODE ###

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

b = [i - 1 for i in a]
c = [i + 1 for i in a]

a.extend(b)
a.extend(c)
f = set(a)
ans = 0
for i in f:
    ans = max(ans, a.count(i))

print(ans)


### FIXED CODE ###

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

N = 10**5
cnt = [0 for i in range(N+2)]
# index 0 == -1
for i in a:
    cnt[i] += 1
    cnt[i+1] += 1
    cnt[i+2] += 1

print(max(cnt))
### BUGGY CODE ###

ans=0
s=input()
if len(s)<4:
  print(0)
  exit()
N=len(s)
L=list()
for i in range(3,N):
  L.append(int(s[:i+1]))
for i in range(N-3):
  for j in range(4,i+5):
    if (L[i]%pow(10,j))%2019==0:
      ans+=1
print(ans)

### FIXED CODE ###

ans=0
S=input()
a=len(S)
k=0
c=dict()
mod=2019
s=1
c[0]=1
for i in range(a):
  k+=(s*int(S[a-i-1]))
  k%=mod
  s*=10
  s%=mod
  if k in c:
    c[k]+=1
  else:
    c[k]=1
for i in c:
  ans+=c[i]*(c[i]-1)//2
print(ans)
### BUGGY CODE ###

import queue


def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = queue.Queue()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.put(s)
    
    n_days = 0
    n_states_left = max_state
    while today_states.qsize() > 0:
        n_days += 1
        n_today_states = today_states.qsize()
        if n_today_states == 0:
            break
        for _ in range(n_today_states):
            s = today_states.get()
            n_states_left -= 1
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    today_states.put(ns)
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = set()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.add(s)
    
    n_days = 0
    n_states_left = max_state
    while len(today_states) > 0:
        n_days += 1
        if len(today_states) == 0:
            break
        n_states_left -= len(today_states)
        nextday_states = set()
        for s in today_states:
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    nextday_states.add(ns)
        today_states = nextday_states
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


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

H, W = map(int, input().split())
g = []
q = []
cnt = 0
for h in range(H):
    A = str(input())
    row = []
    for w in range(W):
        row.append(A[w])
        if A[w] == '#':
            cnt += 1
            q.append([h, w])
    g.append(row)
ans = 0
dh = [1, 0, 0, -1]
dw = [0, -1, 1, 0]
while cnt < H * W:
    ans += 1
    nextq = []
    while q:
        h, w = q.pop()
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.':
                g[nh][nw] = '#'
                nextq.append([nh, nw])
                cnt += 1
    q = nextq
print(ans)


### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    g = []
    q = []
    cnt = 0
    for h in range(H):
        A = str(input())
        row = []
        for w in range(W):
            row.append(A[w])
            if A[w] == '#':
                cnt += 1
                q.append([h, w])
        g.append(row)
    ans = 0
    dh = [1, 0, 0, -1]
    dw = [0, -1, 1, 0]
    while cnt < H * W:
        ans += 1
        nextq = []
        while q:
            h, w = q.pop()
            for i in range(4):
                nh = h + dh[i]
                nw = w + dw[i]
                if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.':
                    g[nh][nw] = '#'
                    nextq.append([nh, nw])
                    cnt += 1
        q = nextq
    print(ans)
main()
### BUGGY CODE ###

K=int(input())
ANS=[]
for i in range(1,10**6*3):
  LEN=len(str(i))
  STR=str(i)
  if LEN==1:
    ANS+=[i]
  for k in range(LEN-1):
    if abs(int(STR[k])-int(STR[k+1]))>1:
      break
    if k==LEN-2:
      ANS+=[i]
ans=ANS[K-1] 
print(ans)

### FIXED CODE ###

K=int(input())
ANS=[i for i in range(1,10)]
i=0
while len(ANS)<=10**5:
  last=str(ANS[i])[-1]
  if last=="0":
    ANS+=[ANS[i]*10,ANS[i]*10+1]
  elif last=="9":
    ANS+=[ANS[i]*10+8,ANS[i]*10+9]
  else:
    ANS+=[ANS[i]*10+int(last)-1,ANS[i]*10+int(last),ANS[i]*10+int(last)+1]
  i+=1  
ans=ANS[K-1]
print(ans)
### BUGGY CODE ###

H, W =  map(int, input().split())

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

Gs = np.asarray(S)
Gs_ = np.rot90(Gs, k=1)

def count_light(Gs):
    Gc = []
    for gs in Gs:
        count = 0
        gc = []
        for s in gs:
            if s == '#':
                count = 0
                gc.append(0)
            else:
                count += 1
                gc.append(count)
        Gc.append(gc)

    Gc = np.asarray(Gc)

    Gn = []
    for gc in Gc:
        count = -1
        gn = []
        for c in gc[::-1]:
            if c == 0:
                count = -1
                gn.append(0)
            else:
                if count == -1:
                    count = c
                gn.append(count)
        Gn.append(gn[::-1])

    Gn = np.asarray(Gn)
    return Gn

Gn = count_light(Gs)
Gn_ = count_light(Gs_)
Gn_ = np.rot90(Gn_, k=3)

ans = 0
for gn, gn_ in zip(Gn, Gn_):
    for n, n_ in zip(gn, gn_):
        ans = max(ans, n+n_-1)
        
print(ans)

### FIXED CODE ###

H, W =  map(int, input().split())

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

def count_light(Gs, h, w):
    Gc = np.empty((h,w))
    for i in range(w):
        if i == 0:
            Gc[:, i] = Gs[:, i]
        else:
            Gc[:, i] = (Gc[:, i-1] + 1) * Gs[:, i]

    return Gc

Gs1 = np.asarray(S) == "."
Gn1 = count_light(Gs1, H, W)

Gs2 = np.rot90(Gs1, k=1)
Gn2 = count_light(Gs2, W, H)

Gs3 = np.rot90(Gs2, k=1)
Gn3 = count_light(Gs3, H, W)

Gs4 = np.rot90(Gs3, k=1)
Gn4 = count_light(Gs4, W, H)

Gn2 = np.rot90(Gn2, k=-1)
Gn3 = np.rot90(Gn3, k=-2)
Gn4 = np.rot90(Gn4, k=-3)

Gsum = Gn1+Gn2+Gn3+Gn4
ans = int(np.max(Gsum)-3)
print(ans)
### BUGGY CODE ###

z=list(map(int,input().split()))
a=[]
b=[]
for i in range(z[2]):
    a.append(int(input()))
for i in range(z[0]):
    if z[2]-a.count(i+1)>=z[1]:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

n,k,q=map(int,input().split())
a,b=[int(input()) for _ in range(q)],[0]*n
for i in a:
    b[i-1]+=1
for i in b:
    print('Yes' if i+k-q>0 else 'No')
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ind = []
    for i in range(N):
        ind.append(A.index(i+1))
    
    ind.reverse()
    for i in range(N-1):
        if ind[i] < ind[i+1]:
            print(N-i-1)
            exit()

    print(0)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    ind = [0 for _ in range(N)]
    for i in range(N):
        A = int(input())
        ind[A-1] = i

    ans = 0
    count = 0
    for i in range(N-1):
        if ind[i] < ind[i+1]:
            count += 1
        else:
            ans = max(ans,count)
            count = 0
        ans = max(ans,count)

    print(N-ans-1) 

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

from sys import stdin
import math
input=input=stdin.readline().rstrip().split()
for i in range(len(input)):
  input[i]=int(input[i])

output=0
R=input[0]
G=input[1]
B=input[2]
N=input[3]
for r in range(math.floor(N/R)+1):
    for g in range(math.floor(N/G)+1):
        #for b in range(math.floor(N/B)+1):
        #print(r,g)
        #if r*R+g*G+b*B==N:
        b=N-(r*R+g*G)
        #b/B
        if b>=0:
            if b % B == 0:
                #print(r,g)
                output+=1
print(output)

### FIXED CODE ###

from sys import stdin
import math
input=input=stdin.readline().rstrip().split()
for i in range(len(input)):
  input[i]=int(input[i])

output=0
R=input[0]
G=input[1]
B=input[2]
N=input[3]
for r in range(math.floor(N/R)+1):
    for g in range(math.floor(N/G)+1):
        #for b in range(math.floor(N/B)+1):
        #print(r,g)
        #if r*R+g*G+b*B==N:
        b=N-(r*R+g*G)
        #b/B
        #if b>=0:
        if b<0:
            break
        if b % B == 0:
            #print(r,g)
            output+=1
print(output)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 2*10**5 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# 足す時は0~iまで一律に足し、返すのはi番目の値
class imosBIT():
    def __init__(self, N):
        self.N = N+1
        self.bit = [0 for _ in range(self.N+1)]
    
    def __str__(self):
        ret = []
        for i in range(1, self.N+1):
            ret.append(self.__getitem__(i))
        return "[" + ", ".join([str(a) for a in ret]) + "]"

    def __getitem__(self, i):
        i += 1
        s = 0
        while i <= self.N:
            s = (s + self.bit[i]) % mod
            i += i & -i
        return s

    def add(self, i, x):
        i += 1
        while i > 0:
            self.bit[i] = (self.bit[i] + x) % mod
            i -= i & -i
    
    # (i, N]に全てたす
    def addover(self, i, x):
        self.add(self.N-1, x)
        self.add(i, -x)

B, W = map(int, input().split())
N = B+W
Abit = imosBIT(N+1)
Bbit = imosBIT(N+1)
inv2 = pow(2, mod-2, mod)
t = inv2
for i in range(N):
    if i+1 >= W:
        Abit.addover(i, t*cmb(i, W-1)%mod)
    if i+1 >= B:
        Bbit.addover(i, t*cmb(i, B-1)%mod)
    t = t*inv2 % mod

for i in range(N):
    ans = (1 + Abit[i] - Bbit[i]) * inv2 % mod
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 2*10**5 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# 足す時は0~iまで一律に足し、返すのはi番目の値
class imosBIT():
    def __init__(self, N):
        self.N = N+1
        self.bit = [0 for _ in range(self.N+1)]
    
    def __str__(self):
        ret = []
        for i in range(1, self.N+1):
            ret.append(self.__getitem__(i))
        return "[" + ", ".join([str(a) for a in ret]) + "]"

    def __getitem__(self, i):
        i += 1
        s = 0
        while i <= self.N:
            s = (s + self.bit[i]) % mod
            i += i & -i
        return s

    def add(self, i, x):
        i += 1
        while i > 0:
            self.bit[i] = (self.bit[i] + x) % mod
            i -= i & -i
    
    # (i, N]に全てたす
    def addover(self, i, x):
        self.add(self.N-1, x)
        self.add(i, -x)

B, W = map(int, input().split())
N = B+W
Abit = imosBIT(N+1)
Bbit = imosBIT(N+1)
inv2 = pow(2, mod-2, mod)
t = inv2
for i in range(N):
    if i+1 >= W:
        Abit.addover(i, t*cmb(i, W-1)%mod)
    if i+1 >= B:
        Bbit.addover(i, t*cmb(i, B-1)%mod)
    t = t*inv2 % mod

for i in range(N):
    ans = (1 + Abit[i] - Bbit[i]) * inv2 % mod
    print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())
x_list = np.array(list(map(int, input().split())))

count = 0
for xi in x_list:
  if np.sum(xi%x_list==0) == 1:
      count += 1
print(count)

### FIXED CODE ###

N = int(input())
a_list = sorted(list(map(int, input().split())))
a_max = a_list[-1]

count = [0] * (a_max+1)

for a in a_list:
  for j in range(a, a_max+1, a):
    count[j] += 1
  
ans = 0
for a in a_list:
  if count[a] == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

import bisect
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
H = list(H)
now = 0
ans = 0
for now in range(n):
  if H[now] > 0:
    l = -(-H[now]//a)
    ans += l
    l *= a
    for i in range(now, bisect.bisect_right(X, X[now]+2*d)):
      H[i] -= l
print(ans)

### FIXED CODE ###

import bisect
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
K = [-(-i//a) for i in H]
L = [0]*(n+2)
ans = 0
for i in range(n):
  L[i+1] += L[i]
  s = max(K[i]-L[i+1], 0)
  ans += s
  L[i+1] += s
  L[bisect.bisect_right(X, X[i]+2*d)+1] -= s
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

input_list_1 = input().split()

N = int(input_list_1[0])
M = int(input_list_1[1])
clear_list = []
for i in range(1,N+1):
    clear_list.append(i)
    
for i in range(M):
    input_list_2 = input().split()
    start = int(input_list_2[0])
    end = int(input_list_2[1])

    for i in range(1,N+1):
        if i < start or end < i:
            try:
                clear_list.remove(i)
            except:
                pass

print(len(clear_list))    


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from sys import stdin

N, M = [int(x) for x in stdin.readline().rstrip().split()]

clear_list = [1] * N
start = 0
end = 0
ans_start = 0
ans_end = 0
    
for i in range(M):
    start, end  = [int(x) for x in stdin.readline().rstrip().split()]
    if ans_start == 0 or ans_start < start : 
        ans_start = start
    if ans_end == 0 or ans_end > end:
        ans_end = end

if ans_end - ans_start < 0:
    print(0)
else:
    print(ans_end - ans_start + 1 )
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
def count(l,r):
    s = S[l-1:r]
    cnt = 0
    for i in range(len(s)-1):
        if s[i] == "A" and s[i+1] == "C":
            cnt += 1
    return cnt
    
for i in range(Q):
    l,r = map(int,input().split())
    print(count(l,r))

### FIXED CODE ###

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

t = [0]
for i in range(N):
    t.append(t[-1]+1 if S[i:i+2] == "AC" else t[-1])
for i in range(Q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])